Algorithmic Graph Theory
MATH 542 Fall 2006 course information
Instructor: Dr. André Kündgen
Email: akundgen@csusm.edu
Office: 339 Science Hall 2
Office phone: (760) 750-8070
Office hours: Thursdays 2:45-3:45 PM (when classes are in session),
or by appointment.
The easiest way to make an appointment or reach me in general
is by email.
Lectures: Tuesday, Thursday 4:00-5:15 PM (308 Science Hall 2).
CRN: 42071
Webpage:
http://courses.csusm.edu/math542ak/
The course webpage contains links to useful information,
like the homework assignments, general announcements,
and clarifications regarding the homework.
You should check it at least once a week.
Textbook
D. Jungnickel,
Graphs, Networks and Algorithms 2nd edition, Springer Verlag (2005),
ISBN 3-540-21905-6.
Prerequisites
A certain amount of mathematical maturity is
necessary for this course. MATH 350, MATH 370 or a similar
discrete mathematics course that stresses the ability to understand and
write proofs is required. It is also sufficient, and definitely helpful,
if you have already taken a more
advanced course in discrete mathematics like MATH 472, MATH 474,
MATH 540 or MATH 544.
The course is open to upper level undergraduate students as
well as graduate students. No knowledge in graph theory or algorithms
is required, since we will develop everything we need from first
principles.
Grading Policies
The numerical scores of all exams and assignments will be used in computing
final score that will determine your final letter grade:
| Homework |
20% |
| Midterm exam |
25% |
| Presentation |
25% |
| Final exam |
30% |
|
| Letter grade |
Numerical grade |
| A | 85-100 |
| B | 70-84 |
| C | 60-69 |
| D | 50-59 |
| F | 00-49 |
|
There will be around 5 homework assignments and a detailed
homework policy can be found on the web.
Important Dates
| August 24: | First day of classes |
| October 12?: | Midterm exam |
| November 23: | Thanksgiving (no classes) |
| December 7: | Last day of classes |
| December 12: | Final exam, 4:00-6:00PM |
Course content
If you plan a car trip through 30 cities, starting and ending
in San Marcos, then it is obvious that there is SOME order in which
you should visit the cities in order to minimize the number of
miles you have to drive. How do you find this order? Do you
need to try all 1032 tours to determine which one is
shortest, or is there a smarter way of doing this?
The goal of this course is to tackle many problems of this type:
Optimization questions
that can be expressed in the language of Graph Theory.
In some cases we will find efficient algorithms for solving a problem,
and in other cases we will prove that it is very unlikely that an
efficient algorithms will ever be found. (As a matter of fact you
would earn
$1,000,000 for finding a good algorithm for solving any one of these
hard problems.)
More specifically, we will try to cover my list of major theorems
and topics of algorithmic graph theory. A draft of this list
can be found on the course webpage. This list will be updated
as we go along.
Learning outcomes
Students in this course are expected to solve problems independently, to develop mathematical proofs in the area of algorithmic graph theory, and then to communicate their ideas orally and in writing. Connections to related areas of mathematics and other disciplines, especially theoretical computer science, are also developed.