Study Guide for Final Exam
CSE 326: Data Structures
Spring 1997
Final Exam, June 11, 1997, 2:30  4:20
 Topics covered

Linked lists. Simple linked lists, doubly linked lists, multilists,
polynomials, sparse matrices, adjacency lists, text editing, stacks, queues,
depthfirst search.

Recursion. Designing algorithms recursively, using call by reference.

Analysis of algorithms. Worst case, average case, upper bound, lower
bound, analyzing loops, recurrences, amortized complexity.

Trees and traversals. Multiway trees, preorder, postorder.

Binary search trees. Inorder traversal, insert, delete, find.

AVL trees. Single and double rotations, insert, delete, find.

Splay trees. Splaying, split, join, insert, delete, find.

Btrees. Insert, delete, find.

Multidimensional trees. Quadtrees and kdtrees, insert, delete, range queries.

Hashing. Open and closed hashing, hash functions, linear probing, quadratic
probing, double hashing, rehashing.

Extendible hashing. Splitting pages and extending the hash table.

Priority queues. Binary heaps and dheaps, insert, deletemin, increment,
decrement, delete, cache performance of heaps.

Mergeable priority queues. Leftist heaps and skew heaps, merge operation,
insert and deletemin in terms of merge.

Calendar queue. Discrete event simulation, insert and deletemin, selecting
the bucket width and queue size.

Sorting. Insertion sort, heapsort, quicksort, mergesort, and radix sort.
Cache performance of sorting.

Dynamic Equivalence. Uptrees, union, weighted union, path compression.

Study suggestions

Do concrete problems from the book. This will help you understand more
fully the various data structures explored in the course.
Here are some suggestions from chapters
4, 5, 6, 7, and 8.

4.1, 4.2, 4.9, 4.16, 4.23, 4.24, 4.36

5.1, 5.2, 5.14

6.2, 6.3, 6.16, 6.17, 6.23, 6.24,

7.1, 7.10, 7.12, 7.16

8.1
 Do other problems from the book where thought must go into algorithm
design and analysis.

Do the last final exam.

Be sure that you can demonstrate knowledge of all the operations on all the
data structures we have studied. For those data structures not in the
book, quadtrees, kdtrees, and calendar queues, you should practice on
some specific examples doing their operations.