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

Midterm Exam #2, Friday, February 27, 2009

Exam policies:

• Closed book, closed notes. No Calculators allowed.
• The exam begins promptly at 2:30 and ends at 3: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.
• Leftist Heaps and Skew Heaps - Findmin, Deletemin, Insert. Additional operations of merge, increase, decrease
• Disjoint Union/Find. Up-trees. Weighted union (union by size) and path compression.
• Dictionary ADT
• 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.
• The memory hierarchy. Temporal and spatial locality. Data structure choice and the memory hierarchy.

Sample midterm: (Note: no calculators will be allowed on our exam)

• Sample Midterm II (Note: We will not have any questions on Binomial Queues or B-trees on our midterm)
• Key to Sample Midterm II
• Midterm II from 08sp (Note: We will not have any questions on B-trees on our midterm)
• Key to Midterm II from 08sp
  
  
• Key to Midterm II from 09wi

Study suggestions:

• Do concrete problems from the book and re-work problems from lecture and HW.
• Practice all the operations on heaps, 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 Hashing the Memory Hierarchy (temporal and spatial locality), 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: Chapters: 5 (not 5.7), 6 (not 6.8), and 8.

---