Massachusetts Institute of Technology Handout 10 6.042J/18.062J: Mathematics for Computer Science September 23, 2000 Professors Nancy Lynch and Shlomi Dolev

Mini-Quiz 3

1. Write your name:

Velleman 2.3, Ex. 5(a)(b): Let I = {2, 3}, and for each i ∈ I let A_{i} = {i, 2i} and B_{i} = {i, i + 1}.

(a) List the elements of the sets A_{i} and B_{i} for i ∈ I.

(b) Find ∩_{i∈I}(A_{i} ∪ B_{i}) and (∩_{i∈I}A_{i}) ∪ (∩_{i∈I}B_{i}). Are they the same?

Tutorial 3 Problems

Problem 1 Well ordering

Rosen 3.2, Ex. 58: The well-ordering property can be used to show that there is a unique greatest common divisor of two positive integers. Let a and b be positive integers, and let S be the set of positive integers of the form as + bt, where s and t are integers.

a) Show that S is nonempty.

b) Use the well-ordering property to show that S has a smallest element c.

c) Show that if d is a common divisor of a and b, then d is a divisor of c.

d) Show that c|a and c|b. (Hint: First, assume that c |̸a. Then a = qc + r, where 0 < r < c. Show that r ∈ S, contradicting the choice of c.)

e) Conclude from (c) and (d) that the greatest common divisor of a and b exists. Finish the proof by showing that this greatest common divisor of two positive integers is unique.

Problem 2 Induction and Recursive Algorithms

Procedure binary search(x, i, j) m := ⌊(i + j)/2⌋ if x = a_{m} then

location := m else if (x < a_{m} and i < m) then

binary search(x, i, m − 1) else if (x > a_{m} and j > m) then

binary search(x, m + 1, j) else location := 0

The above procedure searches x in a sequence a_{1}, a_{2}, …, a_{n} (when called with i = 1, j = n). Prove by (strong) induction that the binary search procedure sets location to an index i such that a_{i} = x, if there is such an index, and otherwise sets location to 0.

Problem 3 Relations

(a) Consider the following putative theorem and the accompanying proof.

Theorem. For any sets A, B, C, and D, if A × B ⊆ C × D then A ⊆ C and B ⊆ D.

Proof. Suppose A × B ⊆ C × D. Let a be an arbitrary element of A, b be an arbitrary element of B, and (a, b) ∈ A × B. Since A × B ⊆ C × D, it follows that (a, b) ∈ C × D. Therefore, a ∈ C and b ∈ D. Since a and b were arbitrary elements of A and B, respectively, this shows that A ⊆ C and B ⊆ D.

Is the proof correct? If so, what proof strategies does it use? If not, can it be fixed? Is the theorem correct?

(b) Let A be the adjacency matrix for a digraph G with n vertices. Note that A is a zero-one valued n × n matrix. In this problem we use the Boolean “OR” operation, ∨, instead of “+” when multiplying zero-one valued matrices (this is called “boolean” matrix product).

(i) For k ∈ ℕ, let A^{k} be the kth Boolean power of A. Prove that A^{k}_{ij} = 1 iff there is a directed path of length k from the ith to the jth vertex of G.

(ii) Let B = A ∨ I where I is the n × n identity matrix. Prove that B^{k}_{ij} = 1 iff there is a directed path of length ≤ k from the ith to the jth vertex of G.

(iii) Conclude that B^{n}_{ij} = 1 iff there is a directed path from the ith to the jth vertex.

Problem 4 Scheduling Courses

We consider a simple kind of scheduling problem — for MIT courses with prerequisites. The problem is to determine how a student could complete all of the courses in the fewest terms, under the simplifying, if unlikely, assumption that there is no limit on the number of courses a student can take in a term as long as their prerequisites have all been met. We model this problem with a digraph. An example is shown in Figure 1.

Figure 1: This is a picture of a directed acyclic graph. Vertices are labeled with course numbers. An edge from u to v indicates that course u is a prerequisite for course v.

(a) What’s the length of a critical path; find such a path.

(b) How many terms are necessary and sufficient to complete all of the courses in Figure 1, assuming prerequisites are observed, but course load is no issue? Prove your answer (both necessary and sufficient).