CSI 5165 - Combinatorial Algorithms - Fall 2005

 
Professor :  Lucia Moura
Course Material:  Course Description and Outline (first handout).

Lectures notes:
  • Introduction (pdf,ps) - lecture 1.
  • Generating Elementary Combinatorial Objects (pdf,ps) - lectures 2,3,4,part 5.
  • Exhaustive Generation and Search: Backtracking and Branch-and-bound (pdf,ps)- lectures 5,6,7.
  • Heuristic Search (pdf,ps) - lectures 8,9.
  • Computing isomorphism (pdf,ps) - lectures 10,11,...

    Assignments: A1 (pdf,ps), A2 (pdf,ps)

    Abstracts of talks by students

    • Brief Description: The main theme of the course is algorithms for the generation, enumeration and search of combinatorial objects.
    Combinatorial objects/structures include: sets, lists, strings, permutations, graphs and set systems. 
    Topics:
    • Basic algorithms for ordering, ranking and unranking of basic combinatorial objects.
    • Exhaustive search and exhaustive generation algorithms (backtracking, branch-and bound).
    • Heuristic search algorithms (hill climbing, simulated annealing, tabu search, genetic algorithms).
    • Computing isomorphism. Isomorph-free generation. (isomorphism of graphs and set systems; computing invariants and certificates; exhaustive generation of complete (isomorph-free) lists of combinatorial objects.)
    The basic material can be found in the textbook: 
    D. Kreher and D. Stinson, "Combinatorial Algorithms: generation, enumeration and search", CRC Press, 1998.
    Advanced topics will be complemented with papers/book chapters.
    Focus of the course: Combinatorial problems arise in all areas of computer science, engineering and mathematics. Students will learn fundamental and advanced techniques for search and generation problems and choose a topic of their interest for a project. Ideally the project will be on the use of these techniques to solve problems on the student's area of research/interest. A typical project will involve reading research papers, and designing/implementing algorithms.

    Any questions about the course contents or the use of these techniques in specific problems/areas? Please, contact the instructor: lucia@site.uottawa.ca.