|
|
|
|
|
Midterm #1 Study Guide
CSE 373: Data Structures & Algorithms - Autumn 2007
Midterm Exam #1, Monday, Oct 22, 2007
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 and ends at 13: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.
- 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
Sample Midterm I
Study Suggestions
- Do concrete problems
from the book and re-work problems from lecture, section, and homeworks. 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.
- Practice all the
operations in binary search trees, AVL trees, stacks and
queues.
- 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
or 4.8).
|
