CSI 7106 FALL 2002 course description

Advanced topics in the theory of computing:
Combinatorial Algorithms and Structures

WEB PAGE: http://www.site.uottawa.ca/~lucia/courses/7160-02/
PROFESSOR: Lucia Moura
tel: 562-5800 ext. 6678
email: lucia@site.uottawa.ca
OFFICE HOURS: Office: SITE 5-027 
Fridays 13:30-14:30
(alternatives at a lower priority: Mondays 10:10-11:30, Thursdays 11:40-12:40)
LECTURES: Room: CBY B202; Time: Fridays 10:00-13:00
TEXTBOOK and Extra material: D. Kreher and D. Stinson, "Combinatorial Algorithms: generation, enumeration and search", CRC Press, 1998.
It will be available at: the University of Ottawa Bookstore ($136.25) by Sept 15.

References and resources will be posted at the page: http://www.site.uottawa.ca/~lucia/courses/7160-02/resources.html
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: find at least one example of a structure of a particular type.

    • 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. Basic algorithms for ordering, ranking and unranking of basic combinatorial objects. -- Chapters 2 and 3
    2. Exhaustive search and exhaustive generation algorithms (backtracking, branch-and bound). -- Chapter 4
    3. Heuristic search algorithms (hill climbing, simulated annealing, tabu search, genetic algorithms). -- Chapter 5
    4. Computing isomorphism (isomorphism of graphs and set systems; computing invariants and certificates) -- Chapter 7
    5. Isomorph-free generation (exhaustive generation of complete (isomorph-free) lists of combinatorial objects). -- papers
    6. Other techniques for generation, enumeration and search. -- papers
    MARKING SCHEME: 45% Assignments (3 @ 15% each)
    05% Project proposal (up to 1 page)
    40% Project (10-15 pages)
    10% Presentation (20 minute talk)
    IMPORTANT
    DATES:    		 Schedule of assignments, projects and due dates:
    weight: handout: due date:
    Assignment 1 15%  Sep 20  Oct 11 10:00 am 
    Assignment 2 15%  Oct 11  Nov 1 10:00 am 
    Project proposal 5%  Oct 25 10:00 am 
    Assignment 3 15%  Nov 1  Nov 22 10:00 am 
    Project 40%  Nov 29 10:00 am 
    Presentation 10%  Nov 29

    Dates from the Academic Calendar:
    First lecture: September 6
    Last date to drop: November 4
    Last lecture: November 29