Heaps:
- priority queues! (Similar abstraction to queue)
- ordering requirement
- shape requirement
- representation with vector/array -- index calculations for parent/children
- operations:
  - push
  - pop
  - top
  - upHeap() / sift_up
  - downHeap() / sift_down
  - buildHeap() / make_heap
  - heap_sort()
  - know the complexity for each operation (hint: *usually* height of tree)

Hash Tables:
- vector of slots
- average complexity for insert/erase/find
- worst case for insert/erase/find
- "hash function" -- what is it? What does it do?
  - goals
- open addressing vs. separate chaining
  - how are collisions resolved for each
- load factor of hash table
  - why would we want to change the table size?
- insertion / removal examples
  - separate chaining
  - open addressing

Sorting and partitioning
- partition
  - two way (<=, >)
  - three way (<, ==, >)
  - choosing a good pivot
- nth_element
  - recurrence
  - complexity
- shell_sort
  - h_sort
  - choosing a good h-sequence
  - average runtime O(N^1.5)
- divide and conquer sorting
  - merge_sort
    - merge algorithm
    - complexity
    - comparison to quick_sort
  - quick_sort
    - partitioning
    - complexity
    - comparison to merge_sort
- How sorting algorithms perform when:
  - reverse sorted
  - almost sorted
  - sorted

Non-comparison-based sorting
- radix sort
  - how does it work
  - tracing through an example
  - Complexity (space AND time)
- counting sort
  - how does it work
  - tracing through an example
  - Complexity (space AND time)
- Limitations of radix and counting sort

Graphs
- Representations
  - Adjacency Matrix
  - Adjacency List
- Terms
  - Vertex
  - Edge
  - Directed/Undirected
  - Disconnected, Connected, Complete
  - Strongly vs. Weakly connected
  - Minimum Spanning Tree
  - Shortest Path
  - Topological Sort
- Algorithms
  - Searching
    - Breadth-First Search
    - Depth-First Search
    - Be able to trace through an example of each
  - Topological Sort
    - Goals / When to use
    - Trace through an example
  - Minimum Spanning Tree
    - Prim's
      - add smallest edge in EXPLORED graph (so far) until completely connected
    - Kruskal's
      - add smallest edge in ENTIRE graph until completely connected
    - Which one is better? Why?
    - Trace through an example
  - Shortest Path
    - Dijkstra's
      - complexity
	  - know the idea!

ACM Code of Ethics




NOT ON THE EXAM:
  - Dijkstra: trace through an example
  - Bellman-Ford
    - complexity