This is intended to give you a sense of what I think is important from
the course so far, and what I will be thinking of when creating the
exam.

I hate disclaimers, but here are some anyway. This is not a
contract. I may have inadvertently left something off this list that
ends up in an exam question. I make no guarantees that the exam will
be 100% limited to items listed below. Moreover, I will not be able to
test all of this material given the time limitations of the exam. I
will have to pick and choose some subset of it.

You are permitted one 8.5 x 11 sheet of paper with notes (both sides)
for use as a reference during the exam.

Here are the specifics: Students should be able to...

ADTs: Be able to describe, use, and determine appropriate uses for
sets, maps, priority queues, and graphs.

Implementation strategies: Be able to explain what binary search
trees, heaps, hash tables, AVL trees, 2-3 trees, adjacency lists, and
adjacency matrices are used for. Be able to illustrate how standard
operations (insert, delete, etc.) work. Be able to quantify
performance (big-O) of standard operations. Show understanding of the
ideas behind operations and big-O performance by being able to answer
questions about novel variations on standard techniques.

Specifics regarding particular implementation strategies:

 - Be able to distinguish between binary trees, binary search trees,
   complete trees, balanced trees, and heaps. Know how and why they
   are implemented via pointer structures or arrays as appropriate.

 - Be able to insert a series of data into a binary search tree, heap,
   hash table, AVL tree, 2-tree, adjacency matrix, or set of adjacency
   lists and be able to show the intermediate results along the way.

 - Be able to describe and/or work through examples of hashing via
   open addressing and via chaining. Demonstrate how collision
   strategies work, such as linear probing, quadratic probing, and
   double hashing. Distinguish between primary and secondary
   clustering. Be able to describe trade-offs between open addressing
   and chaining. Be able to construct an appropriate hash function for
   a particular situation.

 - Be able to describe trade-offs between trees and hashing, and why
   one chooses one vs. the other.

 - Be able to describe trade-offs between adjacency lists, adjacency
   matrices, and other variations on the theme, and why one chooses
   one vs. the other.

Algorithms:

 - Be able to demonstrate detailed examples of the following sorting
   algorithms: selection sort, insertion sort, heapsort, merge sort,
   quicksort, radix sort. Be able to describe big-O performance for
   each, and be able to justify it. Be able to analyze a novel sorting
   algorithm that uses similar ideas.

 - Be able to demonstrate detailed examples of preorder, inorder, and
   postorder tree traversal.

 - Be able to demonstrate detailed examples of graph traversal
   algorithms such as depth-first and breadth-first traversal.

Java implementations:

 - Be able to construct Java code to implement sets or maps via
   binary search trees or hashing (open addressing or chaining),
   priority queues via heaps, or graphs via adjacency lists or
   adjacency matrices. Be able to implement variations on the above
   that I might come up.

 - Be able to implement aspects of sorting algorithms or graph
   traversal algorithms listed above, or variations that I might come
   up with.