Midterm #2 Study Guide
CSE 373: Data Structures & Algorithms
Midterm Exam #2, Wednesday, Nov 17, 2010
- Closed book, closed
notes. No Calculators allowed.
- The exam begins promptly at
2:30 and ends at 3:20.
- Binary Heaps -
Findmin, Deletemin, Insert. Additional operations of increase, decrease,
- D-heaps - Findmin,
Deletemin, Insert. Additional operations of increase, decrease,
- Leftist Heaps and Skew
Heaps - Findmin, Deletemin, Insert.
Additional operations of merge.
- 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
- The memory
hierarchy. Temporal and spatial locality. Data
structure choice and the memory hierarchy.
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 and Binomial
Queues appear on some sample midterms but will NOT be on our midterm)
Midterm I samples: (some of these might
contain a few relevant questions)
- 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
- Although the focus
will be on material from lecture that was not covered on midterm #1 up
through the Memory Hierarchy (temporal and spatial locality), 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.8 or 6.9) and 8
(not 8.6) and the lecture on Memory Hierarchy/Locality and data