Homework assignment 2
CSCI 3650
Summer 2001

Due: Thursday May 24

These assignments are from Cormen/Leiserson/Rivest, except for the last one.

  1. Page 57 4.1-1
  2. Page 60 4.2-2 (Use a recursion tree. Don't worry about non-integer values.)
  3. Page 64 4.3-1
  4. A binary tree has two kinds of nodes: internal nodes that have exactly two children, and leaves that have no children. Prove, by induction on the number of leaves in the tree, that a binary tree with n leaves has exactly n-1 internal nodes.