###
CSC 222: Computer Programming II

Spring 2004

Test 2 Review

TEST 1 MATERIAL
Object-oriented design
designing complex/interacting classes (e.g., Cave, CaveMaze)
templated classes, templated functions
inheritance
derived class inherits data fields & member functions from parent
can add new functionality, or override existing functionality
e.g., List --> SortedList
IS_A relationship: can pass derived object where parent is expected
private vs. protected, virtual member functions
code testing strategies
Searching and efficiency
sequential search vs. binary search
worst case vs. average case vs. best case performance
Big-Oh notation
sequential search is O(N), binary search is O(log N)
rate-of-growth behavior
formal definition of Big-Oh
Sorting and recursion
insertion sort vs. selection sort vs. merge sort
insertion & selection sorts are O(N^2), merge sort is O(N log N)
mixing selection & merge sorts
recursion
base case(s), recursive case(s)
avoiding infinite recursion
recursion vs. iteration
Stacks & queues
stack ADT: push, pop, top, empty, size
vector implementation, library
stack applications: delimiter matching, reverse Polish expressions, ...
run-time stack: push activation record when function called, pop when done
queue ADT: enqueue (push), dequeue (pop), front, empty, size
library
queue applications: simulating customer lines, print queues, ...