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, <stack> 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 <queue> library queue applications: simulating customer lines, print queues, ...