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

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.