Homework 8 Solution

Problem 1: Consider the shortest reliable paths problem on the following graph:




6









B
-3
C


6










-4
A
9


8






-5



8
6





D
7
E







Assume that A is the starting vertex and k = 3. Fill in a matrix of distance values using the algorithm from slide 2322 of the Chapter 6 notes (which is the same algorithm as discussed in the textbook). What is the shortest (i.e. least cost) path from A to E that uses no more than 3 edges?







Problem 2: Download TSPtrace.pdf from Canvas. Fill in the rest of the matrix. Assume that we start from vertex A. What is the a least cost tour of the graph? Specify both the tour and its cost.

Problem 3: Suppose we want to find the largest independent set in the following tree:



















A







B C D










E F G H I J K










L M N O P










The recurrence relation covered in the textbook and in class was:




I(u) = max{1 + ∑{I(w) : w is a grandchild of u},

∑{I(w) : w is a child of u} }




Treat A as the root of the tree and clearly label each node with its I-value. What is the independent set that is found by the dynamic programming algorithm?







The directions for the next two problems are the same as you saw on Homework #7: “Do the following exercises from Chapter 6. For each problem define the relevant recurrence relation, along with any relevant base cases. Also write down the top-level recurrence relation instance that needs to be solved. You do not need to write pseudocode for the resulting algorithm. You can see quite a few examples worked if you look at Chapt6Solns.pdf, which is on Blackboard under Course Notes-Chapter6. Please write up your solutions similar to the way those example solutions are written.”




6.21 Hint: Think of the tree as being rooted at a particular node t0. If t is a node in this rooted tree, then let children(t) be the children of t. Then define C(t,true) = the size of the smallest vertex cover of the subtree rooted at t, assuming that t is part of the vertex cover. Also let C(t,false) = the size of the smallest vertex cover of the subtree rooted at t, assuming that t is not part of the vertex cover.




6.22 Hint: Define C(j,m) = true if ∑{ai : i S} = m for some S {1,…,j}.