CSE 373: Data Structures & Algorithms

Autumn 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: **

- 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:
**

- 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.