**Unformatted text preview:**

CS369B: Problem Set #1Due in class on Thursday, January 24, 2008Instructions:(0) Warning: Budget a lot of time for this problem set.(1) Students taking the course for a letter grade should attempt 4 of the following 5 problems; those takingthe course pass-fail should attempt 2 of them.(2) Some of these problems are quite difficult. I highly encourage you to start on them early and discussthem extensively with your fellow students. If you don’t solve a problem to completion, write up whatyou’ve got: partial proofs, lemmas, high-level ideas, counterexamples, and so on. This is not an IQtest; we’re just looking for evidence that you’ve thought long and hard about the material.(3) You may refer to your course notes, and to the textbooks and research papers listed on the courseWeb page only. You cannot refer to te xtbooks, handouts, or research papers that are not listed on thecourse home page.(4) Collaboration on this homework is strongly encouraged. However, your write-up must be your own,and you must list the names of your collaborators on the front page.(5) No late assignments will be accepted.Problem 1Fibonacci heaps.(a) Unlike normal heaps or binomial heaps, Fibonacci heaps can include trees that are very deep. Provethis by giving a sequence of operations for a Fibonacci heap with n elements such that the depth ofone of its trees is Ω(n).[Hint: induction on n.](b) Suppose we modify Fibonacci heaps so that we only rip out a node if k of its children have already beenripp e d out. Intuitively, this should speed up (the constant factors of) the amortized time bound forDecrease Key, since there will be fewer cascading cuts, and slow down Extract Min, since the trees canget more scraggly. Try to quantify how the amortized bound for Extract Min degrades as a functionof k.Problem 2Matroids. A matroid is given by a ground set E of elements and a collection I of subsets of E, calledindependent sets, satisfying three properties:(i) ∅ ∈ I;(ii) I is closed under subsets: if S ⊆ T and T ∈ I, S ∈ I;(iii) the Excha nge Property: if S, T ∈ I and |S| > |T|, then T can be extended by some element of S \ T :there is an element e ∈ S \ T such that T ∪ {e} ∈ I.1A basis of a matroid is a maximal independent set. A cycle is a minimal dependent set (i.e., all of its propersubsets are in I). A cut is a minimal subset that intersects every basis.(a) [Do not hand in.] Convince yourself that all bases of a matroid have the same cardinality. This iscalled the rank of the matroid.(b) [Do not hand in.] Let I denote the acyclic subgraphs of an undirected connected graph. Convinceyourself that this is a matroid, the bases are the spanning trees of the graph, and cuts and cycles ofthe matroid correspond to cuts and cycles of the graph.(c) Let M be an arbitrary matroid and assign distinct real-valued costs to its elements. Prove the CutProperty: for every cut S of M, the cheapest ele ment of S belongs to every minimum-cost basis of M.(d) Let M be an arbitrary matroid and assign distinct real-valued costs to its elements. Prove the CycleProperty: for every cycle S of M , the costliest element of S belongs to no minimum-cost basis of M.(e) [Do not hand in.] Let M be an arbitrary matroid and assign distinct real-valued costs to its elements.Define the greedy algorithm for computing a minimum-cost basis of M as in Kruskal’s MST algorithm:start with S = ∅; go through the ele ments of M in order from cheapest to costliest, in each iterationadding the current element to the set S if and only if doing s o preserves independence. Convince yourselfthat the correctness proof for Kruskal’s algorithm remains valid in this general matroid context.(f) Consider a ground set E and a collection J of subsets of E that satisfies the first two defining propertiesof a matroid but not the third. Prove that there exists an assignment of costs to the elements E suchthat the greedy algorithm fails to output the minimum-cost subset in J .Problem 3An O(m log log n)-Time Implementation of Bor ˙uvka’s Algorithm.(a) Suppose as a preprocessing step, we sort the edges in each node’s adjacency list by cost. (This takesO(m log n) time.) Show how to implement the rest of Bor ˙uvka’s algorithm to run in time O(m+n log n).[Hint: It might help to implement contractions only implicitly. Have each node of the original graphkeep track of which edges in its adjacency list are useless, in that they point to a different node in thesame connected component of the tree-so-far. Keep the potentially useful ones sorted by c ost. Canyou achieve a bound of O(n) per phase, plus O(m) additional time overall to maintain the adjacencylists?](b) Call an array partially sorted with parameter k if every element is less than k positions away from itsrightful position in the s orted version of the array. (k = 1 is fully sorted, k = n is unsorted.) Showhow to k-partially sort an array of n numbers in O(n lognk) time.[Hint: linear-time median.](c) Strengthening the result in (a), show that O(m log log n) preprocessing time for partial sorting is enoughto obtain a bound of O(m + n log n) for the rest of the work done by Bor ˙uvka’s algorithm.(d) Explain why performing log log n Bor ˙uvka phases prior to your algorithm in (c) yields an O(m log log n)MST algorithm (including all preprocess ing steps).Problem 4MSTs and Shortest-Path Trees: The Best of Both Worlds. Our first two topics are minimum-spanning trees and shortest-path trees. But what if we want a single tree possessing the good properties ofboth? Consider an undirected graph G = (V, E) with distinct and nonnegative edge lengths and a sourcevertex s.2(a) Show that the s hortest-path tree rooted at s can be an extremely bad approximation of the MST (interms of the sum of the lengths of the edges in the tree). How big a gap can you obtain? (You shouldgive a family of examples such that, as the number of nodes n goes to infinity, the total edge cos t ofthe shortest-path tree is f(n) times the MST cost, where f (n) is as large a function as possible.)(b) Conversely, show that the MST T can be a bad approximation of the shortest-path tree, in that therecan be vertices v such that the s-v path in T has length much larger than that of a shortest such pathin G. How big a gap can you obtain?(c) Prove that there always exists a tree that simultaneously O(1)-approximates the cost of an MST andalso O(1)-approximates shortest-path distances from s to all other vertices. What kind of

View Full Document