MATH 211 Final, Fall 2006

Math 211 — Fall 2006–07 Discrete Structures Final exam, January 18 — Duration: 2 hours 15 minutes GRADES (each problem is worth 12 points): 1 2 3 4 5 6 7 8 9 10 TOTAL/120 YOUR NAME: YOUR AUB ID#: PLEASE CIRCLE YOUR SECTION: Section 1 Section 2 Section 3 Section 4 Recitation W 4 Recitation W 11 Recitation Th 12:30 Recitation Th 3:30 Professor Makdisi Ms. Karam Ms. Karam Ms. Karam The usual instructions: 1. Write your NAME and AUB ID number, and circle your SECTION above. 2. Solve the problems inside the booklet. Explain your reasoning precisely and clearly to ensure full credit. Partial solutions will receive partial credit. Each problem is worth 12 points. 3. You may use the back of each page for scratchwork OR for solutions. There are four blank sheets at the end, for extra scratchwork or solutions. If you need to continue a solution on another page, INDICATE CLEARLY WHERE THE GRADER SHOULD CONTINUE READING. 4. Open book and notes. NO CALCULATORS ALLOWED. Turn OFF and put away any cell phones. 5. You do not need to simplify your answers to counting problems — for example, if the answer is �211 30 � + (12!)7 · 6 · 5, just leave it that way. GOOD LUCK! i An overview of the exam problems. Each problem is worth 12 points. Take a minute to look at all the questions, THEN solve each problem on its corresponding page INSIDE the booklet. 1. Show that (p → r) ∧ (q → r) is logically equivalent to (p ∨ q) → r in two different ways, (a) and (b+c): a) Use a truth table. b) Give a direct proof that if (p → r) ∧ (q → r), then (p ∨ q) → r. c) Give a direct proof of the converse of the statement in (b). 2. a) Show that the following statement is TRUE: ∀n ∈ Z, � n2 ̸≡ 0 (mod 12) � → � n ̸≡ 0 (mod 12) � . b) Show that the converse of the above statement is FALSE. 3. Given a function f : X → Y . a) Show that for all subsets S ⊆ X, we have S ⊆ f −1(f(S)). b) Show that f is injective if and only if for all S ⊆ X, we have S = f −1(f(S)). 4. Find the cardinality |X| of the following set (recall that 0 is included in N): X = {(x1, x2, x3, x4, x5) ∈ N5 | x1 + · · · + x5 = 24, exactly TWO of the variables x1, . . . , x5 are equal to 6, and the others are all ≤ 5}. 5. a) Show directly from the definition that 5n is O(n!). (Make sure to find explicit constants C and k.) b) (UNRELATED) Define a function f : N → N recursively by f(0) = 211, f(1) = 201, f(2) = 230, ∀n ≥ 3, f(n) = f(n − 3) + 7. Find a general formula for f(n) (hint: the formula depends on n mod 3), and use it to show that f(n) is Θ(n). 6. We wish to write an algorithm to compute the function f(n), defined by f(n) = the product of all positive odd numbers k such that k ≤ n. ii For example, f(10) = 1 · 3 · 5 · 7 · 9 and f(11) = 1 · 3 · 5 · 7 · 9 · 11. Note that to tell if a number is odd, you can use the function IsOdd(n), which return true or false depending on whether n is odd or not. You can also use a similar function IsEven(n). a) Write an algorithm (in GAP or pseudocode) that computes f(n) WITHOUT any recursion. (Use a loop.) b) Write a RECURSIVE algorithm to compute f(n). 7. a) Write the number 42(= 4210) in base 3. b) (UNRELATED) A ternary string is a string made from the symbols 0, 1, 2. For example, 010122011 is a ternary string. Define an = the number of ternary strings of length n that do NOT contain 00 anywhere. Find a recurrence for an, and specify the initial conditions. Do NOT solve the recurrence for the general value of an. 8. a) Use the (extended) Euclidean algorithm to find the inverse of 30 modulo 43. In other words, find x ∈ Z such that 30x ≡ 1 (mod 43). b) (UNRELATED) Show that the while loop below is repeated ⌈log2 log2 x⌉ times: << x is some number greater than 2 from earlier in the program >> a := 2; while a < x do a := a*a; od; << program continues >> 9. Write a RECURSIVE algorithm totalsum(ll) (in GAP or pseudocode) that adds up all the numbers in the list ll and all its sublists. For instance, totalsum([3, [1, 4, 1], [5, [9, 2], [6, 5, 3]]]) = 3 + 1 + 4 + 1 + 5 + 9 + 2 + 6 + 5 + 3 = 31. You may use the GAP function IsList to tell if you have a list or not. Hint: you will probably want to keep track of the sum in a variable ans, and use a loop of the form for x in ll do . . . to compute something involving each sublist x. 10. a) Find the general solution of the recurrence (∗) ak = 6ak−1 − 8ak−2, for k ≥ 2. b) In a certain “divide-and-conquer” algorithm with complexity f(n), we obtain the recurrence (∗∗) f(n) = 4f(⌈n/2⌉) + n for n ≥ 2, f(1) = 1. Define ak = f(2k), and show that ak satisfies the recurrence (∗). (Hint: from (∗∗), deduce a first recurrence for ak that you must then use twice to prove (∗).) c) Find the exact value of f(2k). (Caution: a0 = f(20) = 1.) iii