Midterm Study Guide
CSE 326: Data Structures
Winter 2006

Midterm Exam, Friday, February 3, 2006

• Exam policies
• Closed book, closed notes. Calculators allowed (not sure they will be useful for anything but you may use one if desired)
• The exam begins promptly at 12:30 (sec A) (2:30 sec B) and ends at 1:20 (sec A) (3:20 sec B).
• Topics covered
• Linked lists. Simple linked lists, doubly linked lists, circularly linked lists.
• Stacks and Queues, array and list implementations.
• Recursion. Designing algorithms recursively.
• Asymptotic analysis, Big-O. Worst case, upper bound, lower bound, analyzing loops, recurrences, amortized complexity.
• Trees – definitions
• Binary Heaps, D-heaps - Findmin, Deletemin, Insert. Additional operations of increase, decrease, buildheap.
• Leftist Heaps and Skew Heaps - Findmin, Deletemin, Insert. Additional operations of merge, increase, decrease
• Binomial Queues - Findmin, Deletemin, Insert. Additional operations of merge, increase, decrease.
• Dictionary ADT
• Binary search trees – Inorder, preorder, postorder traversals, insert, delete, find.
• AVL trees - Single and double rotations, insert, find.
• Splay trees - Splaying, insert, find.
• Study suggestions
• Do concrete problems from the book and re-work problems from lecture, section, and HW #1. Suggestions of more problems from the book: Chapter 2: 2.6, 2.10. Chapter 3: 3.21, 3.22, 3.23 (a). Chapter 4: 4.1, 4.2, 4.8, 4.9, 4.22, 4.27, 4.28. Chapter 6: 6.2, 6.3, 6.26, 6.30.
• Practice all the operations in binary heaps, leftist and skew heaps, binomial queues, binary search trees, AVL trees, splay trees. Practice analysis of algorithms.
• All material from lecture up through Splay trees is fair game. This material corresponds to: Chapters: 1, 2, 3, 4 (not section 4.7 on B-trees), and 6.

---