Any questions over the following will be **closed book**.

## Sorting, Searching, Generic classes

*Know the linear search
algorithm, when it is appropriate to use, and its relative efficiency
(big-Oh notation).*
*Know the binary search
algorithm, when it is appropriate to use, and its relative efficiency.*
*Know algorithms (not
the code, just how they work) for selection sort, bubble sort, heap sort,
quick sort.*
*Know the time
efficiency of each sorting algorithm (big-Oh notation).*
*Know logs of numbers in
base 2. *
*Be able to explain the
advantages of generic classes.*

Any questions over the following
will be **open book.**

## Stacks & Queues

·
Know the basic operations on a stack.

·
Know how to convert an arithmetic expression from infix to
post-fix.

·
Know the basic operations on a queue.

·
Know how to use a stack and a queue to evaluate a post-fix
expression.

## Trees

·
Be able to hand-execute binary tree traversals: pre-order,
in-order, and post-order.

·
Understand how a binary search tree is organized.

·
Understand how trees are used to represent arithmetic
expressions.

## Graphs

·
Know the definition of a graph.

·
Know how to do a depth-first traversal of a graph.

·
Know how to do a breadth-first traversal of a graph.

·
Know how to do a topological sort of a directed graph.

## Java Collections

·
Be familiar enough with the Java collections
that are in the textbook that you can __write your own code__ using them.
Note that all of these are *generic*
classes.

## Arrays

·
Use both 1-dimensional arrays and 2-dimensional arrays of either
primitives or objects in a program.

·
Pass arrays as parameters.

·
Return arrays from functions.

## File Input and Output

- Know how to allow the
user to use a
*FileChooser*
object to select a file.
- Know how to read data from a file using a
*Scanner* object; know how to use the
*Scanner* methods.

## Classes

- Create classes, write
accessor and mutator methods, override methods.

## Recursion

- Definition of recursion.
- Understand how activation records go on the stack.
- Hand-execute a recursive subprogram.
- Know advantages and disadvantages of recursion vs.
iteration.

## Memory Allocation and Linked Data Structures

·
Understand how an array is implemented in memory.

·
Understand the difference between a direct access data
structure and a sequential access data structure.

·
Know when a linked data structure is appropriate and when
another type of list structure is appropriate.

## Generic Classes

·
Be able to use a generic class in a program.

·
Be able to create your own generic class.