Last update: August 5, 2:45PM.

Warning: Do not slack off yet! This is a hard assignment. Start now.

Note: You are responsible for reading and understanding the course policy on academic integrity.

1. Counting path-lengths as the number of vertices in the path:
   1. Describe an undirected graph with n vertices and n-1 edges such that that the (shortest-path) distance between any two vertices is at most 3.
   2. Describe an undirected graph with n vertices and n-1 edges such that the (shortest-path) distance between any two vertices is less than or equal to 2log n and no vertex has degree greater than 3.
   3. Describe a strongly-connected directed graph with n vertices that has as few edges as possible.
   4. Describe a dag with n vertices and as many edges as possible.
   
   
   
2. Let G be an undirected graph with vertices 1,2,...,n and a total of m edges. Let k be a constant. Let G'  be defined as follows:
   • It has vertices 1,2,...,i and all the edges between them.
   • No connected component in G'  has more than n/k edges.
   • If we added vertex (i+1) and the edges between it and lower-numbered vertices, then there would be a connected component with more than n/k edges.
   Clearly, there is exactly one value of i that correctly defines G' . We want an algorithm that finds this i.
   1. Describe a straightforward algorithm that runs in time Theta((n+m)n).
   2. Give a better algorithm that runs in time Theta((n+m)log n).
   3. Give a better algorithm that runs in time O((n+m)log^*n).
   
   
   
3. Let us define "collapsing" a directed graph G into a directed graph G' as follows:
   • The vertices of G' are the strongly-connected components of G.
   • Let v₁ and v₂ be vertices of G' representing sets of vertices s₁ and s₂ in G respectively. Then (v₁, v₂) is an edge in G' if and only if there exist some u in s₁ and w in s₂, such that (u,w) is an edge in G.
   Assume G has n vertices and m edges.
   1. Let collapse be a function which collapses a graph. Prove that for all graphs G, no strongly-connected component in collapse(G) has more than one vertex. What do we call such graphs?
   2. Argue that collapse can run in time O(n+m).
   3. Give an algorithm to find a forest over G (each vertex is in exactly one tree of the forest) that has as few trees as possible. Total running time should be O(n+m).
   
   
   
4. CLR Exercise 24.2-6, page 510.
   
   
5. CLR Exercise 25.2-5, page 532.