The midterm will cover chapters 2, 3, 6, 7, 8, 11, 12, and 13.
In particular, you will be expected to know (without using books or notes):

[Step-through of algorithm] how to perform each of the following
algorithms (e.g. on a given input, recording the partial results of
each iteration of the outermost loop or recursion):
 - insertion sort
 - merge sort
 - heap sort
 - quicksort
 - counting sort
 - radix sort
 - bucket sort
 - hash find / insert using open addressing
 - binary search tree insert / delete / traversal(`tree walk')
 - red-black tree rotate (it is not necessary to memorize RBT-insert/delete)

[Short answer]
 - what kind of input would be a worst-case input for each of the above algorithms
 - what is the worst-case and average-case asymptotic complexity of each of the 
     above algorithms, and under what assumptions
 - briefly justify these asymptotic complexity bounds (you should introduce a
     worst-case input to explain some of these)
 - heaps: what is a heap,
          what is the heap property
          what are the complexities of the basic heap operations
 - limits of comparison sort: what characterizes a comparison sort
                              what is the worst-case complexity of the best 
                                possible comparison sorting algorithm, and why
                              under what conditions might one prefer 
                                counting/radix/bucket sort over
                                quick/merge/heap sort, and vice versa
 - hash tables: what makes a good hash function?
 - trees: what is the relationship between a tree's height, the number of
     nodes it has, and the number of leaves it has,
 - binary search trees: what is the BST property
                        what are the complexities of basic BST operations
                        why might one prefer a BST over a hash table and vice versa
 - red black trees: what are the RBT properties
                    what do these properties guarantee
                    why might one prefer a RBT over a BST

[Proof]
 - you will be expected to know how to prove an algorithm is correct
   using an inductive argument and an invariant