CS 70 Discrete Mathematics for CSSpring 2005 Clancy/Wagner MT 1PRINT your name:,(last) (first)SIGN your name:PRINT your class account name: cs70-Name of the person sitting to your left:Name of the person sitting to your right:You may consult any books, notes, or other paper-based inanimate objects available to you. Calculators andcomputers are not permitted. Please write your answers in the spaces provided in the test; in particular, wewill not grade anything on the back of an exam page unless we are clearly told on the front of the page tolook there.You have 80 minutes. There are 5 questions, of varying credit (40 points total). The questions are of varyingdifficulty, so avoid spending too long on any one question.Do not turn this page until your instructor tells you to do so.Problem 1Problem 2Problem 3Problem 4Problem 5TotalCS 70, Spring 2005, MT 1 1Problem 1. [True or false] (12 points)Circle TRUE or FALSE. You do not need to justify your answers on this problem.Reminder: N = {0,1,2,3,...} represents the set of non-negative integers.(a) TRUE or FALSE: The propositions P =⇒ Q and Q =⇒ P are logically equivalent.(b) TRUE or FALSE: The proposition Q∨ P∨ (P =⇒ Q) is guaranteed to be true, no matter what the truthvalues of P and Q may be.(c) TRUE or FALSE: If we are told that the proposition P is true, we are entitled to conclude that ((P =⇒Q) =⇒ P) =⇒ Q must also be true.(d) TRUE or FALSE: ∀n ∈ N . (x2− x = 0) ∨ (x ≥ 2).(e) TRUE or FALSE: ∀x ∈ N . ∃y ∈ N . ∀z ∈ N . x+ y = z.(f) TRUE or FALSE: ∀x ∈ N . ∃y ∈ N . x2= y.(g) TRUE or FALSE: (∀x ∈ N . ∃y ∈ N . x < y) ≡ (∃y ∈ N . ∀x ∈ N . x < y).(h) TRUE or FALSE: Let P(n) denote the proposition that 1 + 2+ ··· + n + (n + 1) = n(n + 1)/2. Then∀n ∈ N . P(n) =⇒ P(n+ 1) is true.(i) TRUE or FALSE: Define the relation ≺ so that n ≺ m iff n divides m and n < m. Then the relation ≺ isa well-ordering on N.(j) TRUE or FALSE: Any 2-party cake-cutting protocol that is fair is also envy-free.(k) TRUE or FALSE: In the stable marriage problem, if M denotes the male-optimal matching, then thereexists a girl who does not get her optimal boy in M (i.e., her mate in M is not her optimal boy).(l) TRUE or FALSE: Suppose that we have n boys, b1,. . .,bn, and n girls, g1,. . .,gn. Assume that g1lists b1as her top choice, g2lists b2as her top choice, and so on, so that biappears at the front of gi’s preferencelist for all i. If we run the Traditional Marriage Algorithm, then the resulting matching is guaranteed tomatch gito bifor all i.CS 70, Spring 2005, MT 1 2Problem 2. [A peculiar sequence] (6 points)Define u0= u1= 1, and define un= (n− 1)un−2for n = 2,3,4, . ... By convention, 0! = 1.Prove that un+1un= n! for all n ∈ N.CS 70, Spring 2005, MT 1 3Problem 3. [Recognizing complete binary trees] (6 points)A binary tree is a tree with the property that every internal node (i.e., every non-leaf node) has exactly twochildren. A binary tree is called complete if all its leaves are at the same depth.Assume that if T is a tree, then the helper function (leaf? T) returns true iff T has no children. Also, ifT is a tree with children, then (left T) returns the left subtree of T and (right T) returns the rightsubtree of T. Consider the following algorithm:(define (complete? T)(if (leaf? T)#t(and (complete? (left T)) (complete? (right T))) ) )Here is an attempt to prove this algorithm correct.Theorem 0.1: For all trees T, if (complete? T) returns true, then there exists k ∈ N such that everyleaf is at distance k from the root of T.Proof: Use proof by structural induction. Base case: Suppose the tree T has no children, so that (leaf?T) returns true. Then (complete? T) also returns true, and moreover every leaf is at distance 0 fromthe root (i.e., k = 0), so the implication is true in this case.Inductive step: Assume the claim is true for trees TL and TR. Suppose the tree T is constructed so that theleft subtree of the root is TL, and the right subtree is TR. Assume (complete? T) returns true. By thedefinition of (complete? T), this means that (complete? TL) and (complete? TR) must bothhave returned true. Then, by the induction hypothesis, there is some k so that every leaf of TL is at distancek from the root of TL. Similarly, there is some k so that every leaf of TR is at distance k from the root ofTR. In both cases, the leaf is at distance k + 1 from the root of T (by the way that T was constructed fromTL and TR). Also, every leaf of T falls into one of these two cases. Consequently, we have proven that if(complete? T) returns true, then there exists k0∈ N so that every leaf of T is at distance k0from the rootof T (in fact, k0= k+ 1). 2This problem is continued on the following page.CS 70, Spring 2005, MT 1 4Please tell us whether this proof is valid. In particular, answer each of the following questions with “Yes” or“No”, and explain your answer:(a) Is the use of structural induction appropriate?(b) Is the proof of the base case OK?(c) Is the proof of the inductive step OK?(d) Bottom line: Is the proof valid?CS 70, Spring 2005, MT 1 5Problem 4. [Working with expressions some more] (8 points)This question involves expressions generated by the following rules. (Note that rule 2. is slightly differentfrom what you saw on a previous quiz.)1. A single digit is an expression.2. If E1and E2are expressions, then E1E2is an expression.3. If E is an expression, then (E) is an expression.Prove that no expression generated by the three rules above contains an open parenthesis immediately fol-lowed by a close parenthesis, i.e. “()”.CS 70, Spring 2005, MT 1 6Problem 5. [A variant on merge sort] (8 points)Let Fkdenote the kth Fibonacci number. Reminder: the Fibonacci numbers are defined by F0= F1= 1, andFk= Fk−1+ Fk−2for k ≥ 2. Consider the following variation on merge sort, which assumes that the numberof elements in its list argument L is a Fibonacci number Fk.algorithm FibMergesort(L){L is a list of items from a totally ordered set, whose length is a Fibonacci number Fk}if L contains only 1 element, then return Lelsedivide L into L1(the first Fk−1items) and L2(the remaining Fk−2items)sortedL1:= FibMergesort(L1)sortedL2:= FibMergesort(L2)sortedL := Merge(sortedL1,sortedL2)return sortedLAssuming that the “divide” step in FibMergesort takes constant time (no comparisons) and Merge behavesas described in the lecture notes, identify which of the following expressions most
View Full Document
Unlocking...