Due Wednesday 19 April 11:59pm (automatic extension for a couple of hours as it won't get looked at until Thursday morning....)
Dijkstra's Algorithm
Read about Dijkstra's Algorithm (Cormen p. 595, but you will probably want to read pp. 580-587 as well). Answer the following questions:
Dijkstra's algorithm is called a single source shortest path algorithm. Explain what this means.
For each vertex in the graph, Dijkstra's algorithm keeps track of two values. (Cormen calls these d and pi, but they may have different names if you look them up in another source.) What does each of these values represent, i.e., what information does each one track?
Run Dijkstra's algorithm on the following graph beginning from vertex A, tracking the d and pi values for each vertex at each step. (Your answer might look like Cormen Figure 24.6 on p. 596, but with a different graph.) The graph has seven vertices, {A, ... G}. In the following table, the number in row x and column y represents a weighted, directed edge from x to y; e.g., there is an edge from A to B of weight 7.
A
B
C
D
E
F
G
A
7
3
5
B
5
C
5
1
1
D
2
E
F
2
G
8
NP completeness
- Explain what it means to prove a that a problem is NP-complete. In particular,
- explain how you can prove that a problem is NP-hard (i.e., at least as hard as any problem in NP); and
- explain how you can prove that a problem is in NP (i.e., no harder than NP).
Consider the problem DOUBLE-SAT = { <F> | F is a propositional formula with at least two satisfying assignments}. Show that DOUBLE-SAT is NP-complete:
Imagine that you have an oracle that can solve any DOUBLE-SAT problem. Show how you can use this oracle to solve an arbitrary SAT(ordinary propositional satisfiability) problem in polynomial time. (Alternately, you may use the DOUBLE-SAT oracle to solve an arbitrary instance of CNF-SAT or 3-SAT if you prefer.)
What does this show, i.e., what does it prove that you can use a DOUBLE-SAT solver to solve SAT (or CNF-SAT or 3-SAT)?
What else do you need to show to prove that DOUBLE-SAT is NP-complete?
Complete the proof that DOUBLE-SAT is NP-complete.
Union-Find
Read the description of the fast disjoint set algorithm in Cormen p. 508. (You will probably want to read pp. 408-501 and section 21.3 as well as the code itself.) You may also find this data structure/algorithm described elsewhere as an Up-Tree or Union-Find.
- Draw the data structure(s) created by the following code. Include the rank estimate for each node:
for i <- 1 to 16 do MAKE-SET(X_i)
- Show the same data structure(s) after executing the following code on the previous result:
for i <- 1 to 15 by 2 do UNION(X,_i, X_i+1)
- Show the same data structure(s) after executing the following code on the previous result:
for i <- 1 to 13 by 4 do UNION(X_i, X_i+2)
- Show the same data structure(s) after each of the following five lines. You may assume that they are executed in order after the previous step. Be sure to preserve rank estimates.
UNION(X_1, X_5)
UNION(X_11, X_13)
UNION(X_1, X_10)
FIND-SET(X_2)
FIND-SET(X_9)
Project Assignment (3520a students only)
Project assignment 5 is to identify a source of graph data (e.g., Friendster, Amazon, GoogleMaps) and write some code to manipulate it. For example, you might play Six Degrees of Separation with FOAF data; find a the four books most likely to have been co-purchased by the buyer of any individual Amazon book; attempt to solve the Traveling Salesman Problem for Needham; etc.
This is the final project assignment for the semester, so it need not be turned in until Monday 1 May.
Also, you should plan to put at least one assignment from FOCS Project into your portfolio. Now would be a reasonable time to investigate the portfolio system (if you haven't already) and to select an assignment for inclusion. That way, if you want to tweak it a bit more before you put it in, you have some time. (You are welcome to include more than one assignment, of course!)