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
    sequential search: O(N) worst case, O(N) average case
    binary search: O(log N) worst case, O(log N) average case
    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
    base case(s), recursive case(s)
    analysis via recurrence relation
    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