Due Monday May 22, no late assignments accepted
Problems 1 and 2 use the following graph G1.
1. Use Prim's algorithm to construct a minimum spanning tree for graph G1.
(a) List the sequence of steps taken, e.g. "edge (c,d) rejected because..." or "edge (e,f) accepted".
(b) Draw the spanning tree and give its cost.
2. Use Kruskal's algorithm on graph G1. Give the same information as you did for problem 1, parts a and b.
3. Use Dijkstra's algorithm to compute the shortest paths to all nodes, starting from node a. Show the intermediate steps--I have provided multiple copies of the graph where you can fill in values. You may also use a separate sheet of paper. Indicate whether nodes are "done", and the distance and parent info for each node at each step.
 |
 |
 |
 |
4. This problem is a very simple example of amortized analysis, to give you some experience. Consider a new kind of stack, which supports the operations Push, Pop, and Multipop. Multipop is given an argument k which says how many items to pop. If k is larger than the number of items in the stack, assume it just pops everything that is present.
Consider the following sequence of 10 operations, with N=7 Push steps, P=2 Pop steps, and M=1 Multipop steps.
push(1), push(2), push(3), POP, push(4), push(5), push(6), MULTIPOP(4), push(7), POP
(a) Write down the actual cost of each operation. Assume that a simple operation has a cost of 1.
(b) What is the worst-case time cost for Push, Pop, and Multipop, as a function of N?
Obviously, if there are M Multipop steps, we don't expect to see a total cost of M * multipop-worst-case. We need to use amortization to get a tighter bound on the cost.
(c) Write down a potential function for this data structure.
Hints: the potential must be at its minimum value when we begin with an empty
stack. Let's say that it starts at zero. Since budget = actual cost + change in
potential, we need to accumulate some credit (i.e. under-budget operations)
before we get to an expensive operation. It may be instructive to consider the
sequence push,push,push,push,push,multipop(5).
(d) Write down the amortized costs (i.e. the "budget") for push,
pop, and multipop.
Hint: these should not be functions of N.
(e) Using the result from part d, write down the asymptotic time cost of any sequence of N push, P pop, and M multipops.
5. Show the result of splaying the following tree at node 21.
