Evaluation

Labs: Each Lab will be worth the same and lab problems will be posted on the course web page approximately one week before the lab in which it is to be marked and handed in. You should attempt these problems before the lab. The problems will be taken up in the lab period, where you will be encouraged to work on them.

Assignments There will be a series of (roughly) bi-weekly programming assignments. These will generally be implementations of graph algorithms related to the course. These (programming) assignments will be ``auto-marked", which means that you will not be marked on style of code, but rather performance and in some cases efficiency. All assignments will be submitted in C.

Cooperation Through the term you will be required to submit work for the labs and assignments, this work should be your own. You are however allowed to discuss general methods algorithms and strategies for solving Lab problems or doing assignments with your fellow students.

Many of the algorithms discussed will be available on the internet. Please refrain from using publicly available source, though you can use the net for ideas about how to takle a problem or assignment.

Late Assignments A late penalty of $-3^n$ marks (out of 100) will be removed, where $n$ is the number of school days (Monday to Friday) an assignment is late by.

Missed Labs and Tests: Students who cannot be present for a test or exam because of illness must contact their instructor or the department by phone or in person on or before their first day back at school. They must also submit a printout of the Ryerson Student Medical Certificate filled out by their doctor.

Besides illness, only very serious reasons, properly documented, can be considered as valid excuses for missing a test or exam. If documentation is not received the test or exam mark will be zero.

Course

Teaching modes: 3 hrs. Lectures / 1 hr. Lab per week.

Course Website: http://www.scs.ryerson.ca/~mth607 (you're reading it!)

The web pages associated with this course contain some vital information, Homework exercises, Lab problems, Assignments and more. The contents may be updated from time to time, and so you should be checking it regularly.

It will be assumed throughout the course that students are familiar with the contents of the home page.

Learning Objectives The aim of the course is to introduce the student to the theory of graphs, particularly algorithmic graph theory. The student will learn a number of standard and powerful algorithms, as well as demonstrating methodologies in graph techniques. In addition the student will be introduced to the use of graphs in the solution of complex problems. Graph theory has become one of the major tools for the design and analysis of algorithms, as well as the focus of much interest in theoretical computer science.

Calendar Description: Introduction to graph theory and its applications with an emphasis on algorithmic structure. Topics may include graphs, digraphs and subgraphs, representation of graphs, breadth first and depth first search, connectivity, paths, trees, circuits and cycles, planar graphs flows and networks, matchings, colourings, hypergraphs, intractability and random algorithms. {Prerequisite:} MTH 110

Notes:

Generally the use of email for material relating to the course is discouraged. The reason for this is that discussing mathematics by (text based) email quickly becomes extremely arduous. A five minute conversation is quickly transformed into hours of painstaking explanations. On the other hand for simple questions relating to course management etc. email may be appropriate.

Student grades for this course may be posted (on the web or otherwise) by student number with the first two digits removed, as per academic council policy 145 section 2.2f. Students who do not wish to have their grades posted in this manner must inform the instructor in writing.

Students will receive their final course grades only from the Registrar, final course grades may not be posted or disclosed anywhere by an instructor.

Students are reminded that they are required to adhere to all relevant University policies, such as the Student Code of Academic Conduct.

Instructor Information