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

### Midterm Study Guide

#### Midterm Exam: Friday, February 5, 2010

• Exam policies
• Closed book, closed notes.
• The exam begins promptly at 2:30 and ends at 3:20.
• Topics covered
• All material from lecture 1 up to and including AVL trees is fair game.
• This material corresponds to: Chapters: 1, 2, 3, 4 (not section 4.5 on Splay Trees or 4.7 on B-trees), and 6.
• Here is a (fairly complete, but not exhaustive) summary of topics we've covered in lecture:
• 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.
• The focus will be on ideas/concepts about data structures and algorithms, not Java.

• Study suggestions
• Do concrete problems from the book and re-work problems from lecture, section, and HW.
• Practice all the operations on binary heaps, skew heaps, leftist heaps, binomial queues, binary search trees, and AVL trees.
• 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 midterms.
• Practice midterms (Some include topics (e.g. Splay Trees and B-Trees) not covered on our exam.) Unfortunately sample solutions to these are not available. The instructor or TAs would be happy to discuss any problems with you during office hours. There is also a section on the class message board devoted to midterm discussion.
• Sample Solution to Winter 2010 Midterm.

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