Final Exam Topics:
*******************************************************

Exam 1 & 2 Topics


Module 7: Sorting Algorithms
=================================

Algorithms
-----------
Insertion sort
Bubble sort
Selection sort
Mergesort
Quicksort (pivot selection: default to video algorithm [median of 3])
Heapsort
Bucket sort
Radix sort

For each algorithm:
-----------
Big-Ohs
+ Best-case
+ Average-case
+ Worst-case
+ Extra Space
Stable?
Adaptive?
Be able to trace the execution
Be able to write code (for Insertion sort, Bubble sort and Selection sort)


Module 8: Hashing
=================================
Hash functions
Resolving Collisions
+ Separate chaining
+ Linear probing
+ Quadratic Probing
+ Double Hashing
Load Factor Alpha
Rehashing
Big-Ohs


Module 9: Graphs
=================================

Graph Terminology
Graph ADT
Graph Implementations
+ Adjacency Matrix
+ Adjacency List
Graph traversals
+ Depth-First Search
+ Breadth-First Search
Topological Sorting
Shortest Paths Algorithms
+  Dijkstra's Algorithm

Spanning Trees
-----------
DFS spanning tree
BFS spanning tree
Minimum spanning tree (Prim's algorithm)

Circuits
+ Euler
+ Hamiltonian
  * Traveling salesperson problem