Recursion. Know my four rules
for doing recursion, and understand why they are important. You will be asked
to write a simple recursive method.
Collections. Know how
the interfaces and classes are related. Know the methods defined in the interfaces.
Stacks. Know the methods defined
for Stacks and Vectors, and how the two are related.
Be familiar with some uses of stacks. Understand the algorithms for parsing
and evaluating arithmetic expressions.
Simple Recursive Algorithms.
Understand the basic idea behind finding all permutations and behind Quicksort,
and understand the algorithm for Towers of Hanoi.
Backtracking. Understand the
relationship between backtracking and tree searching. Be able to write a backtracking
method. Understand the concept of a "virtual tree."
Analysis. Be able to determine
a suitable "characteristic operation" for an algorithm, and be able
to express the running time of an algorithm in terms of its characteristic
operations. Know the relationship between various Big-O running times.
Comments on the "Three Piles"
problem. Understand the use of a façade method. Also note that
the term "façade" is usually applied to complete classes,
not just individual methods.
Binary Trees. Know all the
terminology (including "balance") and know how to do every kind
of binary tree traversal.
Abstract Data Types. Know the difference
between a data type and an ADT. Understand what goes into a Javadoc "contract,"
and why. Understand the value of interfaces.
Generics. Know how to use generic
classes and methods, and how to write your own. Understand "erasure."
Learn more about generics than was discussed in class.
More JUnit. Know how to add
a test to a test suite, and how to test for methods that should throw exceptions.
Simple Sorting Algorithms.
Be able to distinguish the three types of sorts, and understand the notion
of a "loop invariant."
Searching. Understand why binary
searches take logarithmic time, and what that means.
Pointers and References.
Know the difference between pointers and references, and how they are implemented.
Understand the meaning of a "null" reference. Understand how Vectors
(and similar data structures) can "grow" in size as needed.
HTML. Know how to do simple HTML
markup in your Javadoc comments. Know how to pass parameters to an applet.
Hashing. Know the necessary and
the desirable characteristics of a hash code. Understand the different types
of hash tables, and how they handle collisions and clustering.
Abstract Data Types II. Know how
to classify methods. Understand the purpose of factory methods, and be able
to write them. Understand "mutable" vs. "immutable" objects.
BNF. Know the difference between simple
and extended BNF. Know how to read, and be able to write, definitions in both
kinds.
Recognizers. Given a BNF definition,
be able to write a recognizer for that definition.