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...

Complexity: Look at Java code or pseudo code and accurately count the
number of times that something executes. Use the fact that successive
divisions in half is logarithmic. Use big-O to represent count
appropriately. Use definition of big-O in order to show that one
expression is O(another). Compare different big-O quantities (n^2,
log n, 2^n, etc) and be able to rank them relative to each
other. Determine the big-O description of an algorithm described.

Inheritance: Be able to write Java code that appropriately uses
interfaces, abstract classes, and subclasses. Be able to correctly
predict what results that sample code using the above produces.

Data structures (general): Be able to distinguish between and justify
the roles of an ADT, an interface, an implementation (in concept), and
an actual Java implementation.

ADTs: Be able to describe, use, and determine appropriate uses for
lists, stacks, and queues.

Implementation tradeoffs: Be able to justify when arrays (or
ArrayLists) are appropriate vs. linked lists. Be able to do this
quantitatively with big-O descriptions.

Java implementations:

 - Linked lists: Be able to construct Java code to implement linked
   lists or other similar structures (doubly linked lists, or
   something else I come up with) according to specification.


 - Stacks: Be able to construct Java code to implement a stack using
   an array, ArrayList, or LinkedList.

 - Queues: Be able to construct Java code to implement a stack using
   an array, ArrayList, or LinkedList. Be able to appropriately handle
   problems that occur with a queue in an array.

Recursion: Be able to code a recursive method in Java subject to
specifications. Be able to explain quantitatively (with big-O
notation) tradeoffs in recursive vs. iterative solutions to a
particular problem.

Not going to test:
 - generics
 - "built-in" classes for Stack, Queue, Deque
 - backtracking