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 a sum of
consecutive integers is quadratic. 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, subclasses, and method overriding.. 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, a general implementation framework,
and a 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.

 - Lists: Be able to construct Java code to implement a stack using
   an array, or linked list.

 - 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
 - "for each" loop
 - "built-in" classes for Stack, Queue, Deque
 - Sets or Maps (which we may start Friday)