CSE 326 Winter 2010
 CSE Home 326 Home About Us Search Contact Info

 Assignments & Exams Projects Written Homeworks Midterm Exam Final Exam Administrative Home Annoucement Archive Message Board Anonymous Feedback Lectures Calendar & Slides Handouts First Day Handout Policies General Guidelines Grading Policies Programming Guidelines Written HW Guidelines Computing Unix Basics LaTex Info

Final Exam Study Guide

Final Exam: 2:30-4:20pm, Tuesday, March 16, 2010

• Exam policies
• The exam will be held in our regular lecture room (EEB 125)
• Closed book, closed notes.
• The exam begins promptly at 2:30 and ends at 4:20.
• Topics
• All material from lecture is fair game, although you can assume that material you have not been tested on yet (post-midterm material) will be emphasized a bit more.
• This material corresponds to: Chapters: 1-9, and 10.3.4
• Here is a (fairly complete, but not exhaustive) summary of topics we've covered in lecture that are fair game for the exam:

Pre-Midterm:

• Stacks and Queues, array and list implementations.
• Recursion. Designing algorithms recursively.  Inductive proof.
• Asymptotic analysis, Big-O. Worst, amortized (just the idea), average, best cases.  Upper and lower asymptotic bounds.  Analyzing loops, recurrences.
• Trees - definitions
• Binary Heaps, D-heaps - Findmin, Deletemin, Insert. Additional operations of increaseKey, decreaseKey, buildHeap.
• Skew Heaps - Findmin, Deletemin, Insert. Additional operations of merge, increaseKey, decreaseKey
• Leftist Heaps - Findmin, Deletemin, Insert. Additional operations of merge, increaseKey, decreaseKey
• Binomial Queues - Findmin, Deletemin, Insert. Additional operations of merge, increaseKey, decreaseKey.
• Binary search trees - Inorder, preorder, postorder traversals, insert, delete, find, build.
• AVL trees - Single and double rotations, insert, find, (no delete), build.

Post Midterm:

• Splay trees - Splaying: zig, zig-zig, and zig-zag rotations, insert, find, (no delete).
• The memory hierarchy. Temporal and spatial locality. Data structure choice and the memory hierarchy.
• B trees - motivation, choice of M and L, basic operations of find, insert, delete.
• Hashing. Properties of good hash functions. Selecting hash table size. Separate chaining and open addressing. Linear Probing, Quadratic Probing, & Double Hashing to resolve collisions. Rehashing.
• Sorting. Insertion sort, Selection sort, Heap sort, Merge sort, quicksort. In-place sorting. Stable sorting.
• Lower bound on comparison sorting.
• Disjoint Union/Find - Up-trees. Weighted union (union by size) and path compression.
• Graphs. Directed and undirected. Adjacency list and adjacency matrix representations. Edge and vertex complexities.
• Topological sorting.
• Graph searching (just the ideas on these - don't have to be able to execute). Depth-first, breadth-first, best-first.
• Shortest paths: Dijkstra's algorithm for SSSP, Floyd-Warshall for APSP
• Minimum spanning tree: Prim's and Kruskal's algorithms
• Huffman Coding will only appear as an extra credit question.
• The focus will be on ideas/concepts about data structures and algorithms, not Java. Although you could be asked to write short bits of Java or pseudo code.

• Study suggestions
• Do concrete problems from the book and re-work problems from lecture and homework.
• Practice all the operations on the data structures.
• Practice analysis of algorithms.  Learn and be able to reason about the complexities of operations on the data structures we've discussed in class.
• Try practice finals.
• Review the practice midterms.

• Practice finals (which cover some topics that we did not):

 Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to rea]