STUDY GUIDE FOR FINAL
CSE 326 Autumn 2000
· Exam will be Monday, Dec 11th, from 2:30 to 4:20.
· The final will cover all material in the course, but will be weighted most heavily toward material covered after the midterm.
· Questions will be drawn from:
o Weiss, Chapters 1 – 9, plus 11.3, 11.5, 12.5, 12.6. We will not cover 9.4, 9.6, or 9.7.
o The lecture handouts.
o Material covered in the homeworks and programming projects.
· The exam will be closed books, closed notes.
· Be sure you know:
o how to compare functions using O(N), Θ(N), and Ω(N) notation
o how to analyze the running times of programs using the notions of worst case and best case complexity
o how to solve a simple recursive equation
o how to carry out a simple amortized analysis
o how the basic dictionary operations are implemented, what their worst-case (and when appropriate, average case or amotized case) running times for
§ linked lists and array-based lists
§ binary search trees, AVL trees, splay trees, and b-trees
§ hashing (including separate chaining, linear probing, quadratic probing, and double hashing)
§ binary heaps, leftist heaps, skew heaps
§ k-d trees and quadtrees
§ up trees and union/find
§ randomized skip lists and treaps
o Graph algorithms:
§ adjacency-list representation of graphs
§ Dijkstra’s shortest path algorithm
§ Kruskal’s minimum spanning tree algorithm
o Complexity and tradeoffs of sorting algorithms
§ insertion sort, quicksort, heapsort, mergesort, radix sort
§ lower bounds on comparison-based sorting algorithms
§ memory hierarchy (effect of cache on execution time)