COSC 311  Fall 2017 Final Exam Topics

Sorts:
  merge, quick, heap, radix, shell, counting
  (insertion, selection and bubble are assumed from previous course)
  
Skip list:
  find, insert, delete
  
(2, 4) tree:
  find, insert, delete
  
Priority queue:
  insert, delete
  
Splay tree:
  find, insert, delete
  
AVL tree:
  find, insert
  
BST:
  find, insert, delete
  
General tree
  - The idea of multi-way tree
  - Traversals:
      breadth-first
      binary tree:
        postfix, infix, prefix
  - Expression tree
  
Hashing:
  find, insert delete
  linear probe, quadratic probe
  chaining
  
Stack:
  Stack ops: push, pop, isEmpty
  Stack algorithms: paren matching, palindrome detection, evaluate postfix,
    other algorithms as given in "Appendix"

Queue:
  Queue ops: insert, delete, isEmpty, isFull
  Circular queue
  
Recursion

Graph algorithm:
  Topological sort

Big Oh:
  Counting execution time (i.e., finding T(n) )
  Using the definition of Big Oh (e.g., find Big Oh from T(n) )
  Ranking Big Oh functions