Department of Computer Science

Course directors:
X. Deng (Fall)
T. Papadakis (Winter)
Implementation details

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 algorithms.

The course may include the following topics.

Texts: t.b.a. Suggested reading: T.H.Cormen, C.E.Leiserson, R.L.Rivest, Introduction to Algorithms, McGraw-Hill, 1990.

Prerequisites: general prerequisites, including COSC3101.03; MATH2320.03