1.  Graph Shortest Paths: Consider the following directed, weighted graph:

(a)  Even though the graph has negative weight edges, step through Dijkstra’s algorithm to calculate

ga夕夕Оgedl夕 shortest paths from A to every other vertex.  Show your steps in the table below. At the end of each step show the distances as they are after relaxation (in the beginning only d[A] is 0, the rest are &, shown for your convenience). Also list for each vertex its Edge To (which is the edge that marks the final step in the shortest path, as shown in class). Under “Vertex” show the vertex being added to the tree (taken out of the priority queue) at that stage.

2.  Greedy Algorithms: The maximum independent set in a graph or a tree is a maximal set of mutually disconnected nodes in a graph.  To solve the problem we should find a maximum set of nodes such that no two nodes in the set have and edge between them.   When the graph is a tree, the maximum size independent set can be found efficiently using a greedy algorithm.

(a)  Show that every leaf in a tree is included in at least one maximum independent set.  Hint:  Given a

leaf, show that every maximum independent set can either have this leaf or be made to have this leaf with one simple exchange.

(b)  Given (a) above, we can define a greedy algorithm as follows:

● Initialize an empty set S .

●  Pick a random leaf and add it to S .

●  Remove its parent from the tree because the parent cannot be part of the set (leaving possible descendants of that parent in the tree. Notice that the tree may now be disconnected but that’s ok and that now some nodes may become leaves).

●  Repeat until the tree is empty.

●  Return S

What is the runtime of this algorithm as a function of n, the number of nodes in the tree?

3.  Dynamic Programming:  The RОd ca≠≠ing problem is defined as follows:  Suppose you have a rod of length n, and you want to cut up the rod and sell the pieces in a way that maximizes the total amount of money you get. A piece of length i is worth pi  dollars. For example, given a rod of length 4, these are the ways to cut it:

(1,1,2)                   (1,2,1)                   (2,1,1)                  (1,1,1,1)

(a)  A recursive algorithm to solve the problem is to examine all the possible cuts:

● First, cut a piece of size i off the left end of the rod, and sell it.

● Then, recursively find the optimal way to cut the remainder of the rod (of size n 一 i).

We don’t know how large a piece we should cut off. So we try all possible cases. First we try cutting a piece of length 1, and combining it with the optimal way to cut a rod of length n 一 1, then cut a piece of length 2 and combining it with the optimal way to cut a rod of length n 一 2, etc.  Notice that we can also ”cut” a piece of size n which is the same as not cutting at all and just use the entire rod. Question: Formulate the recursive algorithm as an equation by filling in the missing parts. We define rn  as the optimal solution for a rod of size n:

rn  = maxsomething {something}

(b)  Draw the recursion tree resulting in calculating the solution for a rod of size 4. The first level is given.

Each node is the step where you cut a piece of i, sell it and calculate recursively the optimal solution for the remaining n 一 i.  Draw the rest (as a function of i at every level based on the formula you calculated above).

4  

i =     cut 0              cut 1              cut 2              cut 3

(c)  The problem  can be solved using  dynamic programming by first solving  small  subproblems  and memoizing them, using the formula as above. Given the following prices, solve the problem for a rod of size 4 by filling the table below: