Algorithms II supervisions (2008–2009)

The course webpage contains links to the syllabus, past tripos questions, lecture notes and Frank’s signature “microchallenges”.

Please make sure that your work reaches my inbox at least 24 hours before the supervision, either by email or paper-based via the post box outside Student Administration in the William Gates Building.

First Supervision [70]

  1. Show how to implement a FIFO queue and a stack using a priority queue. [2]
  2. Give an O(lg n) implementation of Heap-Delete(A, i) which deletes node i from a binary heap A. [4]
  3. Building a binomial heap (from sratch). Outline the following operations and draw the heap after each operation.
    1. Insert keys 10, 3, 7, 20, 17, 25, 5, 14 in that order. [4]
    2. Run decreaseKey(25, 4). [2]
    3. Insert keys 8, 13, 19, 16 in that order. [2]
    4. Run extractMin(). [2]
  4. Discuss the relationship between inserting into a binomial heap and incrementing a binary number, and merging two binomial heaps and adding two binary numbers. [2]
  5. A sequence of n operations is carried out on a data structure. The ith operation costs i if iis an exact power of 2, and 1 otherwise.
    1. Use aggregate analysis to determine the amortised cost per operation. [4]
    2. Use the potential method to determine the amortised cost per operation. [8]
  6. Implement a Fibonacci heap in a programming language of your choice, including all operations listed in the lecture notes. [20]
  7. Using your implementation, or otherwise, carry out the following operations on an empty Fibonacci heap and draw the heap after each operation.
    1. Insert keys 10, 3, 7, 20, 17, 25, 5, 14, 8 in that order. [2]
    2. Extract the minimum item. [2]
    3. Decrease the key of 17 to 2. [2]
    4. Delete item 10. [2]
    5. Merge with the heap constructed by inserting 12, 6, 21, 13, 4, 1 in that order. [2]
    6. Extract the minimum item. [2]
  8. Provide pseudo-code for the disjoint set operations makeSet(x), findSet(x) and union(x,y) using both list and forest implementation, including “union by rank” and “path compression” heuristics. [8]

Second Supervision [80]

Elementary graph algorithms (chapter 22 in Cormen et al.):

  1. 2001 Paper 6 Question 1 [20]
  2. When would you represent a graph using an adjacency list and when using an adjacency matrix? What is their memory requirement for (un)directed graphs? [4]
  3. What is a topological sort of a dag? Outline an algorithm for computing a topological sort. [4]

Minimum spanning trees (chapter 23 in Cormen et al.):

  1. 2000 Paper 4 Question 6 [20]
  2. Show that if (u, v) is contained in some minimum spanning tree, then it is a light edge (the edge of minimum weight) crossing some cut of the graph. [2]
  3. Is the Fibonacci-heap implementation of Prim’s algorithm asymptotically faster than the binary-heap implementation for a sparse graph G = (V, E), where |E| = Θ(V)? What about for a dense graph, where |E| = Θ(V2)? How must |E| and |V| be related for the Fibonacci-heap implementation to be asymptotically faster than the binary-heap implementation? [4]

Single-Source Shortest Path (chapter 24 in Cormen et al.):

  1. 2006 Paper 5 Question 1 [20]
  2. Provide a pseudo-code implementation of the Bellman-Ford algorithm and derive its time complexity. [6]

Third Supervision [80]

Shortest paths between any two vertices (chapter 25 in Cormen et al.):

  1. 2008 Paper 4 Question 2 Parts (b)–(d) [16]
  2. 2005 Paper 5 Question 1 Part (d) [8]
  3. Suppose that w(u, v) ≥ 0 for all edges (u, v) ∈ E. What is the relationship between w and ŵ (w hat)? [2]

Maximum flow (chapter 26 in Cormen et al.):

  1. 2007 Paper 4 Question 9 [20]
  2. Prove that if f1 and f2 are flows of the same graph, then so is α · f1 + (1 − α) · f2 for all α in the range 0 ≤ α ≤ 1. [4]
  3. Show that a maximum flow in a network can always be found by a sequence of at most |E| augmenting paths. [2]

Geometric algorithms (chapter 33 in Cormen et al.):

  1. 2004 Paper 6 Question 1 [20]
  2. Prove that if p1 × p2 is positive, then vector p1 is clockwise from vector p2 relative to the origin (0, 0). [4]
  3. Prove that the pair of points with maximum distance lies on the convex hull of a point set. [4]