Topics covered since the Midterm

• Linked Lists (singly, doubly & circular)
  header (sentinel) nodes
• Trees (Binary, BST, 2-3-4 Trees, Red-Black Trees)
  Conversion between 2-3-4 & red-black trees
  building red-black trees (with required rotations)
• Maps & Sets (Multimaps & Multisets)
  Pair data type
  BST implementation & efficiency
  
• Heaps & Heapsort
  Array indexing scheme for complete tree
  heapify() & adjustHeap()
  Huffman Codes & Use of heap
• Hashing (hash functions & collisions)
  Open probing vs. Chaining
  Load Factor & Efficiency
• Graphs
  Adjacency Matrix & Adjacency Set
  Textbook's Implementation using Map & vInfo array
  BFS, DFS, Duals & Strong Components
  Minimum Path (Dijkstra's algorithm)
  Minimum Spanning tree (Prim's algorithm)
• String matching
  Simple approach
  Knuth-Morris-Pratt & use of fail[k] array
  Boyer-Moore & use of charJump[ch] and matchJump[k]

The exam is cumulative. However, approximately 75% of the questions will be from new material. There will be some code writing, but many of the questions will be conceptual in nature.

As on the midterm, you may bring any single sheet of paper with hand written notes. Otherwise this is a closed-book, closed-note test.