Midterm #1 Study Guide
CSE 373: Data Structures & Algorithms
Spring 2008

Midterm Exam #1, Wednesday, April 23, 2008

Exam policies:

• Closed book, closed notes. Calculators NOT allowed (this policy was modified since you will not be required to do very sophisticated math and because some types of calculators could potentially give someone an unfair advantage)
• The exam begins promptly at 11:30 and ends at 12:20.

Topics covered:

• 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
• Dictionary ADT
• Binary search trees – Inorder, preorder, postorder traversals, insert, delete, find.
• AVL trees - Single and double rotations, insert, find.
• Splay trees – insert, find, splay operations
• Binary Heaps - Findmin, Deletemin, Insert. Additional operations of increase, decrease, buildheap.

Sample midterm:

• Sample Midterm I (Note, we will not have any questions on Heaps on our midterm)
• Solution to Sample Midterm I (Note, we will not have any questions on Heaps on our midterm)
• Extra steps written out for Sample Midterm I
• Key to Midterm I from 08sp

Study suggestions:

• Do concrete problems from the book and re-work problems from lecture, section, and HW. 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.19, 4.25. Chapter 6: 6.2, 6.3.
• Practice all the operations in binary heaps, binary search trees, AVL trees, splay trees, stacks and queues.
• Practice analysis of algorithms.
• All material from lecture up through Splay trees and binary min heaps is fair game. This material corresponds to: Chapters: 1, 2, 3, 4 (not section 4.7 on B-trees or 4.8), and 6 (not 6.5-6.9).

---