CSC 427: Data Structures and Algorithm Analysis
Fall 2004
Test 1 Review
C++ review
program structure, input/output
variables, constants, expressions
functions, parameters (by-value & by-reference), default parameters
control statements: if, if-else, while, for
strings, arrays, vectors, stacks, queues, linked lists
classes, data fields, member functions
algorithm design and analysis
big-Oh notation, rate-of-growth, formal definition
searching
sequential search: O(N) worst case, O(N) average case
binary search: O(log N) worst case, O(log N) average case
sorting
insertion sort: O(N2) worst/average case, O(1) best case
selection sort: O(N2) worst/average/best case
merge sort: O(N log N) worst/average/best case
recursion
base case(s), recursive case(s)
analysis via recurrence relation
inheritance
derived classes, overriding member functions
virtual member functions, protected data fields
List, SortedList, LazyList classes
dynamic memory structures
pointers, dynamic memory
sorting vectors of items vs. sorting vectors of pointers to items
2-dimensional vectors, Matrix class