## Midterm #1 Study Guide CSE 373: Data Structures & Algorithms Autumn 2009

#### Midterm Exam #1, Friday, October 23, 2009

Exam policies:

• Closed book, closed notes.  Calculators NOT allowed.
• 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
• Binary search trees – Inorder, preorder, postorder traversals, insert, delete, find.
• AVL trees - Single and double rotations, insert, find.
• B-trees.  Motivation, structure, choice of M and L, insert/delete.

Sample midterms:

NOTES

·        Topics covered on these exams may not be the exact same topics covered on our exam; please see the list of topics listed above for topics covered on our exam.

·        These are provided to help you study and are not meant to be interpreted as a guarantee of the format of our actual midterm in terms of length or type of questions.

Midterm I samples:

Midterm II samples: (these contain questions on B Trees)

Study suggestions:

• Do concrete problems from the book and re-work problems from lecture and HW.  Suggestions of a few 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, B Trees, stacks and queues.
• Practice analysis of algorithms.
• All material from lecture up through B Trees is fair game.  This material corresponds to: Chapters: 1, 2, 3, 4 (Not Including: section 4.5 on Splay trees).