STUDY GUIDE FOR FINAL

CSE 326 Autumn 2000

· Exam will be Monday, Dec 11^th, 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)