CSI 5165 (COMP 5709) Fall 2015 course description

WEB PAGE: http://www.eecs.uottawa.ca/~lucia/courses/5165-15/
PROFESSOR: Lucia Moura
tel: 562-5800 ext. 6678
email: lucia@eecs.uottawa.ca
OFFICE HOURS: Office: SITE 5-027 
Office Hours: Mondays 1:30-2:30
LECTURES: Mondays 10:00AM-1:00PM (LPR285)
TEXTBOOK: Textbook:
[KS] D. Kreher and D. Stinson, "Combinatorial Algorithms: generation, enumeration and search", CRC Press, 1998.

Reference book:
[KO] P. Kaski and P. Ostergard, Classification algorithms for codes and designs, Springer, 2006.
Paper copy available at Carleton University library.
OttawaU electronic resources:
http://orbis.uottawa.ca/search/t?SEARCH=classification+algorithms+for+codes+and+designs&sort=&submit=Search/
go to "connect to Springer resource" for individual chapter's pdf"
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]
  2. [B] Exhaustive search and exhaustive generation algorithms (backtracking, branch-and bound). -- [KS, Chapter 4]
  3. [H] Heuristic search algorithms (hill climbing, simulated annealing, tabu search, genetic algorithms). -- [KS, Chapter 5]
  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: 24% Assignments 3 @ 8 each
25% Midterm Test
3% Project proposal (up to 1 page)
15% Project report (10-15 pages)
8% Project Talk (20 minute)
25% Final Exam
IMPORTANT
DATES:

weight: due date: (tentative)
Assignment 1 8%  Oct 13
Project proposal 3%  week of Oct 19
Assignment 2 8%  Nov 2
Midterm 25%  week of Nov 9
Assignment 3 8%  Nov 23
Project Talk 8%  Dec 9
Final Exam 25%  December 10-22
Project Report 15%  December (to be decided)

Dates from the University of Ottawa Academic Calendar:
First lecture: September 14
Holiday: October 12 (Monday)
Study break: October 25-31
Last date to drop: November 20
Last lecture: December 9 Wed follows Monday schedule (Note: lecture on Dec 7 and Dec 9)