Test #3 Topic List

• Bucket Sort and Hashing
  • Bucket Sort
  • Open chaining vs. Open addressing, including applications
  • Collision resolution w/open addressing, including linear and quadratic probing and double hashing.
  • Growing a hash table by rehashing
  
  
  
• Heaps and also Heap sort
  • Don't forget both representations (indexed and node-reference)
  
  
  
• Binary Search Trees
  
  
• Expression Trees
  
  
• Pre-order, Post-order, and In-order traversal
  
  
• Graphs, representation
  • Adj. Matrix
  • Adj. List
  • Applications and cost/benefit of each
  
  
  
• Graphs, BFS and DFS
  
  
• Graphs, Dijkstra's Alg.
  
  
• Graphs, Prim's
  
  
• Graphs, Kruskals using a heap and union-find
  
  
• Graphs, Topological sort.