Work any 5 problems (you can work 6 and I will grade best 5)

1.What is the running time of the nearest-neighbor algorithm for TSP 
where at each step we visit the nearest unvisited
vertex?  (Assume adjacency matrix input/ give pseudocode)
2. Give an efficient algorithm (and state its running time) to 
determine if graph G contains a uv path, all of whose edge weights 
are equal.
3. 15-4 (just assume a simple tree structure)
4. An independent set in a graph is a subset of the vertices, no two of which are adjacent. 
The maximum independent set is the largest such subset. A Maximal Independent Set of a graph G=(V, E) 
is an independent set M such that the addition to M of any vertex in V-M creates a non-independent set. 
Write an efficient algorithm to find a maximal independent set in a graph. Demonstrate a graph on which 
your algorithm's maximal independent set is not the maximum independent set. 
5. Let G be a graph in which each vertex is colored either red or blue. Give a O(V+ E) time algorithm 
that finds a path from u to v that passes through the minimum number of blue vertices. 
6. 34.2-4
7. 15.2-1 
8. Can the following be bounded by a polynomial function?
 a) T(n) = T(n-1) + T(n/2) + 1; T(1) = 1. 
b) T(n) = T(n-1) + T(n/2) + n; T(1) = 1. 
Hint: write out the first ~20 terms in each and note the the growth rate 
in the difference between the ith and i+1st terms.