Midterm Study GuideCIT 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.