Graphs and Algorithms

Course Outline and Roass Document

Last update = Jan 4/2018.
Topics to be covered

  1. Graph Isomorphism
  2. Graph Connectivity
  3. Max Flow
  4. Graph Colouring
  5. Hamilton cycles
  6. Graph Planarity
  7. Graphs on other surfaces
  8. Digraphs

Assignments

There will be 3 assignments, each worth 10% of the final grade.
There will be an individual coding project to implement a significant algorithm.
The project will be worth 25% of the final grade.
Each student is expected to give a 20 minute presentation on his/her project in the last two weeks of classes.
There will be a final exam (3 hours), worth 45% of the final the grade.

As this is a joint graduate/undergraduate course (7750/4060),
the assignments for the graduate and undergraduate students will be slightly different.

Programming is to be done in C, C++, Java, or Python.
Please write your own classes.
Use arrays and pointers.
Do not use a "visual" programming environment.