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, tries, adjacency lists, and
adjacency matrices are used for. Be able to illustrate how standard
operations (insert, delete, etc.) work. Be able to indicate
computational complexity (big-O) of standard operations. Show
understanding of the ideas behind operations and computational
complexity 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. 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, or AVL tree 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 and random probing. Be able
   to describe tradeoofs between open addressing and chaining. Be able
   to construct an appropriate hash function for a particular situation.

 - Be able to describe tradeoffs between trees and hashing, and how
   one chooses one vs. the other.

 - Be familiar with B+ trees and extendible hashing, be able to
   explain what their purposes are, and be able to demonstrate how
   they work on simple examples.

Algorithms:

 - Be able to demonstrate detailed examples of the following sorting
   algorithms: selection sort, insertion sort, merge sort, quicksort,
   radix sort. Be able to describe computational complexity for each,
   and be able to justify it in cases of the quadratic sorts. 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. Be able
   to find the shortest path through an unweighted graph by using
   breadth-first, or through a weighted graph using Dijkstra's
   algorithm.

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 listed above, or
   variations that I might come up with.