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

The midterm2 as well as solution are here (mid2, soln).

Midterm Exam #2, Monday, Nov 16, 2009

Exam policies:

• Closed book, closed notes. No Calculators allowed.
• The exam begins promptly at 12:30 and ends at 13:20.

Topics covered:

• Binary Heaps - Findmin, Deletemin, Insert. Additional operations of increase, decrease, buildheap.
• D-heaps - Findmin, Deletemin, Insert. Additional operations of increase, decrease, buildheap.
• Hashing.  Properties of good hash functions.  Selecting hash table size.  Separate chaining and open addressing.  Linear Probing, Quadratic Probing, & Double Hashing to resolve collisions.  Rehashing, Extendible Hashing
• Sorting: Bubble Sort, Insertion sort, Selection sort, Heap sort, Merge sort, Quicksort. Lower bound on comparison sorting. Bucket sort, Radix sort. 
• Liftist Heap, Skew Heap, Disjoint Set, Memory Hierarchy.

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: (some of these contain questions on Heap/Hashing)

• Sample Midterm I (Solution to Sample Midterm I) (Extra steps written out for Sample Midterm I): Binary Min Heap
• Midterm I from 09wi (Solution to Midterm I from 09wi): Binary Min Heap
• Midterm I from 09sp (Solution to Midterm I from 09sp): Hashing

Midterm II samples: (contain questions on Heap/Hashing)

• Sample Midterm II (Key to Sample Midterm II): Heap and Binary Min Heap
• Midterm II from 08sp (Key to Midterm II from 08sp): Heap and Binary Min Heap
• Midterm II from 09wi (Key to Midterm II from 09wi): Heap and Binary Min Heap
• Midterm II from 09sp (Solution to Midterm II from 09sp): Binary Min Heap/D-Heap

Final samples: (contains questions on Heap/Hashing/Sorting)

• Sample Final (Key to Sample Final): Heap/Hashing/Sorting

Study suggestions:

• Do concrete problems from the book and re-work problems from lecture and HW.
• Be prepared to describe the running time of the operations on each data structure.

---