Below is a list of topics potentially on the final (not exhaustive):

• Abstract Data Types
• Big Oh notation (and related little oh, etc.)
• Iterative implementation of recursion using a stack
• Dictionaries
  • BST
  • AVL
  • Splay trees
  • B-trees (not covered in any detail in this course)
  • Hash-tables (listed in the book as a separate ADT)
• Priority Queues; primarily Binary Heaps
• Quicksort
• Heapsort
• Graphs
  • Directed vs undirected; weighted vs unweighted
  • Representations: adjacency list & adjacency matrix
  • Breadth-first-search & it's use for finding shortest distances in unweighted graphs
  • Topological sort
  • Dijkstra's algorithm for finding the shortest path
  • Kruskal's algorithm
• Parallelism
  • The forkjoin framework
  • Analysis: work & span
  • Parallel Prefix & Pack
• Concurrency
  • Race conditions & data races
  • Locks & Java's synchronized statement
  • Deadlocks
  • Readers/writer locks
• Union/find data structure
• Recurrences (last day of class)

Review worksheet used in section
Partial solutions to the worksheet