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

Midterm Exam #2, Friday, Nov 18, 2011

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.
• Disjoint Union/Find - Dynamic equivalence relations, Up-tree representation, union, find, 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.
• Graphs - definitions, adjacency list and adjacency matrix representations [Graphs I lecture, Weiss 9.1]
• Graphs - topological sort [Graphs II lecture (up through slide 25, material on graph traversals is not included) , Weiss 9.2]

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 II samples: (Note: B-trees, Binomial Queues, Leftist Heaps and Skew Heaps appear on some sample midterms but will NOT be on our midterm)

• Sample Midterm II (Key to Sample Midterm II)
• Midterm II from 08sp (Key to Midterm II from 08sp)
• Midterm II from 09wi (Key to Midterm II from 09wi)
• Midterm II from 09sp (Key to Midterm II from 09sp)
• Midterm II from 10sp (Key to Midterm II from 10sp)
• Midterm II from 10au (Key to Midterm II from 10au)
• Midterm II from 11au (Key to Midterm II from 11au)

Midterm I samples: (some of these might contain a few relevant questions)

• Sample Midterm I (Solution to Sample Midterm I) (Extra steps written out for Sample Midterm I)
• Midterm I from 08sp (Solution to Midterm I from 08sp)
• Midterm I from 09wi (Solution to Midterm I from 09wi)
• Midterm I from 09sp (Solution to Midterm I from 09sp) (contains hashing questions)
• Midterm I from 10sp (Solution to Midterm I from 10sp)
• Midterm I from 10au (Solution to Midterm I from 10au)

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 topological sort, I will not expect that you have forgotten material from midterm #1 completely. For example, I could definitely 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.6 or 5.7), 6 (not 6.4, or 6.6-6.9), 8 (not 8.6), 9.1 and 9.2, and the lecture on Memory Hierarchy/Locality and data structures.

---