Topics for the Final Exam
The final is open book, open notes, calculators allowed, but no computers. Schedule the exam through distance education services!
The emphasis is on the second half of the class, but this means knowing concepts from the first half (e.g. recurrence relations, BigO, etc.)
Linked Data Structures
Hash Tables
 General concepts behind a hash table and idea of efficiently looking up key/value pairs (but maybe not storing efficiently)
 Properties of a good hash function
 How to handle collisions
 chaining
 probing
 double hashing
 Expected runtime
Disjoint Sets
 Simple implementations using arrays or linked lists
 Disjoint set forest
 Why path compression and union by rank help
 Idea of amortized runtime
Graphs

Basic concept, edges, vertices, relationship

Breadth First Search

Algorithm, Purpose, space/time behavior

Run on a graph, be able to identify when it may be useful

Depth First Search

Algorithm, Purpose, space/time behavior

Run on a graph, be able to identify when it may be useful

Detecting cycles

DAG, Directed Acyclic Graph

Minimum Spanning Tree

Dijkstra's Shortest Path Algorithm

Limitations

Runtime

Demonstrate on a graph
STL and Java Collections
 Using STL vector, map, set
 Using Java Collections Arraylist, Map