Study Guide for Final Exam
CSE 326: Data Structures
Winter 1999

Final Exam, Monday, March 15, 1999, 2:30 - 4:20

• Exam policies
  • The midterm is closed book.
  • An 8 1/2 X 11 inch blue (or green) book is required.
  • You may put your own hand written notes in your blue book to aid you during the exam.
  • The exam begins promptly at 2:30 and ends at 4:20.

• Topics covered
  • Linked lists. Simple linked lists, doubly linked lists, multi-lists, polynomials, sparse matrices, adjacency lists, text editing, stacks, queues.
  • 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.
  • B-trees. Insert, delete, find.
  • Multidimensional trees. Quad-trees and k-d-trees, 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 d-heaps, insert, delete-min, increment, decrement, delete, cache performance of heaps.
  • Mergeable priority queues. Leftist heaps and skew heaps, merge operation, insert and delete-min in terms of merge.
  • Calendar queue. Discrete event simulation, insert and delete-min, selecting the bucket width and queue size.
  • Sorting. Insertion sort, heapsort, quicksort, mergesort, and radix sort. Cache performance of sorting.
  • Dynamic Equivalence. Up-trees, 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.25, 4.27, 4.28, 4.43
    • 5.1, 5.2, 5.19
    • 6.2, 6.3, 6.19, 6.26, 6.27
    • 7.1, 7.11, 7.15, 7.16, 7.19
    • 8.1
  • Do other problems from the book where thought must go into algorithm design and analysis.
  • Do the last final exam, writing complete solutions.
  • 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, quad-trees, k-d-trees, and calendar queues, you should practice on some specific examples doing their operations.