This summary of the material to study for the test on September 26 is now finalized.

1. Review all the written homework assignments:
   1. Assignment 1
   2. Assignment 2
   3. Some practice questions on recurrences.
   4. Assignment 3
2. Problem 5.5 on page 181 of your textbook.
3. Problem 5.7 on page 182 of your textbook.
4. Problem 5.14 on page 182 of your textbook.
5. Problem 5.15 on page 182 of your textbook.
6. Problem 5.18 on page 183 of your textbook.
7. Represent the weighted directed graph G on page 199 of your textbook by a 5x5 matrix. Compute the matrix G^* using (min,+) matrix multiplication. (You will need to do matrix multiplication only twice.)
8. 1. What characteristics should a good hash function have? Answer.
   2. If the table size is the same as the number of data items, 100, roughly how many out of the 100 table entries would be expacted to have no item?
      (a) 5
      (b) 13
      (c) 25
      (d) 37
      (e) 56
      Answer.
9. Give a detailed description of the steps of heapsort, starting with the array "facetiously" and anding with a sorted array. Answer.