CSI 7160 - Advanced topics in the theory of computing - Fall 2002
Topic: Combinatorial Algorithms and Structures

Professor :  Lucia Moura
Course Material: 
 
Course Description and Outline (first handout)
Office hours with Professor during December:
Wednesdays 2:00-4:00 (Dec 4, 11, 18) or by appointment.
References and resources
Lecture schedule(sorry schedule not complete)
Assignments: A1 (ps,pdf) (sorry A2 and A3 not available online)
 
IMPORTANT: CLASSROOM CHANGE: room CBY-B202 starting September 13.

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.)
  • Other techniques for generation, enumeration and search.
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.