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

Midterm Exam #1, Friday, October 19, 2012

Exam policies:

• Closed book, closed notes. Calculators NOT allowed.
• The exam begins promptly at 2:30 and ends at 3: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. (No delete)
• Binary Heaps - Findmin, Deletemin, Insert. Additional operations of increase, decrease, buildheap

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:

• Sample Midterm I (Solution to Sample Midterm I) (Extra steps written out for Sample Midterm I) (Note, we will not have any questions on Splay Trees on our midterm)
• Midterm I from 08sp (Solution to Midterm I from 08sp) (Note, we will not have any questions on Splay trees or amortized analysis on our midterm)
• Midterm I from 09wi (Solution to Midterm I from 09wi)
• Midterm I from 09sp (Solution to Midterm I from 09sp) (Note, we will not have any questions on hashing on our midterm)
• Midterm I from 10sp (Solution to Midterm I from 10sp)
• Midterm I from 10au (Solution to Midterm I from 10au)
• Midterm I from 11au (Solution to Midterm I from 11au)
• Midterm I from 12wi (Solution to Midterm I from 12wi)

• NEW! Midterm I from 12au (Solution to Midterm I from 12au)

Midterm II samples: (These are mostly not relevant except where noted.)

· Midterm II from 08sp (Key to Midterm II from 08sp) (contains a binary min heap question)

· Midterm II from 09sp (Key to Midterm II from 09sp) (contains AVL and binary min heap questions)

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 (2^nd and 3^rd editions): 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 on stacks and queues, binary search trees, AVL trees, and binary min heaps.
• Practice analysis of algorithms.
• All material from lecture up through and including Binary min heaps is fair game. This material corresponds to: Chapters: 1, 2, 3, 4 (Not Including: section 4.5 on Splay trees, 4.7 on B-trees, or 4.8) and 6 (Not including: sections 6.3.4 & 6.4-6.9).

---