CS15-750 Midterm Exam 1 22 FEBRUARY 2000 Manuel Blum Your name:______________________, __________________________ FAMILY (LAST) GIVEN (FIRST) Your signature:_____________________________________________ Your email address:_________________________________________ Full credit is 100 pts. You should be able to get full credit entirely from problem 1. The remaining problems, though not worth nearly as much, are partial substitutes for solving problem 1, or for getting extra credit. Do all your work on the pages of this examination. 100 pts Problem 1: 3-COLORING A PLANAR TRIANGULATED GRAPH. In this problem, G = denotes a planar triangulated graph given by its planar triangulated embedding. Triangulated means that every face (including the outer face) is a "triangle," i.e. bounded by 3 edges. * Can every (such) planar triangulated graph G = be properly 3-colored? Recall that a proper 3-coloring is a map c: V -> {1,2,3} such that c(i) <> c(j) for all vertices i<>j in V such that is in E. Prove that the answer is yes, or give a counterexample. * Properly 3-color the following (such) graph: _______ / \ / --o--o-- / / /| /|\ \ / / /_o/_o_\ \ / / // |\ | \\ \ ( ( o< | \| >o ) \ \ \\_o__o_// / \ \ \ | /| / / \ \ \|/ |/ / \ --o--o-- \___/ * Give a linear time algorithm that, given any (such) planar triangulated graph G as input, either properly 3-colors the vertices of G or else proves (how?) that such a 3-coloring is impossible. To keep things simple, assume that all vertices are of degree greater or equal to 3. * Prove your algorithm correct. * Analyze the running time of your algorithm. * Specify clearly the data structure and what counts as a step. * (Extra Credit): What if the embedding of G in the plane is NOT given? 10 pts Problem 2: SPLAY TREES. * Do splay (1,S) on the following splay tree S: 4 S = / \ 2 5 / \ 1 3 * Has the splay tree become more balanced or less? 10 pts Problem 3: TREAPS Show the successive trees obtained in the process of deleting 5 from the treap below. Assume for this that the priorities of the elements 1,...,10 are given by 3 5 9 4 2 7 8 10 6 1. highest priority..: :..lowest priority 3 S = / \ 2 5 / / \ 1 4 9 / \ 7 10 / \ 6 8 15 pts Problem 4: AMORTIZED RUNNING TIME. Count 1 step for each bit flip. * What is the worst case time to add 1 to an n-bit binary number? <- n -> * Assuming that you start with the n-bit number 0 = 0 0... 0, what is the amortized time to perform a sequence of m "ADD 1" operations to such an n-bit binary number? <-- n --> * Assuming that you start with the n-bit number 0 = 0 0 ... 0, as above, what is the amortized time to perform a sequence of m "ADD 1" and "SUBTRACT 1" operations to an n-bit binary number? As usual, count 1 step for each bit flip. ============================================================= CS15-750 Midterm Exam 1 22 FEBRUARY 2000 Manuel Blum Your name:___SOLUTION___________ 100 pts SOLUTION Problem 1: 3-COLORING A PLANAR TRIANGULATED GRAPH. In this problem, G = denotes a planar triangulated graph together with its planar triangulated embedding. Triangulated means that every face (including the outer face) is a "triangle," i.e. bounded by 3 edges. * Can every (such) planar triangulated graph G = be properly 3-colored? Recall that a proper 3-coloring is a map c: V -> {1,2,3} such that c(i) <> c(j) for all pairs of distinct vertices i,j in V. Prove that the answer is yes, or give a counterexample. ANSWER in NO: o /|\ / | \ / | \ o | / \ | | / \ | |/ \| o-------o * Properly 3-color the following graph: _______ / \ / --W--R-- / / /| /|\ \ / / /_B/_W_\ \ / / // |\ | \\ \ ( ( R< | \| >B ) \ \ \\_W__R_// / \ \ \ | /| / / \ \ \|/ |/ / \ --B--W-- \___/ * Give a linear time algorithm that, given any (such) planar triangulated graph G as input, either properly 3-colors the vertices of G or else proves (how?) that such a 3-coloring is impossible. To keep things simple, assume that 1) the graph is connected, and 2) all vertices are of degree greater or equal to 3. ALGORITHM: The 3 colors are red, black, and white. Begin with a breadth first search starting from an arbitrary vertex, s, and put the vertices on a queue. The breadth first search should pick off the neighbors of s starting with any arbitrary neighbor, in clockwise order. After that, the breadth first search should pick off the neighbors of any given vertex in clockwise order, starting just clockwise of the one that has most recently already been put on the queue. Put those not yet on the queue clockwise into the queue. Label every vertex as it goes into the queue with its distance from s. *// At the end of the breadth first search, the queue will contain all vertices, starting with s at distance 0, followed by all vertices at distance 1 from s, and so on. After that, as time goes on, vertices will be taken out of the queue and colored. The queue will continue to have all and only uncolored vertices ordered by their distance from s. Vertices are colored when they are removed from the queue.//* Remove s from the queue and color it red. Remove the next vertex from the queue and color it white. This will be one of s's neighbors, at distance 1 from s. Traverse the neighbors of s clockwise around s, starting with the white vertex. These vertices, in this clockwise order, are pairwise adjacent (joined by edges). As they are removed from the queue, color these vertices (at a distance 1 from s) alternately black and white. While there are still vertices to color, proceed as follows: Assume that all vertices at distance d from s have been colored. Next color the vertices at distance d+1 from s: every vertex at distance d+1 from s is joined to at least 2 adjacent vertices that have already been colored. (Why? See * below.) These 2 necessarily have different colors (because they are joined by an edge). If they don't have different colors, return UNCOLORABLE. Otherwise, color the given vertex at distance d+1 with the sole remaining color. When all vertices have been colored, do one more pass in O(m) steps through all the edges to check that every edge joins two differently colored vertices. If not, return UNCOLORABLE. If yes, return the proper 3-coloring. * Prove your algorithm correct. ANSWER: SEE ABOVE. *Every vertex v at distance d+1 from s is adjacent to at least 1 vertex u at distance d from s. The edge is an edge on 2 faces. The faces are and . If either w1 or w2 is at distance d from s, then it is already colored and adjacent to u. If both are at distance d+1 from s, then both are adjacent to u and at least one of them is colored before v, because of the way that vertices are picked off in clockwise order, starting with one that is already colored. * Analyze the running time of your algorithm. ANSWER: linear time. * Specify clearly the data structure and what counts as a step. * (Extra Credit): What if the embedding of G in the plane is NOT given? ANSWER: The Hopcroft Tarjan algorithm for embedding a planar graph in the plane is linear time. If the graph is triangulated, then so is its embedding. 10 pts Problem 2: SPLAY TREES. * Do splay (1,S) on the following splay tree S: 4 2 1 S = / \ / \ \ 2 5 -> 1 4 -> 2 / \ / \ \ 1 3 3 5 4 / \ 3 5 * Has the splay tree become more balanced or less? ANSWER: LESS 10 pts Problem 3: TREAPS Show the successive trees obtained in the process of deleting 5 from the treap below. Assume for this that the priorities of the elements 1,...,10 are given by 3 5 9 4 2 7 8 10 6 1. highest priority..: :..lowest priority 3 3 3 S = / \ -> / \ -> / \ 2 5 2 9 2 9 / / \ / / \ / / \ 1 4 9 1 5 10 1 4 10 / \ / \ \ 7 10 4 7 5 / \ / \ \ 6 8 6 8 7 / \ 6 8 3 3 3 -> / \ -> / \ -> / \ 2 9 2 9 2 9 / / \ / / \ / / \ 1 4 10 1 4 10 1 4 10 \ \ \ 7 7 7 / \ / \ / \ 5 8 6 8 6 8 \ / 6 5 15 pts Problem 4: AMORTIZED RUNNING TIME. Count 1 step for each bit flip. * What is the worst case time to add 1 to an n-bit binary number? ANSWER: n+1 <- n -> * Assuming that you start with the n-bit number 0 = 0 0... 0, what is the amortized time to perform a sequence of m "ADD 1" operations to this n-bit binary number? ANSWER: 2m * Assuming that you start with the n-bit number 0 = 00...0, as above, what is the amortized time to perform a sequence of m, m < 2^n, "ADD 1" and "SUBTRACT 1" operations to an n-bit binary number? As usual, count 1 step for each bit flip. ANSWER: mn