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

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

PRE-MIDTERM:

[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
 - binary search tree insert / delete / traversal (`tree walk')
 - red-black tree rotate (it is not necessary to memorize RBT-insert/delete)

[Short answer]
 - what is the definition of big-O, big-omega, big-theta
 - 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


POST-MIDTERM:

[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):
 - Dynamic Programming: fastest way
 - Dynamic Programming: matrix chain order
 - Dynamic Programming: longest common subsequence
 - Dynamic Programming: shortest path
 - Greedy: activity selector
 - Greedy: Huffman code
 - Greedy: Knapsack
 - Graph: DFS
 - Graph: BFS
 - Graph: Topological sort
 - Minimum Spanning Tree: Kruskal
 - Minimum Spanning Tree: Prim
 - Single-Source Shortest Path: Belman-Ford
 - Single-Source Shortest Path: DAG
 - Single-Source Shortest Path: Dijkstra
 - All-Pairs Shortest Path: Slow
 - All-Pairs Shortest Path: Faster
 - All-Pairs Shortest Path: Floyd-Warshall
 - All-Pairs Shortest Path: Johnson's

[Short-answer]
 - Dynamic Programming: what characterizes a DP algorithm
                        how to turn a recursive algorithm into a memoized one
                        how to turn a memoized algorithm into a bottom-up one
                        why longest simple path is not DP-solvable
 - Greedy: what characterizes a greedy algorithm
           why Knapsack 0-1 is not greedy-solvable
 - Greedy Huffman Coding: what Huffman coding is good for
                          what the prefix property is, why is it necessary
 - Graphs: the advantages of adjacency list vs. adjacency matrix representations
           the worst-case complexities of the graph algorithms above
           why can't the DAG algorithm handle cycles
           why can't Dijkstra's algorithm handle negative-weight edges
           h ow does Johnson's algorithm get rid of negative-weight edges