Office hours:

• Tuesday 10:30 - 11:30 am
• Wednesday 11 am - noon
• Thursday 10:30 - 11:30 am
• Other times by appointment
  

Required Text:  

• Gary Chartrand & Ping Zhang, Introduction to Graph Theory, McGraw Hill, 2005.

Goals:   At the conclusion of this course, students should have a basic understanding of terminology associated with Graph Theory including the myriad topics and applications arising from this subject. Students should also know how to manipulate graphs and graph algorithms through programming.

Prerequisite:   CS 110 (Introduction to Programming) and Math 250 (Discrete Mathematics).

Topics to be covered (and tentative course schedule):

Weeks 1 - 2:	Introduction to Graph Theory (Ch. 1-2)
Weeks 3-5:	Isomorphic Graphs, Trees & Connectivity (Ch. 3-5)
Week 5:	Midterm - Thursday, February 3rd, 2005
Week 6:	Traversability and Digraphs (Ch. 6-7)
Week 7:	Matchings and Factorization (Ch. 8)
Week 8:	Planarity, Coloring and Ramsey Numbers (Ch. 9-11)
Week 9:	Distance and Domination (Ch. 12-13)
Week 10:	Student Presentations on applications from Graph Theory; Evaluation
Exam Week:	Final Exam on Monday, March 14, 8-11 am

Grades will be based on:

The format of this class will be tailored to the class and may be run as a seminar instead of as a traditional lecture style course. Since this class will be extremely participatory your attendance is crucial. Please be sure to talk to me in advance if you must miss any class meetings.

Reading assignments, announcements, links to class presentations, and other material will be made available on the CS 484 homepage:

Students are responsible for checking this resource frequently.

Collaboration and the Honor System:

This course operates in accordance with the principles of the Kalamazoo College Honor System: responsibility for personal behavior, independent thought, respect for others, and environmental responsibility. In particular, academic integrity is a fundamental principle of scholarship. Representing someone else's work as your own, in any form, constitutes academic dishonesty. Unauthorized collaboration and receiving help from others outside the bounds permitted by the instructor are also violations of the College honor code. You are responsible for working within the permitted bounds, and acknowledging any help from others or contributions from other sources.

Programming Projects:

Both of the programming projects can be done individually or in teams of 2 or 3. Your responsibilities under the Honor Code include contributing to the team in all ways, documenting everyone who worked on any piece of code, and acknowledging all help you and your team receive from any source, including books, articles, classmates, your instructor, etc. I may occasionally ask all the members of a group to evaluate the effort and effectiveness of the other members of their group.

Homework assignments: You may discuss the requirements, concepts, and overall strategies related to homework assignments with your classmates, but you should write the solutions individually, using your own words. Organizing and writing up the solutions on your own ensures that you really understand the material. Submitting someone else's work does not help you learn and constitutes academic dishonesty. As always, you should acknowledge your collaborative discussions with your solutions.

Class presentations: These presentations should represent your own analysis and synthesis of ideas drawn from one or more sources. Your presentation should indicate clearly the source(s) you used or about which you are reporting.

Attendance and Participation:

Regular attendance and fully engaged participation is crucial in this course. Active participation in the class means being on time, being prepared, listening to others, contributing ideas of your own, and asking questions as they come up. Student presentations in this course will be as important as presentations by the instructor. You should obviously prepare for your own presentations carefully, but you should also attend to your classmates' presentations thoughtfully and actively.