Midterm 2 Review

Tom Kelliher, CS23

Apr. 24, 1996

Please do not feed the instructor!!! He is an endangered species. (Well, at least his hair is.) He requires a very special diet to keep him from spending even more time devising ``evil'' homework assignments and examinations. Thank you for your cooperation.

There will be no material from Chapter 10 (trees) on the midterm. The final is another story...

1. Recursion: Searching techniques --- backtracking.
2. Grammars.
3. ADT stack
   • Implementations: pointer-based, array-based, derived from list base class
   • Applications: postfix to infix conversion, validating parentheses-like structures in an expression.
   • Graph searching.
4. ADT queue
   • Implementation: pointer-based, circular array, derived from list base class.
5. Inheritance, virtual functions, late binding
   • Base, derived classes.
   • Is-a, has-a, as-a.
   • Polymorphism.
   • Virtual, pure virtual functions.
   • Abstract base classes.
   • Types of inheritance.
   • Early, late binding.
6. Algorithm analysis
   • Why ``big Oh,'' definition, using.
   • Summations (Math. induction).
   • Worst-, average-case analysis.
   • Growth rates.
   • Sorting: lower bound, ``slow'' sorts, mergesort, quicksort, radix sort.