Final Exam Study Guide
CSE 373: Data Structures and Algorithms
Autumn 2002

Final Exam, Wednesday, December 18, 2002, 8:30 - 10:20

• Exam policies
  • The final exam 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. You may use your midterm blue book if you desire.
  • The exam begins promptly at 8:30 and ends at 10:20.
• Topics covered
  • Linked lists. Simple linked lists, doubly linked lists, sparse polynomials, unbounded integers.
  • Stacks and Queues, array and list implementations.
  • 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, insert, delete, find.
  • B-trees. Split for insert. Borrow and merge for delete.
  • Hashing. Find, insert, delete (lazy deletion). Hash functions for integers and character strings. Chaining. Open addressing with linear probing, quadratic probing, and double hashing. Load factors. Rehashing.
  • Binary Heaps. Insert, findmin, deletemin. Increasing and decreasing keys.
  • Binomial Heaps. Merge, insert, findmin, deletemin.
  • Sorting. Bubblesort,Insertionsort, Heapsort, Mergesort, Quicksort. In-place sorting. Stable sorting.
  • Lower bound on comparison sorting. Radix sort.
  • Memory performance of algorithms. Temporal and spatial locality. Cache misses and hits. Analysis of long scans.
  • Disjoint Union/Find. Up-trees. Weighted union and path compression.
  • Graphs. Directed and undirected. Labeled and unlabeled. Bipartite matching. Adjacency list and adjacency matrix representations.
  • Topological sorting.
  • Graph searching. Depth-first and breadth-first search. Application to finding connected components, spanning trees, and alternating paths for bipartite matching.
  • Shortest paths. Dijkstra's algorithm. All pairs shortest paths.
  • K-D trees. Construction of k-d trees. Nearest-neighbor search.
• Study suggestions
  • Do concrete problems from the book.
    Chapter 2: 2.1, 2.7.
    Chapter 3: 3.2, 3.9, 3.10, 3.17.
    Chapter 4: 4.1, 4.2, 4.9, 4.11, 4.22, 4.27, 4.28, 4.36.
    Chapter 5: 5.1, 5.2.
    Chapter 6: 6.2, 6.3, 6.18, 6.31, 6.32, 6.33.
    Chapter 7: 7.1, 7.2, 7.11, 7.12, 7.15, 7.17, 7.19, 7.20, 7.21.
    Chapter 8: 8.1, 8.2.
    Chapter 9: 9.1, 9.2, 9.5, 9.53.
  • Do the final exam from 1999 (CSE 326). Ignore questions on topics not covered in our course.
  • Practice all the operations in binary search trees, AVL trees, splay trees, hashing, binary heaps, and binomial heaps, disjoint union/find, sorting, graphs, and k-d trees. You need to know how to implement pointers with arrays (cursor implemenation of pointers). You will need to understand basic memory performance analysis. Practice analysis of algorithms, including recurrences.