Midterm Spring 2012 Algorithms and Data CS 4800 Karl Lieberherr Open Book and Open Notes. 6 questions: 1. 30 points 2. 20 points 3. 20 points 4. 10 points 5. 30 points 6. 20 points 130 points total If you use the e-book version of the text book on your laptop, turn the communication switch to off. You are not allowed to communicate with others during the exam. Question 1: Algorithm Design 30 points =============================================== Consider the following tree construction problem TCP(x,y): Instance: Positive integers x and y, y<=x. Solution: A special binary search tree (definition below) of minimum depth with x leaves labeled with keys 0 to x-1. Each path from the root to a leaf has at most y left branches. A special binary search tree satisfies the following: (1) The left subtree of a node contains only nodes with keys less than the node's key. (2) The right subtree of a node contains only nodes with keys greater than or equal to the node's key. (3) Both the left and right subtrees must also be special binary search trees. (4) Every node other than the leaves has two children. Describe your algorithm that constructs minimum depth special binary search tree for given x and y. Hint: Connect to an algorithm we covered in class. Question 2: BFS Algorithm 20 points ================================================ Consider claims C-Graph(n,c,k) of the following form: c and n are a positive integer >= 2. k is a positive integer >= 1. n is a multiple of c. Claim C-Graph(n,c,k) is defined by for all graphs G=(V,E) with |V|=n and two nodes s and t in V with dist(s,t) > n/c there exists an integer k between 1 and n so that the removal of at most k nodes (different from s and t) and all edges incident with them eliminates all s-t paths. Part 2.1: For each of the following claims say whether they are true or false and if they are true, whether they can be strengthened and by how much. Strengthening means to lower k. C-Graph(9,3,3) C-Graph(160,4,10) C-Graph(10,2,1) Part 2.2: Now we consider a variation of the above claims: We call the claims C1(n,c,k) which is the same as C-Graph(n,c,k) except that the condition "n is a multiple of c" is dropped. Is C1-Graph(11,3,2) true or false? Explain your answer. Question 3: Simple Algorithm Design 20 points ===================================================== Consider the following two claims: based on the propositional expression: !Q or (R and S) or (!R and !S) where Q, R and S are Boolean variables. Here is the truth table computed by Wolfram Alpha: Q | R | S | !Q||(R&&S)||(!R&&!S) T | T | T | T T | T | F | F T | F | T | F T | F | F | T F | T | T | T F | T | F | T F | F | T | T F | F | F | T Claim 1: ForAll Q, R in Boolean Exists S in Boolean !Q or (R and S) or (!R and !S) Claim 2: Exists Q,R ForAll S: !(!Q or (R and S) or (!R and !S)) and assert whether they are true or false. If a claim is true, give your defense strategy. If the first one is true: give your algorithm which maps input Q, R into S. If the second one is true, give Q and R. Question 4: Landau Notation 10 points =================================================== Consider the following true claim: 10*n^2 + 100*n + 1000 in O(n^2). You are the proposer of the claim, i.e. the ExistsP player. What is your move to defend the claim. The answer consists of two numbers. Question 5: Algorithms we covered 30 points ========================================= Part 5.1: Consider the following claims: 5.1.1 For all directed graphs G there exists a topological ordering. 5.1.2 For all undirected graphs G there exists a two-coloring. 5.1.3 For all weighted CNFs with clauses of length 2 there exists an assignment satisfying the fraction >= 7/8. 5.1.4 There exists a weighted CNF S in NoPairContradictions so that for all assignments J: fsat(S,J) <= 7/10. Some are true and others are false. Explain briefly which are true and and which are false. For the false claims suggest a minimal change to make them true. If there are multiple ways to make them true, choose the optimum claim. Optimally strengthen true claims. Part 5.2: We say that there exists a polynomial-time algorithm for a claim of the form ForAll x in X Exists y in Y: p(x,y) if there exists a polynomial-time algorithm that takes as input x and produces y as result. 5.2.1 There exists a polynomial time algorithm for the following claim: For all directed graphs G with nodes s and t where t is reachable from s there exists a shortest path from s to t. 5.2.2 There exists a polynomial-time algorithm for the following claim: For n men and n women and all preference lists where each of the n women ranks each man and each of the n men ranks each woman there exists a stable matching. Explain whether these statements are true or false. If they are true, refer to the relevant algorithm in the text book. Question 6: Reasoning about algorithmic claims 20 points ================================================= Answer this question when you are done with the others. Consider claims of this ForAll-Exists form: ForAll x in X Exists y in Y: p(x,y). Why is refuting a claim different from proving it false? Why is defending a claim different from proving it true?