COSC 311  Final Exam topics FALL 2015

The exam is comprehensive.
As an aid to memory, you can bring an 8-1/2 X 11" sheet of paper, 
both sides used, with notes.

(0) Use of memory
  singly linked list
  doubly linked list
  array, arraylist
  
  run time stack
  use of heap (for dynamic allocation)

(1) Stack and stack algorithms
  basic operations on stack

(2) Queue and the use of the queue
  basic operation on queue
  linked list
  array
  circular queue
  
(3) Big Oh
  meaning and implications (using Big Oh properly to choose among algorithms)
    O(1), O(log n), O(n), O(n log n), O(n^2), ... O(2^n), O(n!)
  definition, given an algorithm -- how to determine Big Oh
  
(4) Recursion
  Understand stack based recursion: able to trace any recursive algorithm
  
(5) Trees
  General definitions
  Binary tree
  Binary search tree (BST)
    basic operations on BST
  Balanced binary search tree (AVL)
    insert operation
  B tree
    insert, find operations
  
(6) Priority Queue (heap)
  basic operations on heap
  When to use it
  
(7) Hashing
  Open addressing (doing probes)
  Chaining (aka closed addressing)
  basic operations (insert, delete, find)
  
(8) Sorts
  heap
  merge
  quick
  shell
  radix
  
(9) Graph algorithm
  Data structures: adjacency matrix, adjacency list
  Topological sort.