Topics for Data Structures and Algorithms

Comprehensive Exam

Posted: September 2006
UPDATE: September 9, 2004
Sample problems(PDF): posted September 2006

1. Binary Search Trees: AVL, Red-Black, and Splay
   
   
2. Sorting algorithms- quicksort, mergesort, heapsort, radix-sort, insertion sort
   
   
3. Binary Heaps
   
   
4. Hashing: hash functions, collision resolution strategies, load factor
   
   
5. Stacks, Queues, and Linked Lists- when to use one versus the other
   
   
6. Big-O notation
   
   
7. Algorithm Complexity
   
   
8. Recurrence relations and the Master Method
   
   
9. Recursive algorithms
   
   
10. Graph Algorithms.  Includes depth-first and breadth-first traversals, shortest-path algorithms, network flows, matching, minimum spanning trees, connectivity algorithms,
    
    
11. Dynamic Programming:  matrix-chain multiplication, polygon triangulation, longest common subsequence, 0-1 knapsack, etc.
    
    
12. Divide and Conquer algorithms: order statistics, binary search, minimum distance points, convex-hull formation, etc.
    
    
13. Greedy Algorithms:  Huffman codes, unit-task scheduling with deadlines, activity selection, fractional knapsack, etc.
    
    
14. NP completeness
    
    
15. Formal languages: Turing machines, Finite State Machines, Automata, Regular Expressions