|
|
|
|
|
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:
- 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 (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.
- Dictionary ADT
- 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.
|
CSE Home 
