Mini #4, 15451 Fall 2010
         ========================

This mini is due via *email* to your TA, by 11:59pm Tuesday, Oct 12.
Please use the *exact* subject line "15-451 MINI #4" in your email.
As always make sure to include your name and Andrew ID.

Also, we prefer that you copy your answers directly into the email body, instead
of including attachments. Thanks!

1. You are given the following tree:

A----6----B----2----C----1----D
|         |         |        /
0.5       5         43      0
|         |         |      /
E----21---F----4----G-----/

a. Find the minimum weight spanning tree using Kruskal's algorithm. You can just
list the order in which the edges are chosen.

b. Find the minimum weight spanning tree using Prim's algorithm. Start from node
A. You can just list the order in which the edges are chosen.


2. Suppose we are walking up n stairs. At each step, you can go up 1 stair, 2
stairs or 3 stairs. Our goal is to compute how many different ways there are to 
get to the top (level n) starting at level 0. We can’t go down and we want to 
stop exactly at level n.

a. Let f(n) denote number of ways to get to level n. Complete the following 
small cases.
    f(0) = 1 //We are already at 0.
    f(1) = ?
    f(2) = ?
    f(3) = ?

b. Explain why is the recurrence f(n) = f(n-1) + f(n-2) + f(n-3) correct.

c. Using dynamic programming write pseudocode to compute f(n) in linear time.