$30.00
Description
Problem 1 (Prim’s and Kruskal’s algorithms – 10 points) Suppose we want to the find a minimum spanning tree of the following graph:
G
4
C
9
B
3
2
A
D
6
8
5
7
E
F
1

Run Prim’s algorithm starting from node A. Fill in the following table showing the intermediate values of the cost array.

initially
dequeue A
dequeue
dequeue
dequeue
dequeue
dequeue
dequeue
A
0,nil
B
∞,nil
C
∞,nil
D
∞,nil
E
∞,nil
F
∞,nil
G
∞,nil
Draw the resulting minimum spanning tree.
G
B
C
A
D
E
F

Run Kruskal’s algorithm on the same graph. First, show your sorted list of the edges. As the algorithm proceeds, show how the disjointsets data structure looks at every intermediate stage (includes both the current rank values and the current parent pointers). Do not perform path compression. The nodes of the trees are given below.
List of edges:
Initially:
A
B
C
D
E
F
G
Add edge _____:
A
B
C
D
E
F
G
Add edge _____:
A
B
C
D
E
F
G
Add edge _____:
A
B
C
D
E
F
G
Add edge _____:
A
B
C
D
E
F
G
A
B
E
D
F
C
Add edge _____:
A
B
C
D
E
F
G
Add edge _____:
A
B
C
D
E
F
G
K
L
2. (Kruskal’s algorithm – 3 points) Suppose that we are running Kruskal’s algorithm on a weighted, undirected graph and that the following directed tree exists in the supporting data structure (assume F has a loop pointing back to F):
Which node is returned by find(I)?
A
E
D
F
A
E
D
F
Draw the tree structure that results from performing find(I). Use the version of find that does path compression.
3. (Horn formulas – 6 points)
 Trace the algorithm from Section 5.3 on the following Horn formula, indicating which variables are set to true in which order:
a b d
d e g
e
e a
b
d g
Algorithm trace:
Is the formula satisfiable?
If it is satisfiable, what is the minimum satisfying assignment?
 Repeat the above problem for the Horn formula:
a b d
d e g
e
a e
b
d g
Algorithm trace:
Is the formula satisfiable?
If it is satisfiable, what is the minimum satisfying assignment?
4. (Set cover – 6 points)
Consider the following diagram taken from http://en.wikipedia.org/wiki/Set_cover_problem:
If we label the dots along the top row as a_{1},…,a_{7} and the dots along the bottom row as b_{1},…b_{7}, then the diagram corresponds to the following set cover problem:
Cover {a_{1},…,a_{7}, b_{1},…b_{7}} with the following subsets:
S_{1} = {a_{1},…,a_{7}}
S_{2} = {b_{1},…,b_{7}}
S_{3} = {a_{1},b_{1}}
S_{4} = {a_{2},a_{3},b_{2},b_{3}}
S_{5} = {a_{4},a_{5},a_{6},a_{7},b_{4},b_{5},b_{6},b_{7}}
(a) Recall the following notation: “Let n_{t} be the number of elements still not covered after t iterations of the greedy algorithm (so n_{0} = n).” Trace the greedy algorithm by listing the successive values of n_{t} and the subset S_{i} chosen at each step. How many subsets does the greedy algorithm choose?
(b) What is the optimal set cover for this problem instance?
(c) Extend the above diagram to one with 2^{4}1 = 15 dots along the top row and 15 dots along the bottom row. Using a similar pattern of subsets, we can have S_{1} = S_{2} = 15; S_{3},..,S_{5} as before; and a new subset S_{6} added on the far right with S_{6} = 16. The greedy algorithm yields a rather high (that is, poor) approximation factor on this instance. How large is the set cover that is selected by the greedy algorithm, and how large is the optimal set cover?
(d) Now extend this pattern to one with 2^{n}1 dots along the top row and 2^{n}1 dots along the bottom row. How large is the set cover that is selected by the greedy algorithm? How large is the optimal set cover?