|
|
|
|
|
Midterm #2 Study Guide
CSE 373: Data Structures & Algorithms - Autumn 2007
Midterm Exam #2, Wed, Nov 21, 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
- Dictionary ADT
- The memory hierarchy. Temporal and spatial locality. Data structure choice and the memory hierarchy.
- B-trees. Motivation, choice of M and L, Insert (no delete).
- Binary Heaps - Findmin, Deletemin, Insert. Additional operations of increase, decrease, buildheap.
- D-heaps - Findmin, Deletemin, Insert. Additional operations of increase, decrease, buildheap.
- Leftist Heaps and Skew Heaps - Findmin, Deletemin, Insert. Additional operations of merge, increase, decrease.
- Binomial Queues - Findmin, Deletemin, Insert. Additional operations of merge, increase, decrease.
- 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.
- Disjoint Union/Find. Up-trees. Weighted union (union by size) and path compression.
Sample Midterm II
Study Suggestions
- Do concrete problems from the book and re-work problems from lecture and HW.
- Practice all the operations on heaps, binomial queues, disjoint sets, hashing with various collision resolution strategies.
- Although the focus will be on material from lecture that was not covered on midterm #1 up through Disjoint sets, I will not expect that you have forgotten material from midterm #1 completely. For example, I could ask you to compare something to a data structure covered on midterm #1.
- Be prepared to describe the running time of the operations on each data structure.
- This material corresponds to: section 4.7, ahapters: 5, 6 and 8.
|
