The assignment below consists of three parts, one for each lecture. For each part, the maximum possible score has been indicated. Each part consists of a number of exercises and the maximum possible score has been indicated for each of them.
Here is the correspondence between grades and scores:
Grade 3 (pass): 40 <= score < 60
Grade 4 (good): 60 <= score < 80
Grade 5 (very good): 80 <= score <= 100
Part 1: Fully-dynamic graph connectivity (40 points):
----------------------------------------------------
Give a description of the deterministic data structure as pseudo-code. (10 points)
Give the main ideas in the proof of the O((log n)^2) amortized update time bound and the O(log n) worst-case query time bound. You do not need to cover all details but as a minimum, you should explain the invariant and why it is not violated during edge level increases, explain how local trees are updated after a merge or split (figures would be nice), and explain why searching in parallel (when looking for a replacement edge at a given level) is important for the analysis. (18 points)
Explain how the XOR trick that we covered in the last part of the lecture works. (5 points)
Assuming no random sampling is used: when a tree edge is deleted, what is required of the resulting cut for the XOR trick to work to determine a replacement edge (or to determine that no replacement edge exists) and why is this required? (5 points)
Explain the rough idea of how to get rid of this assumption using random sampling. (2 points)
Part 2: Fully-dynamic all-pairs shortest paths (20 points):
----------------------------------------------------------
What do pebbles from the pebble lemma correspond to (.i.e., what do they measure) in the analysis of the data structure? Give the rough idea of why minimizing the maximum number of pebbles in any pile leads to a good worst-case running time. (15 points)
Is the final O~(n^{2+2/3}) fully-dynamic data structure able to handle an adaptive adversary? (as defined in the slides) Explain your answer. (5 points)
Part 3: Decremental (1+epsilon)-approximate single-source shortest paths (40 points):
------------------------------------------------------------------------------------
Explain how the standard data structure of Even and Shiloach works and argue why its time bound is O(mD) for handling distances up to D. (8 points)
Explain the weight function that we covered, how the modified data structure of Even and Shiloach works for this weight function, and give the running time analysis (expressed as a function of the max weights of the individual edges) of this modified data structure when maintaining (weighted) distances up to D. (12 points)
Which edge weights are chosen for a DAG (directed acyclic graph)? With these weights, sketch how to get the O~(n^2/epsilon) bound on the total running time for maintaining (1+epsilon)-approximate single-source shortest path distances in an n-vertex DAG undergoing edge deletions. (20 points)