Data structures and Algorithms: Past Exam Questions by Topic

(Last updated in 2005.)

Sorting

1993 p10 q7 (pdf|dvi) Insertion sort
1994 p4 q7 (pdf|dvi) Quicksort, Order statistics
1996 p4 q5 (pdf|dvi) Insertion Sort
1997 p3 q5 (pdf|dvi) Order statistics
1997 p4 q5 (pdf|dvi) Median finding
1999 p5 q1 (pdf|dvi) Heapsort
2000 p3 q5 (pdf|dvi) Quicksort
2000 p6 q1 (pdf|dvi) Mergesort, between points on a plane.
2001 p3 q5 (pdf|dvi) Quicksort
2002 p4 q4 (pdf|dvi) Shell's sort, Radix sort
2003 p3 q3 (pdf|dvi) Heap sort

Sets and trees

1993 p3 q7 (pdf|dvi) Binary tree
1994 p4 q6 (pdf|dvi) Red-black trees
1994 p10 q8 (pdf|dvi) Priority queues
1998 p3 q6 (pdf|dvi) Priority queues
1999 p3 q6 (pdf|dvi) Larsen's method
1999 p6 q1 (pdf|dvi) Splay trees
2002 p5 q1 (pdf|dvi) Disk storage
2003 p4 q3 (pdf|dvi) Hash tables
2004 p4 q3 (pdf|dvi) Splay trees, ternary trees
2004 p5 q1 (pdf|dvi) Larsen's method
2005 p4 q3 (pdf|dvi) Hash tables

Compression

1999 p4 q5 (pdf|dvi) Burrows Wheeler
2002 p6 q1 (pdf|dvi) Arithmetic Encoding
2003 p6 q1 (pdf|dvi) Burrows Wheeler
2004 p3 q3 (pdf|dvi) Lempel-Ziv
2005 p3 q2 (pdf|dvi) Huffman

Graph algorithms

1993 p4 q8 (pdf|dvi) Directed graph, transitive closure
1993 p10 q8 (pdf|dvi) All points shortest path
1996 p3 q5 (pdf|dvi) Dijkstra's algorithm
1997 p3 q6 (pdf|dvi) Kruskal's algorithm
1998 p4 q5 (pdf|dvi) Dijkstra's algorithm
2000 p4 q6 (pdf|dvi) Prim/Kruskal's algorithm
2000 p5 q1 (pdf|dvi) Bipartite graphs
2001 p5 q1 (pdf|dvi) Shortest distance; connected
2001 p6 q1 (pdf|dvi) Depth first; strongly connected
2003 p5 q1 (pdf|dvi) Kruskal's algorithm
2005 p5 q1 (pdf|dvi) Floyd's/Warshall's algorithms

Geometric algorithms

1993 p11 q8 (pdf|dvi) Plane closed polygon; convex hull
1996 p3 q6 (pdf|dvi) Graham scan
1998 p3 q5 (pdf|dvi) Points in polygons
2001 p4 q5 (pdf|dvi) Graham scan
2004 p6 q1 (pdf|dvi) Intersection of lines; Convex hull

Misc

1993 p3 q8 (pdf|dvi) O notation
1994 p3 q6 (pdf|dvi) Misc short questions
1994 p3 q7 (pdf|dvi) Misc short questions
2002 p3 q3 (pdf|dvi) Free store