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