# 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