COSC 4101.03 Advanced Data Structures
(x-listed COSC 5191.03)
Section A Fall Mon, Wed, Fri 16:30
Section M Winter Tue, Thu 14:30-16:00
The course discusses advanced data structures: heaps,
balanced binary search trees, hashing tables, red--black
trees, B--trees and their variants, structures for disjoint
sets, binomial heaps, Fibonacci heaps, finger trees,
persistent data structures, etc. When feasible, a
mathematical analysis of these structures will be
presented, with an emphasis on average case analysis
and amortized analysis. If time permits, some lower
bound techniques may be discussed, as well as NP-
completeness proof techniques and approximation
The course may include the following topics.
- Amortized and worst-case analysis of data structures.
- Data structuring paradigms: self-adjustment and
- Lists: self-adjustment with the move-to-front
- Search trees: splay trees, finger search trees.
- Heaps: skew heaps, fibinacci heaps.
- Union-find trees.
- Link-and-cut trees.
- Multidimentional data structures and dynamization.
Suggested reading: T.H.Cormen, C.E.Leiserson,
R.L.Rivest, Introduction to Algorithms, McGraw-Hill,
prerequisites, including COSC3101.03; MATH2320.03