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.
--- The Management.
There will be no material from Chapter 10 (trees) on the midterm. The
final is another story...
- Recursion: Searching techniques --- backtracking.
- ADT stack
- Implementations: pointer-based, array-based, derived from list
- Applications: postfix to infix conversion, validating
parentheses-like structures in an expression.
- Graph searching.
- ADT queue
- Implementation: pointer-based, circular array, derived from list
- Inheritance, virtual functions, late binding
- Base, derived classes.
- Is-a, has-a, as-a.
- Virtual, pure virtual functions.
- Abstract base classes.
- Types of inheritance.
- Early, late binding.
- Algorithm analysis
- Why ``big Oh,'' definition, using.
- Summations (Math. induction).
- Worst-, average-case analysis.
- Growth rates.
- Sorting: lower bound, ``slow'' sorts, mergesort, quicksort, radix
Thomas P. Kelliher
Tue Apr 23 09:28:02 EDT 1996