COMP 4420 - Advanced Design and Analysis of Algorithms
COMP 4420: Algorithm design with emphasis on formal techniques in analysis
and proof of correctness.
Computational geometry, pattern matching, scheduling, numeric algorithms,
probabilistic algorithms, approximation algorithms and other topics.
office hour: Tuesday 9:00-10:00 am in EITC E2-412.
lectures: 9:30 - 10:20 am on Monday, Wednesday, & Friday in EITC E2-304.
prerequisites: COMP 3170
and STAT 1000 or STAT 1001
This calendar lists course-related events for COMP 4420:
Course Objectives and Topics Covered
A primary objective of COMP 4420 is to allow students to discover
advanced data structures and their associated algorithms
from a theoretical perspective.
Students will learn new techniques for solving specific problems
more efficiently and for analyzing space and time requirements.
Several of the data structures we discuss are recent developments that
are not yet found in computer science textbooks.
The emphasis is on theoretical analysis of the
data structures and algorithms.
If you like recurrence relations, double logarithms,
and worst-case linear-time selection,
you wonder whether it is possible to make balanced search trees more efficient,
and you feel O(log n / log log n) is a significant improvement over O(log n),
then this course is for you.
Students are expected to have a strong background in theoretical computer
science (e.g., A or A+ in COMP 3170).
Topics will include:
See this course outline for
a detailed course description.
- Advanced dictionary data structures: van Emde Boas trees, y-fast tries,
cuckoo hashing, splay trees, skip lists, union-find
- Array Range Query: wavelet trees, Cartesian trees, range minimum query,
bitwise rank and select
- Resizeable Arrays
- Geometric Data Structures: range trees, R-trees, quadtrees, kd-trees
- Online Algorithms: paging, ski rental, stock market, load balancing
The following book is strongly recommended and is
available at the
University of Manitoba
to Algorithms, third edition, by Cormen, Leiserson, Rivest, and Stein,
MIT Press, 2009.
The following books are useful references available on reserve at
the Sciences and Technology Library:
and Data Structures, by Mehlhorn and Sanders,
(umanitoba ebook link)
The Algorithm Design Manual,
second edition, by Skiena, Springer, 2008.
(umanitoba ebook link)
Data Structures, by Brass,
Data Structures, by Morin,
Most Springer publications are available online at
through the University of