Time:
MR 12:00-1:50pm
Location: Carnegie 201
Textbook: "Introduction to Graph
Theory", Chartrand & Zhang Supplementary Texts:
"Introduction
to Graph
Theory", Douglas B. West; "Introduction to Algorithms", Cormen,
Leisserson, Rivest and Stein
Prerequisites: Either (a
basic discrete math course such as MATH 2800) or ((working knowledge of
sets and logic, equivalence relations and functions, and methods of
proof) and (permission of the instructor)). You may want to go over
Appendices 1-3 in the textbook before the semester. Though not
required, knowledge of algorithm design and analysis techniques can be
helpful.
Grading: 4 homeworks (10% each) , a
midterm (25%), a final (30%) and class participation (5%).
There is a project assignment which is required for graduate students
and optional for undergraduates.
The project involves identifying an application area of graph
theory, preparing a 15 minute presentation on
the area (motivation, significance), and how graph theory is used. The
presentations will take place during the last couple of lectures. On
the day of the presentation, you are also required to submit an
approximately 2 page report on your project. There is no separate grade
for the course project. It will count toward the 5% class
participation.
To summarize, the project involves the following steps: (1) Pick a
topic and submit a half-page description to sign-up (deadline: April 2)
(2) Prepare your slides and email them to me
before the day of presentation (3) Presentation (4) Report.
Late homework policy:
Homework specific.
The assignment of letter grades will be according to a curve. Cutoffs
TBA.
Hw3 is out. [04/02]. Note the correction in Question 5:
"Prove that G has a matching that saturates S union T".
Homework 2 solutions
have been posted [03/17].
Homework 2 and Midterm grades
have been posted [03/14].
You can go to Nikhil's office hours to take a look at your graded
midterms.
Homework 1 solutions as well as a document summarizing common
mistakes is available through webct [Posted: 02/24].
Information about the midterm: the midterm is closed book. You
are allowed to bring a single copy sheet which contains only
definitions (i.e. no theorems).
WebCT page is up and running.
First homework grades and solutions to be posted shortly.