binary heap
  structure property
  heap property

priority queue
  getMin (remove head)
  add
  build

implement priority queue as binary heap

axioms for alternate version of priority queue
  items are (value, priority) pairs

heap sort 
  build a binary heap
  do repeated getMin() to create the sort

basic graph theory
  undirected graphs
  directed graphs
  bi-partite graphs
  topological sort
  Dijkstra's algorithm for shortest paths
  spanning tree
  minimum spanning tree
    Kruskal's algorithm for MST
    Prim's algorithm for MST

  Euler path
  Euler circuit
  Hamiltonian circuit
  Traveling salesman and P/NP/NP-complete

insertion sort
  O(N^2) worst case
  sometimes used as the "finisher" in quicksort
selection sort
  O(N^2) worst case
  similar in concept to insertion sort but operationally it 
    manipulates the array a bit differently
merge sort
  O(N log N) best case
  O(N log N) wosrt case
  O(N log N) average case
  cost: uses lots of extra memory, needs a second array as large
        as the one you are sorting
quicksort
  O(N log N) best case
  O(N log N) average case
  O(N^2) worst case
  does not need much extra space
  get extra efficiency by cutting off recursion when the lists
    become smaller than, say, length 15 and then doing some other
    sort like insertion sort on the small lists to finish up
bogosort
  random shuffling until you get the one that is in order
  O(infinity) worst case
  an extreme, just an illustration, not a serious shuffle

sorts are stable or unstable
  stable means preserves the original order of items with 
    the same value

solve the recurrance equation analyzing the behavior of mergesort
  T(N) = 2*T(N/2) + N
  we want to solve this so that we get something like
   
     T(N) = ....

  where the function T does not appear on the right hand side
  we find T(N) is O(N log N)

proof by induction
proof by contradiction
proof by contrapositive
dis-proof by counter example


axiomatic definition of ADT behavior
  List ADT
  Stack ADT
  Queue ADT
  Set ADT
  MSet ADT (multiset)
  Map ADT


List data structure
  general ops: get kth item
               insert at slot k
               delete at slot k

implementing lists:
  as array
  as linked cells

Sorted list are especially nice
order information can assist in list searching
binary search can find an item in O(log N) time worst case
         
special lists:
  Stack
    general ops: push, pop, top, empty, size
    keep pointer to most recent slot (t)
    push is insert at slot t
    pop is delete from slot t
    push, pop are O(1) since we access the top slot ddirectly via pointer
      no searching through the list, no rearrangement of locations
      this applies to implementations by links or array
    
  Queue
    general ops: add, remove, front, empty, size
    keep pointers to front slot, back slot
    add is insert at slot front
    remove is delete from slot back
    add, remove are O(1) since we access the slots directly by pointer
      no searching through the list, no rearrangement of locations
      this applies to implementations by links or array


Bubble sort
  O(N^2) time required to sort list of N items
  pro: easy to program
  con: very slow, useless for sorting lists of any serious size


Tree data structure in general (n-ary tree)
  Knuth transform, converts n-ary tree to binary tree
Binary Tree data structure
Binary Search Tree

Tree balancing: AVL, Splay

traversals:
  in-order, pre-order, post-order
  in-order gives sorted list from a BST
  pre-order, post-order give lists dependent on tree structure

BST Sort
  Not a real sorting algorithm name, but a way to remember that one fairly 
  efficient way to sort a list is to first build a binary search tree,
  then traverse it in the right way
    1) build a BST from the list: O(N log N)
         one insert in a BST: O(log N) for tree with N elments
         doing N inserts: O(N log N)
    2) in-order traversal to get the sorted order of elements
         O(N) since we have to visit each of the N nodes in the BST
  So total worst case time complexity is
    O(N log N) + O(N) which is O(N * (1+ log N))
                      which is O(N log N)


Pigeon hole principle
Hash Table, hash function
  how to pick table size
  how to make an effective hash function
  what to do about collisions
    hash into linked lists (or other collection data structures)
      table size should be prime, and same the size as # elements expected
    probing to find an open cell in the table
      linear probing function
      quadratic probing function
      table size should be prime, and twice the # elements expected
  rehasing to extend the table size
  

"Big Oh" notation for expressing growth rates of functions
  List of length N
    insert is O(N)
    remove is O(1) once you find the element
    find is O(N)

  Queue containing N items
    add is O(1)
    remove is O(1)
    front is O(1)
    can't get middle elements like general List

  Stack containing N items
    push is O(1)
    pop is O(1)
    top is O(1)
    can't get middle elements like general List

  Binary Search Tree with N nodes
    find is O(log N)
    insert is O(log N)
    remove is O(log N) because we have to find it to remove it
    traversals are O(N) (list every element in some order)
    we get ordering (sorting) information from the tree structure
    degenerate case of BST is a List
 
  Hash table of N elements
    insert is O(1)
    find is O(1)
    delete is O(1) 
    get no ordering information from the table

  Set
    basic ops: add, delete, isIn (find), empty, delete
    sets can be implemented as BST to make operations take
       O(log N) worst case 
       add is O(log N) like insert in BST
       delete is O(log N) like delete in BST
       find is O(log N) like find in BST
         isIn is a version of find, returns boolean rather than value record
       empty is O(1)
 
  Map
    basic ops: (assume implemented as BST)
      add (key, value) pair is O(log n)
      delete (key, value) pair is O(log n)
      get (key) is O(log N), returns the value stored with this key