Midterm Study Guide CIT 594, Spring 2005
• 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 `Stack`s and `Vector`s, 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.
• Sets and Maps. Learn the operations.
• 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.