MCS-236: Relation-Based Structures / Graph Theory (Fall 2002)

Overview

A successful computer scientist or mathematician must reason logically, think abstractly, and argue convincingly in writing. In this course, we will study these core tools in the context of formal proofs in graph theory, a field of mathematics which plays a central role across all areas of computer science.

There are no formal prerequisites for the course, though the student should have had some exposure to thinking abstractly in mathematics; a solid calculus course would serve the typical student well.

Our text for the course, Douglas West's Introduction to Graph Theory, 2nd edition has excellent coverage in all areas of graph theory. As with most good math books, expect to spend time digesting each page of text. While studying, be sure to have a piece of scrap paper on which you can sketch small examples illustrating a definition or a theorem you've just read.

Reaching me

All office, phone and schedule information will be maintained on my web page. I'll try to keep it updated with any temporary changes to my schedule as well. In short, if my office door is open you are welcome; if I'm busy, we'll set up an appointment. Email and phone calls work, too.

All course handouts (and some supplementary materials) will also be available through the course web page, http://www.gustavus.edu/~wolfe/236/.

Honor

Students are encouraged to discuss the course, including issues raised by the assignments. However, the solutions to homework assignments should be individual original work unless otherwise specified. If an assignment makes you realize you don't understand the material, ask a fellow student a question designed to improve your understanding, not one designed to get the assignment done. To do otherwise is to cheat yourself out of understanding, as well as to be dishonorable.

Any cheating may lead to failure in the course and notification of the Dean. This includes copying anyone else's work, deliberately facilitating copying and failing to give credit for solutions not discovered on your own. Failure to cite a source (written or verbal) on any component of the course is considered cheating. Each citation should be specific: Do not merely say, ``I worked with so-and-so on this homework set.'' Each problem should have specific information spelling out the nature of the collaboration, such as, ``On problem #3, so-and-so helped me to find an algebra mistake.''

Assignments and Grading

There will be about 40 homework problems (25%), three exams (30%), one final (15%), a proof portfolio (15%) and a research paper (15%). If you get 85% or more of the points, you will earn an A, 80% for an A-, 75% for a B+ and down by 5 percentage points each to the lowest passing grade of 40% for a D. There is no curve. However, I reserve the right to subjectively adjust your final grade. Please see me if you have any question how you stand.

We will use a system of mastery homework problems in this course. Each homework set will be assigned with an initial due dates. On the due date, you should submit a thoughtful attempt at each problem on a separate page. If you know you haven't solved a problem yet, clearly write not yet solved at the top, followed by a short description of what you've tried so far. You can miss the initial due date 72 hours once and by 24 hours once; any more late will be heavily penalized. (This very liberal policy is intended to accommodate illness or conflict. Please do not ask for additional exceptions unless your situation is unusual.)

I will return the homework problems to you as quickly as I can, normally with only an indication of whether it is acceptable or needs more work. (Sometimes I may give a brief indication of what area it needs more work in.) If a problem needs more work, and you aren't sure what sort of work it still needs, you should treat that as an invitation to come talk with me about it. Once you've done the additional work, you may turn the problem in again. In fact, you may turn in each problem in as many times as you like before the start of the next exam review class until it is marked as acceptable. (We will typically discuss solutions to homeworks in detail when reviewing on the last class before each exam.) Your grade for the homework portion of the course will be based on the fraction of homework problems that you eventually did acceptably.

I encourage you to work with other students on the homework provided that you do so in such a way that every one in your group learns the material. The most effective way to do this is to first discuss each problem as a group and then have each person work on the problem individually. When you're done (or stuck) compare your work and discuss it. Remember that doing the homework is how you learn the material; and that you are not allowed to work cooperatively on tests.

If you do work with other students on the homework, I would like you to follow these guidelines:

  1. Each person should write up the answers independently.
  2. Each person should be able to work each one of the problems independently.
  3. Each person gives credit to the others who helped. (See Honor for the nature of the citation.)
Additionally, you may also write up a homeowork problem consisting of a proof cooperatively with one other student provided the following:
  1. Each of the two students must complete at least one draft of the problem submission, and
  2. You cannot work with any other one student on more than one problem writeup.

Writing is a significant component of this W-course. Writing assignments will take several forms. First, homework assignments will often require written proofs. These proofs will be checked for logical and grammatical accuracy, as well as for style and exposition. It is important to be able to express your mathematical thoughts in writing, using clear, well organized paragraphs comprised of English sentences. This means more than separating your equations with a few well placed ``Thus it follows that...'' or ``Plugging (a) into (b) shows that ...'' During the course we will work on writing mathematical prose effectively and clearly. In addition, you will be compiling a proof portfolio containing one example of each type of proof discussed. You will also be expected to write one expository paper. Details of the paper, including deadlines for drafts and revisions, will be described later in the course.

Grade disputes should be made before the final exam. I will fix obvious grading errors promptly (and will thank you for pointing them out). For students especially fond of debate, I reserve the right to regrade an entire assignment.

Syllabus

We will cover Chapters 1-7 as outlined on page xvi of the Preface under Design of Courses. Additionally, we will spend at least one additional week covering the material in Appendix A as needed.