1. Do problem 21.3-4. Hint: You know the phrase "Time is money"? We can do this analysis by representing the time we spend as money. Following the parent pointer of a node, and if necessary changing the parent pointer to point to the root, costs one dollar. Now imagine we stash a dollar at each node when we MAKE the node. The algorithm can grab the dollar, when and if it reaches that node during a FIND operation. How can you use this "charging scheme" (the technical term for an argument like this) to prove that the total running time is O(m)?

2. Prove that if the edge weights in an undirected graph G are unique, then the minimum spanning tree of G is unique.

3. In the Hamiltonian path problem, we are given an undirected graph G=(V,E), and are asked to determine whether G contains a simple path visiting all the vertices. We claimed in class that Hamiltonian path is NP-complete. The book contains a complicated proof in Section 34.5.3 that the Hamiltonian cycle problem is NP-complete. Using the assumption that Hamiltonian path is NP-complete, give a simpler proof that Hamiltonian cycle is NP-complete.

4. In HW5 we looked at the problem of finding an independent set in a simple graph consisting of a single path. Recall that an independent set of vertices is a set in which no two vertices are connected by an edge. Unlike the problem in HW5, here the vertices are unweighted, and the maximum independent set is one which has a maximum number of verticies. Show that the maximum independet set problem on an arbitrary graph G is NP-complete.