Final Exam topics COSC 311  FALL 2018

Final exam is comprehensive.

Official exam date/time:  Tuesday, December 18, 5:30 - 7:00 pm
( https://www.emich.edu/registrar/calendars/fall-2018/examschedule.php )

An 8-1/2 X 11 crib sheet (both sides) is permitted.
All scrap paper and crib sheet must be turned in with the completed exam.

Final exam topics:
  Recursion
    Tracing recursion with activation tree
    Memo-izing
  Queue
  Stack and stack algorithms
  Postfix, infix, prefix expressions (and converting between them)
  Expression tree and postorder, inorder, preorder traversals
  General (multi-way) tree
  Binary tree
  Binary search tree 
  AVL tree
  Splay tree
  (2, 3, 4): search and insert
  Hashing
  Skip list
  Priority queue
  Trie
  Huffman code
  Sorts:
    Quick sort
    Merge sort (internal)
    Radix (bucket) sort
    Counting sort
    Topological (graph algorithm)
  Prefix sum
  Big Oh: 
    Estimating big oh from pseudo-code
    Comparing Big Oh categories
  Choosing among algorithms based on problem, data set size, and Big Oh.
  
 


   
No questions on:
   kD tree
   Gray code, hypercubes
   delete from B tree
   Bloom filter
   External merge sort
   Any graph algorithms except topological sort
   Formal definition of Big Oh ( f(n) is O( g(n) ) if there exists n0 (n0 an integer)
      and c >= 1 such that  f(n) <= c * g(n) for all n >= n0 )
   Ackermann's function