Homework 5 (due 5/12)
CSC 321



We talked about Minimum Spanning Tree Algorithms, Kruskal (Section 7.2), Prim (Section 7.3), and Boruvka (the wikipedia article Boruvka's Algorithm is a good starting point and has some history too). We discussed greedy methods (Introduction to Chapter 7), and saw one more greedy algorithm: Dijkstra's algorithm (which is very similar to Prim's) solving the single-source shortest path problem (Section 7.4). We also saw a linear-time solution for the single-source shortest path problem for dags (see NIST's description). That algorithm, together with the Fibonacci number algorithm, are the first simple examples of a dynamoc programming solution, a technique we will start exploring in depth next week (Chapter 8).



Submission
: Submit to the d2l dropbox. Use some standard format for your homework (Word or pdf, for example), and make sure to include your name and assignment number. Include screenshots for code and testruns. You do not need to include the code (or any executables).

1. (Reading Assignment) Read Sections 7.2, 7.3, 7.4, 8.1.

2. [Topological Sort, 10pt] Implement a topological sort (using the method in the book) which given a graph G = (V,E) returns an ordering of the vertices, which is consistent with the dependencies specified in E. Use it to sort the graphs in DAG.txt. Note that the graph is directed, so it's possible that E[1] = [2,5], but E[2] doesn't contain 1 (indeed, it can't, otherwise G would not be an acyclic graph). Show the results of your testruns on the graphs (for the larger graphs, just include the first and last couple of vertices in the linear order).

3. [Shortest Path, 10pt]  We saw an algorithm in class which, given a dag G = (V,E) with weights weight(u,v) for edge (u,v) and a vertex s of G, finds the shortest path from s to every vertex in G in time O(|E|). It proceeded by first topologically sorting G wth respect to E, and then calculating

dist[v[i]] = min[ dist[v[j] + weight(v[i],v[j]): (v[i],v[j]) is an edge in E]. 

We want to illustrate that algorithm, by performing it for

G = ([0,1,2,3,4,5], {0: {2:9}, 1: {2:5}, 2:{}, 3: {2:2}, 4:{0:3, 5: 2}, 5:{0:3, 3: 7, 6:4}, 6:{1:1, 3:2}})

This is an encoding of a weighted graph: e.g. 0 has an edge to 2 with weight 9, and 4 has edges to 0 (weight 3), and 5 (weight 2). This is a standard way of encoding a weighted graph.

a) [2pt] Draw G (with directed edges and weights)

b) [3pt] Topologically sort the vertices of G, and redraw G so that its vertices are on a line, and edges are directed from left to right.

c) [5pt] Perform (by hand), the shortest path calculation. For each vertex v of G, clearly indicate what the length of the shortest path from s to v is, where s is the leftmost vertex of G.

4. (Critical Path, 10pt) You are given a dag G = (V,E) which encodes dependencies between various projects, i.e. an edge a -> b in the graph means that a requires b, so b must precede a. If you want a concrete example, imagine course prerequisites (e.g., see this computer science prereq graph). A crititical path in such a graph is a longest directed path (e.g. in the example above, CS 4471, CS 4411, CS 3331, CS 1141, CS 1122, CS 1121). The length of a critical path is a lower bound on how quickly a project can be finished (in the example, you need at least 6 semesters to complete the degree).

a) [3pt] Suppose you have an algorithm which finds the longest path between two vertices s and t in a given graph H = (V', E') in time O(|E'|). Explain how you can use that algorithm to find a critical path in a graph G = (V,E) im time O(|E|). Hint: show how to construct H = (V', E') from G which encodes the solution.

b) [7pt] Explain (pseudo-code, or high-level explanation) how you can find the longest path between two vertices s and t in a given dag. Hint: Do problem 3 before you do this problem

This solves the critical path problem.

5. [Breadth-First Search, 10pt] Two vertices in a graph are said to be at distance k if the shortest (simple) path between them has length k. So two adjacent (neighboring) vertices are at distance 1. Two vertices that have a common neighbor but no edge between them are at distance 2, and so on. You want to write an algorithm that given a tree T = (V,E) finds two vertices in the tree that have maximal distance from each other and runs in time O(|V|). You don't have to implement this (or write pseudo-code), just give a high-level description. Hint: Since T is a tree, |E| = |V|-1, so O(|V|) gives you enough time to look at the whole input. Note the category this question is in. A straight-forward approach would give O(|V| |E|), but since T is a tree, you can do much better.

6. (Extra Credit, 15pt)  Implement a solution to problem 4, that is, write an algorithm, which as input takes a directed acyclic graph G and returns a critical path and its length. Prove that your algorithm works, by running it on the  computer science prereq graph, you can download the Python version of that graph. (I've removed corequisites, and interpreted alternative prerequisites as both courses being required to simplify the situation).


Marcus Schaefer
Last updated: May 4th, 2015.