hw4

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

hw4

Problem 1. Path FH.

We'll say a Fibonacci heap is a path if it has size n and height n-1. A path has a single root, and every node has at most one child.

(a) For n≥1, show it is possible for a Fibonacci heap to be a path of size n, with all nodes marked. That is, describe a sequence of operations creating such a heap. You might present your construction inductively (base case, and then how to get from n to n+1). Include some diagrams.

(b) Argue that in any path of size n, at least n-2 of the nodes have lost a child. (Some nodes might not be marked, so do not assume it was created by the sequence of operations you proposed in (a).)

Reminder: CascadingCut does not mark a root when it loses a child.

Problem 2. Modified FH.

Suppose we modify the Fibonacci Heap H so that it keeps track of t(H) (say in a field, H.t). At the end of any operation where t(H) might increase, we check whether it is at least 2(D(n)+1). If so, we do Consolidate(H).

(a) Which Fibonacci heap operations do we need to modify?

(b) When t(H)≥2(D(n)+1), argue that the amortized cost of Consolidate(H) is at most 0. (Recall our potential function is really s·Φ(H), where s is a "large enough" constant. You may need to modify the choice of s to make this work out.)

(c) In this modified Fibonacci heap, argue the worst-case cost of ExtractMin is now O(lg n), rather than O(n).

(d) In this modified Fibonacci heap, argue there is still some operation with worst-case cost Ω(n). (Hint: use the previous problem.)

Remark: as a consequence of (b), we don't increase the amortized cost of the operations in (a).

Problem 3. Exercise 22.3-9 (pages 625-626). In this exercise you modify Dijkstra's algorithm to run in time O(E+VW), when all the edge weights are integers in the range 0 to W. (Main idea: all finite distance labels will be integers less than VW, replace the priority queue.)

Problem 4. Exercise 23.2-9 (page 662). Do this exercise on computing the transitive closure.

Hint: use the result from CS-253 or Section 20.5, that we can compute the strongly connected components of a digraph in O(V+E) time. Furthermore, the component graph (GSCC of pages 576-577) is a DAG.

Problem 5 (Floyd-Warshall with negative cycles). Suppose we run Floyd-Warshall (see Ch23.Floyd- Warshall.png (https://canvas.emory.edu/courses/136148/files/12319528)) in a graph with n vertices, which may have negative cycles. It returns a final distance matrix D = (dij) = D(n) .

(a) Argue that if G has a negative cycle, then it has a simple negative cycle (that is, a cycle with no repeated vertices).

(b) Argue that for every simple negative cycle, there is at least one vertex v on the cycle with dvv < 0.

(c) Present an algorithm which modifies D in O(n3) additional time, so that for every pair of vertices i and  j (possibly i=j): if there is a negative cycle on a path from i to j, then we set dij=-∞ . Otherwise, dij  is correct and left unmodified. Present your algorithm to modify D, argue its running time, and say a few sentences about its correctness, i.e. how does it find all the dij which need to be modified.