Carnegie Mellon University School of Computer Science Final Exam in CS15-750: Algorithms and Data Structures Date: Friday 9 May 2003 Instructor: Manuel Blum Teaching Assistant: Ryan Williams * This is a closed book examination: While calculators ARE allowed, NO books, NO laptops, NO scratch paper are permitted. * Do all your work including scratch work on the pages of this exam. * This exam has 11 problems worth a total of 61 pts. * All arguments in quotes are questionable. If you believe a given answer but not the argument, then check that answer and extend, correct or replace the given argument. * Check as many answers as are correct. It may happen that no answer is correct. * If none of the given answers are correct, then insert your own correct answer. (1 pt) Your name:______________________, __________________________ FAMILY (LAST) GIVEN (FIRST) Your signature:_____________________________________________ Your email address:_________________________________________ (2 pts) 1. Meld the following two Binomial heaps into a single Binomial heap: min \ Heap 1 = 2* 1* 4* | |\ 3* 5* *6 | *7 min \ Heap 2 = NIL 8* NIL | 9* Meld of 1 and 2 = (20 pts total -- 2 pts each) 2. Which of the following operations are supported by A = (classical) Binary Heaps. B = Binomial Heaps. C = Fibonacci Heaps. Answer here: heapify(a1,...,an) = create a heap on a given set of n elements in O(n) steps. ____ makeheap(a) = create a heap on 1 element in O(1) steps. ____ insert(a,H) = insert element a to heap H in O(1) amortized steps. ____ insert(a,H) = insert element a to heap H in O(lg n) steps. ____ deletemin(H) = delete the minimum element of heap H in O(1) steps. ____ deletemin(H) = delete the minimum element from heap H in O(1) amortized steps. ____ deletemin(H) = delete the minimum element from heap H in O(lg n) amortized steps. ____ meld(H1,H2) = combine heaps H1 and H2 into one heap in O(lg n) amortized steps. ____ delete(a,H) = remove element a from heap H in O(lg n) amortized steps. ____ decrement(a,,H) = decrease the value of the element a in H by amount  in amortized O(1) steps. ____ (2 pts) 3. Do splay(1,T) on the Splay Tree T = 4* / \ (Do not ask the exam proctor what a 2* *5 splay tree is or how to solve this / \ problem: you are supposed to know.) 1* *3 (2 pts) 4. The elements 0,1,2,3,4,5,6,7,8,9 have the following priorities: 3 1 4 5 9 2 6 8 7 0. This means that 3 has highest priority and 0 has lowest priority. Construct the treap having these elements with these priorities. (4 pts) 5.Toss n balls uniformly at random into n cells. Q. What is the expected number of empty cells? Answer(s) should be correct asymptotically as n -> infinity. Circle correct answers. Cross out incorrect answers. A1. n/e "The probability that a given cell is empty is (1-1/n)^n ~ 1/e, so the expected number of empty cells is asymptotically n/e." A2. n/(ln n) "By the coupon collectors problem, n(ln n) balls is needed to put a ball in each of n cells. So if only n balls are tossed, the number of empty cells will be n/(ln n)." Q. What is the expected number of cells that contain exactly one ball? A.Select one: n/e ___. n/e^2 ___. n/(ln n) ___. other:____ Q. What is the expected number of cells that contain 2 or more balls? A1. Asymptotic to something less than n/e. A2. n/e. A3. More than the number of cells that contain 0 or 1 ball(s). (4 pts) 6.Cover time: Recall that cover time is defined to be the expected number of steps to visit every vertex at least once, starting from the "worst-case" vertex for which this time is largest. Q. What is the cover time for a random walk on the undirected circle of n nodes: Circle = 1 -- 2 / \ n 3 \ / .... A1. O(n) "It takes 10*n steps to walk completely around the circle ten times, which is more than enough time to cover the circle once." A2. O(n*ln n) "One must toss expected O(n*ln n) balls to get a ball in each of n bins. A random walk on a circle is essentially equivalent to tossing balls into bins." A3. O(n^2) "For u,v at opposite ends of the circle, the commute time is Cuv = O(n^2)." A4. O(n^3) "The cover time for any undirected graph is O(n^3)". (4 pts) 7. T or F: Every finite planar graph G = with no self- loops and no multiple edges between the same two nodes has at least one vertex of degree at most 5. T "This is a consequence of an Euler theorem: V-E+F=2 for planar connected graphs." F "A typical hexagonal pattern of kitchen tiles -- viewed as the nodes of a graph -- leads one to infer that one can draw a planar graph on a sphere -- the earth -- so that every node has degree 6. In this graph, the nodes correspond to hexagons. Two nodes are adjacent (joined by an edge) if the corresponding hexagons share an edge:" _ _ _ \|/ \|/ \|/ _/ \_/ \_/ \ * * * Kitchen / \_/ \_/ \_/ corres- \|/|\|/|\|/|\ tile = \_/ \_/ \_/ \ ponding = * | * | * | floor / \_/ \_/ \_/ graph /|\|/|\|/|\|/ \_/ \_/ \_/ | * | * | * \|/|\|/|\|/|\ * * * /|\ /|\ /|\ (4 pts) 8. Can every degree 3 graph (ie. a graph whose vertices all have degree 3) be properly 4-colored? No. "By the 4-color theorem, all planar graphs can be properly 4-colored but non-planar graphs in general need more colors and there exist non-planar degree 3 graphs." Yes. "Every graph of degree 3 is planar, and every planar graph can be properly 4-colored." (10 pts) 9. A Tournament Graph problem: Recall that a Tournament Graph (TG) is a directed graph with n_choose_2 = n(n-1)/2 edges such that for every pair of distinct vertices i,j, exactly one of and is in E. Q. Is there an efficient algorithm to decide if a TG has a Hamilton Cycle (HC)? A1. NO. "The Hamilton Cycle Problem is NP-hard, so there is no known algorithm to decide efficiently if a graph has a HC." A2. YES. "The following algorithm (possibly slightly modified) decides HC of any given TG in poly(n+m) time." ALGORITHM In O(n+m) time, check if there is a vertex of in-degree (or out-degree) 0. If so, return `NO HC'. Else Construct a cycle C = v1 ->v2 -> ... ->v1. Until C is a HC, do: For arbitrary vertex v not in C, look for two successive vertices vi,vi+1 in C such that vi -> v and v -> vi+1. If none such exist, return `NO HC'. Else extend C to include v. Return C. A3. YES. "The above algorithm (possibly slightly modified) decides if a given TG has an HC in O(n+m) time." (4 pts) 10. We did a problem like this in class, but watch out as this one is (slightly) different: n people each have a random bit on their forehead. Each can see the bits on everyone else's forehead but not on their own. Each has to guess the bit on his own forehead. Q. Is there a randomizing algorithm that takes as input the bits on everyone's forehead except one's own and outputs one's own bit with a better than 50% chance of guessing that bit correctly? Equivalently, can you improve your chances of success by looking at the bits around you? A1. NO "Your own bit is independent of the bits around you, so no matter how you guess, the probability that you guess your own bit correctly is 1/2." A2. YES "If you see more 1's than 0's then you should guess that your own bit is 0 as the expected excess of 1's over 0's is 0. A3. YES "If you see more 1's than 0's, then you should guess that your own bit is 1 as this will ensure that more people guess correctly than not. A4. YES "but the correct algorithm depends on n. (4 pts) 11. Recall that f(n) ~ g(n) iff lim f(n)/g(n) = 1. n -> infinity Q. Is (1 - 1/n)^(n ln n) ~ 1/n ? YES "(1 - 1/n)^n ~ 1/e so (1 - 1/n)^n(ln n) ~ 1/e^(ln n) ~ 1/n" NO "Even if f(n) ~ g(n), there is no guarantee that f(n)^(ln n) ~ g(n)^(ln n). For example, 1 ~ 1 - 1/(ln n), but 1^(ln n) NOT ~ (1 - 1/(ln n))^(ln n) since 1^(ln n) ~ 1 while (1 - 1/(ln n))^(ln n) ~ 1/e."