COMP 4420 - winter 2017

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.

instructor: Steph Durocher
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:

  • 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
See this course outline for a detailed course description.


The following book is strongly recommended and is available at the University of Manitoba bookstore:

Introduction to Algorithms, third edition, by Cormen, Leiserson, Rivest, and Stein, MIT Press, 2009. (umanitoba ebook link)

The following books are useful references available on reserve at the Sciences and Technology Library:

Algorithms and Data Structures, by Mehlhorn and Sanders, Springer, 2008. (umanitoba ebook link)

The Algorithm Design Manual, second edition, by Skiena, Springer, 2008. (umanitoba ebook link)

Advanded Data Structures, by Brass, Cambridge, 2008.

Open Data Structures, by Morin, Athabasca University Press, 2013.

Most Springer publications are available online at SpringerLink through the University of Manitoba Library.


The References page has been updated with links to ideas for project topics.

Assignment 2 is now available.

last updated February 18, 2017

Important Dates

Feb 20-24midterm break - no class
Mar 1assignment 2 due
Mar 6midterm exam
Mar 15project proposal due
Mar 22assignment 3 due
Mar 29quiz 2
Mar 31VW deadline
Apr 5assignment 4 due
Apr 14Good Friday - no class
Apr 21project reports due
Apr 21classes end
Apr 29exam period ends