Assigned: Thursday, September 7

Due: Thursday, September 14

CLR = Cormen, Leiserson, and Rivest (the big white book).

1. CLR 1.1-1
2. CLR 1.1-3, 1.2-2
3. CLR 1.3-3
4. CLR 1.3-6
5. A graph T is said to be a tree if T is connected and has no cycles. Show by induction that if T is a tree with n vertices, then T has exactly n-1 edges.
   Caution: When proving the induction step (if true for a tree of n nodes then true for a tree of n+1nodes), make sure to argue that your proof will work for an arbitrary tree of n+1 nodes.