CSI 5165 Winter 2022 Combinatorial Algorithms

WEB PAGE: http://www.eecs.uottawa.ca/~lucia/courses/5165-22/
PROFESSOR: Lucia Moura
email: lmoura@uottawa.ca
OFFICE HOURS: Office Hours: Tuesdays 9:00-10:00AM (see brightspace Zoom)
LECTURES: Fridays 10:00AM-1:00PM (STE F0126- SITE building 800 Kind Edward; unless when re-scheduled online)
CONTACT: Lectures/Office Hours in Zoom; while online.
Materials and submissions in Brightspace.
TEXTBOOK: Main text:
[KS] D. Kreher and D. Stinson, "Combinatorial Algorithms: generation, enumeration and search", CRC Press, 1998.

Other texts:

  • [CA-4A] D. Knuth, The art of computer programming Vol 4A, Combinatorial Algorithms, Part 1, Addison Wesley, 2011.
  • [HM] M. Gendreau and J-Y Porvin, Handbook of Metaheuristics, 2nd Ed, Springer, 2010.
  • [KO] P. Kaski and P. Ostergard, Classification algorithms for codes and designs, Springer, 2006.
    (OttawaU has an electronic copy of [KO] available for download)
COURSE
OBJECTIVES:		 Combinatorial problems arise in many areas of computer science, engineering and mathematics. Combinatorial structures such as graphs and set systems are used to model many problems in computing.
In this course, we will study combinatorial algorithms to solve the following types of problem:
Generation: construct all combinatorial structures of a particular type.
Enumeration: compute the number of different combinatorial structures of a particular type.
Search/Optimization: find at least one example of a structure of a particular type; optimization can be viewed as a special case of search.
In the first part of the course, students will learn a wide range of techniques to solve these problems. In the second part, they will learn more advanced techniques as well as work on a project related to their research interests.
COURSE OUTLINE:
  1. [G] Generating elementary combinatorial objects. Basic algorithms for ordering, ranking and unranking of combinatorial objects such as sets, permutations, tuples, gray codes. -- [KS, Chapters 2 and 3] and [CA-4A]
  2. [B] Exhaustive search and exhaustive generation algorithms (backtracking, branch-and bound). -- [KS, Chapter 4] and [KO, Chapter 4.1]
  3. [H] Heuristic search algorithms (hill climbing, simulated annealing, tabu search, genetic algorithms). -- [KS, Chapter 5] and [HM]
  4. [I] Computing isomorphism (isomorphism of graphs and set systems; computing invariants and certificates) and Isomorph-free generation (exhaustive generation of complete (isomorph-free) lists of combinatorial objects) [KS,Chapter 7] and [KO, Chapter 3,4]
MARKING SCHEME: 45% Assignments 3 @ 15 each
3% Project proposal (1-2 pages): the project is individual, student choice with professor approval, research + your own work
11% Student Presentation (20 minute talk): talk teaching peers about topic not covered in lectures, can be related to project topic
11% Project Presentation (20 minute talk): talk presenting your project
30% Project report (10-15 pages paper): final report, article style
IMPORTANT
DATES:

weight: due date: (tentative)
Assignment 1 15%  Feb 9
Project proposal 5%  Feb 19
Assignment 2 15%  Mar 2
Student Presentation 10%  March 25
Assignment 3 15%  P1 Mar 16/P2 March 30
Project Presentation 10%  To be scheduled
Project Report 30%  April date (to be decided)

Dates from the University of Ottawa Academic Calendar:
First lecture: January 14, 2022
Study break/Reading week: February 20-26
Last date to drop: March 25
Last lecture: April 8, 2022