| Instructor: | Professor Goldberg |
| Class Hours and Place: | Mon - Thur 12:00 - 1:50; Carnegie 113 |
| Office Hours: | Thursday, 2:00 - 3:00; Amos Eaton 108 |
| Tel: | 276-2609 |
| e-mail: | goldberg@cs.rpi.edu |
| url: | http://www.cs.rpi.edu/~goldberg/08-GT/index.html |
| TA: | Chris Willmore |
| Tel: | 276-8275 |
| e-mail: | willmc@cs.rpi.edu |
| Office Hours: | Wed 2:00 - 4:00 |
| Office: | 206, Amos Eaton |
| Room for office hour: | Amos Eaton, 119 |
| Textbook: | Introduction to Graph Theory, Second edition |
| by Douglas B. West, Prentice Hall 2001. | |
| Prerequisite: | MATH-2800 or equivalent |
| READ |
Graph Theory is a delightful playground for the exploration of proof technique in discrete mathematics, and its results have applications in many areas of the computing, social, and natural sciences. D. West, Introduction to Graph Theory
(PLEASE READ IT CAREFULLY).
Students are encouraged to attend all classes. Your active in-class participation will be a substantial part of your learning process, and will be taken into consideration when final grades are determined. In-classes quizzes will be given with some regularity. Helpful exercises will often be recommended. Your solutions to them will not be graded, but you are welcome to consult with me or the TA to check your solutions.Your grade will be based on several quizzes (up to ten) and two tests, the first of them in the middle of the term, and the second at the end of the term.
Quizzes Midterm test Final test 30% 30% 40% The letter grade, to be reported to the registrar, will be assigned based on your final score according to the following rule:
A A- B+ B B- C+ C C- D+ D F >95 91 - 95 87 - 91 83 - 87 80 - 83 76 - 80 72 - 76 68 - 72 64 - 68 60 - 64 < 60
This course discusses fundamental concepts of Graph Theory and its applications in computer, social, and natural sciences. The topics include graphs as models; representation of graphs; trees; distances; matchings; connectivity; flows in networks; colorings; hamiltonian cycles; and planarity. All concepts, methods, and applications will be presented through a sequence of exercises and problems, some of which might be done with the help of a program nauty. An important objective of the course is the development of problem solving skills of the students in the area of discrete mathematics and its applications.
For each in-class quiz, the students attending the class will be temporarily split into two member teams. The class will be given a number of problems, each worth one or two points towards the final grade. Every team will present a short written solution to every problem (and the names of the participants). After the write-ups are collected, if time permitts the solutions will be presented by the instructor. Both tests are open-textbook but close-notes; extensive notes in the textbook may result in removing the textbook from the test. Unless one makes a prior arrangement with the instructor or have a medical excuse supported by a document from a doctor, there will be no makeups for a quiz or a test. Students who know they are going to miss a test must notify me in advance. Special circumstances can be accommodated if I am notified about them in advance.