Problems from the CLR Book:
1) Let T=(V,E) be a connected undirected tree such that
each vertex has degree at most 3. Let n=|V|. Show that T has an edge
whose removal disconnects T into two disjoint subtrees
with no
more than (2n+1)/3 vertices each. Give a linear time
algorithm to
find such an edge.
2) 26.1-8 page 650
3) 26.2-4 page 663
4) 26.2-8 page 664
5) 26.2-10 page 664
6) 26.3-4 page 669
7) 26.3-2 Page 668
8) Formulate a linear programming problem in 2-dimensional space with
6 constraints and show step by step how the randomized LP algorithm
discussed in the class will execute on your example?