Midterm score distribution
Midterm Study Guide
Midterm Exam, Wednesday, April 29, 2009
- Exam policies
- Closed book, closed notes.
- The exam begins promptly at 12:30 and ends at 1:20.
- Topics covered
- All material from lecture up to and including through Splay trees is fair game.
- This material corresponds to: Chapters: 1, 2, 3, 4 (not section 4.7 on B-trees), and 6.
- Here is a (fairly complete, but not exhaustive) summary of topics we've covered in lecture:
- Linked lists. Simple linked lists, doubly linked lists,
circularly linked lists.
- Stacks and Queues, array and list implementations.
- Recursion. Designing algorithms recursively. Inductive proof.
- Asymptotic analysis, Big-O. Worst, amortized, 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.
- Dictionary ADT
- Binary search trees - Inorder, preorder, postorder traversals,
insert, delete, find, build.
- AVL trees - Single and double rotations, insert, find, delete,
build.
- Splay trees - Zig, zig-zig, and zig-zag rotations, insert, find, 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, AVL trees, and splay 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