TEST 1 MATERIAL

Object oriented programming
  class design, data abstraction
  inheritance, abstract class, virtual methods, polymorphism
  examples: Pixel, MonoPixel, GrayPixel, ColorPixel, Matrix, Pixmap
  
Lists and iterators
  previous examples: array, vector, stack, queue
  list class
    member functions: front, push_front, pop_front, back, push_back, pop_back,
                      empty, clear
    O(1) insert/remove from ends, O(N) search/insert/remove from middle
    implemented as doubly linked list
        pointer manipulation
        destructor, copy constructor, operator=
  iterator
      provides sequential access to list (and other collection) items
      iterator operations: * (dereference), ++, --
      list functions involving iterators: begin, end, insert, erase
  <algorithm> library
      collection of algorithms that work on collections via iterators
      find, binary_search, count, max_element, random_shuffle, sort, ...
    
Trees and non-linear structures
  tree terminology: node, root, leaf, path, height, weight
  tree applications: file structure in OS, du command
  binary tree implementation
      pointer manipulation, tree recursion
      divide & conquer algorithms
  binary search tree
      if roughly balanced, O(log N) search/insert/remove
      if unbalanced, O(N) search/insert/remove
  AVL tree
      variant on binary search tree, ensures O(log N) tree height
      must perform rotations to maintain AVL property when insert/remove
      O(log N) search/insert/remove 
  heap
      complete binary tree, heap property, min-heap vs. max-heap
      O(log N) insert, O(1) get max/min, O(log N) remove max/min
      vector implementation
          must perform swaps to maintain heapness when insert/remove
      heap applications: implement priority queue, perform heap sort