UC Berkeley—CS 170 Problem Set 9Lecturer: David Wagner Due on April 17 at 3:30 p.m.Problem Set 9 for CS 170FormattingPlease use the following format for the top of the solution you turn in, with one line peritem below (in the order shown below):<your username on cory.eecs><your full name>CS170, Spring 2003Homework #9Section <your section number>Partners: <your list of partners>(Remember to write your section number, not the name of your TA or the time of yoursection.) This will make it easier for us to sort and process your homeworks. Thank you!NoteWhen asked for an algorithm you must give (1) a brief informal description of the algorithm,(2) a precise description using pseudo-code, (3) an informal argument for termination andcorrectness of the algorithm, and (4) an analysis of the running time of the algorithm. Beclear about what the input to the algorithm is, how you measure the size of the input, andwhat constitutes a “step” in your running-time analysis.Problem 0. [Any questions?] (5 points)What’s the one thing you’d most like to see explained better in lecture or discussion sections?A one-line answer would be appreciated.(Sometimes we botch the description of some concept, leaving people confused. Some-times we omit things people would like to hear about. Sometimes the book is very confusingon some point. Here’s your chance to tell us what those things were.)Problem 1. [Card Game] (30 points)Consider the following card game. The dealer lays out n cards face up and side-by-sidein a line, so that both the player and the dealer know the face value of each card. Theplayer and the dealer then take turns taking a card from either end (but only the ends, notanywhere in the middle) of the line of remaining cards, with the player going first. Aftern of these turns, all of the cards have been taken, and the player wins if the cards in herhand have a larger sum than the cards in the dealer’s hand. The dealer wins if his sum isgreater than or equal to the player’s sum, and he always makes the best possible move hecan.Alice has found a soon-to-be-bankrupt casino that allows players to bet on this gameafter the cards have been dealt.Problem set 9 due on April 17 at 3:30 p.m. 2(a) Design an algorithm for Alice to use in determining when to bet on this game. It isgiven as input n and an array C where C[i] contains the value of card i. It shouldoutput “Yes” if Alice can definitely win (assuming she makes the right moves) or “No”if it is possible for the dealer to win – Alice doesn’t take chances.(b) How would you modify your algorithm to output an optimal move for each possibleintermediate situation? For example:Cards 1..52 remain, take card 1Cards 2..52 remain, take card 2...Cards 5..43 remain, take card 43...Cards 20..52 remain, take card 20...Cards 33..33 remain, take card 33...Problem 2. [Randomized 2-SAT] (35 points)2-SAT (for 2-Satisfiability) is a (relatively easy) special case of the NP-complete problemSAT.In satisfiability problems, you are given a boolean formula φ and you are asked todetermine whether or not it has a satisfying assignment (some True/False setting of thevariables in φ that makes the whole formula true) and return a satisfying assignment if itexists.In 2-SAT, it is required that φ is in 2-conjunctive normal form (2-CNF). This meansthat the input looks something like:(x4∨ x2) ∧ (x3∨ x2) ∧ (x1∨ x2) ∧ . . . ∧ (x501∨ x24)That is, φ is a conjunction (and) of clauses, where each clause has two literals. A literalis an instance of a variable or its negation, a disjunction (or) of two literals makes a clause,and a conjunction of these clauses makes a 2-CNF formula. For example, inφ = (x1∨ x2) ∧ (x2∨ x3),x1, x2, and x3are the variables, (x1∨ x2) is a clause, and x1and x2are literals in thatclause.A satisfying assignment A for a formula φ is a mapping A : {x1, x2, x3} → {True, False}that makes the formula true. For example, if A is an assignment such that A(x1) = Falseand A(x3) = True, it is a satisfying assignment for φ (notice x2’s value does not matter).Finally, the size of a formula φ is the number of clauses. Note that a formula φ of sizen has at most 2n variables.Consider the following algorithm:Problem set 9 due on April 17 at 3:30 p.m. 3MC-2-SAT(φ):1: for each variable xiin φ do:2: A[i] ← False3: do k times:4: if φ is satisfied:5: return Satisfiable by A6: randomly pick an unsatisfied clause (li∨ lj) from φ7: randomly pick v from {i, j}8: A[v] ← A[v]9: return UnsatisfiableThe value of k in line 3 will be determined in part (c) below.(a) Can MC-2-SAT ever output Unsatisfiable when run on a formula that is in fact sat-isfiable?(b) Can MC-2-SAT ever output Satisfiable when run on a formula that is in fact unsatis-fiable?(c) Show that there is a choice of k (as a function of n) so that k = O(n2) and that issufficient to find a satisfying assignment (if one exists) in lines 3–8 with probability atleast 1 −12100.A useful fact: Suppose we have random variables Xi(i ≥ 0) that take values in therange {0, . . . , n}. Suppose they’re defined such that Xi+1= 1 if Xi= 0, Xi+1= n ifXi= n, and otherwise: Xi+1= Xi+1 with probability pi≥ 1/2, Xi−1 with probability1 − pi(i.e., ≤ 1/2)1. Let T = min{k | Xk= n}. Note that T is a random variable.Then it turns out that the expected value of T is at most (n − 1)2. (You do not needto prove this.)Hint: Let B be a satisfying assignment. Define Xiin terms of the difference betweenA and B at each iteration of the main loop.Hint: Given only that E[T ] ≤ (n −1)2, how big should k0be so that Pr[T > k0] ≤ 1/2?If those first k0steps are taken but still Xk0< n, what is the probability that X2k0< n(i.e., what is Pr[T > 2k0| T > k0])?(d) Taking into account your choice of k in part (c), what is the running time of MC-2-SAT(φ)as a function of n, the size of φ?1Strictly speaking, this random ±1 change must happen independently of the values of X0, . . . , Xi. How-ever, you don’t need to worry about independence for this problem.Problem set 9 due on April 17 at 3:30 p.m. 4Problem 3. [Deterministic 2-SAT] (30 points)Refer to the definition of 2-SAT in Problem 2. Note that Problem 2 gives a randomizedalgorithm to solve 2-SAT.For this problem, give a deterministic algorithm to solve 2-SAT. (Deterministic meansthat you cannot use any randomness in your algorithm.) Use the method for solving Hornformula that was given in class as a subroutine. You do not