21-110 Problem Solving and Recreational Mathematics

Spring 2007


Topics

Euler Circuits and Euler Paths in Graphs
Voting Theory and Multicandidate Election Methods
Probability Theory and Expected Value
A Little Bit of Number Theory
Hamilton Circuits in Graphs
Weighted Graphs, Complete Hamilton Circuits, and Shortest Paths
Bipartiteness, Planarity and Other Properties in Graphs
Weighted Voting Systems and Power
Optimization and Linear Programming

Professor's Information

Dr. John Tolle
Office: Wean Hall 6124
e-mail: tolle+@andrew.cmu.edu
Telephone: 412-268-8419

Professor's Appearance

Generally haggard; frightening to small children

Philosophy

In this course we take the view that the final answer to a problem is the least interesting part of the problem's solution. For example, suppose one is asked how many different seating arrangements there are for 50 individuals in a 100-seat auditorium. Does anyone really care? Probably not, so the numerical answer is of little interest to anyone. What is interesting, though, is the problem-solving strategy one uses to derive the answer. Even more interesting would be the revelation that the very same strategy used to solve the 50 person / 100 seat problem can still be used if the data are changed (54 persons and 119 seats; 131 persons and 136 seats, etc.). Still more interesting would be a way to recast the problem involving more individuals than available seats so that the same strategy still applies.

So in all of your written work in this class, we shall be interested in the strategies you use to arrive at results. The habits you may have acquired in previous mathematics courses, such as scribbling strings of equations and circling a final result, should be abandoned in favor of providing clear written explanation and justification of your work.

"The primary question is not what we know, but how we know it." -- Aristotle

Projects

60% of your grade is determined by the completion of writing or problem-solving projects. You will do three such projects during the semester, in which you study a challenging problem, formulate a method for its solution, and then present the solution in clearly written form. Alternatively, you may choose (only once) a project which involves writing an essay on some person or topic we have studied, or a review of a book that I recommend. The link below is the suggested projects list. Guidelines on how to submit a successful write-up are given there. You are also welcome to propose your own project; I must approve it, of course. You must submit one rough draft for each project, and I will look over your draft and suggest revisions.

Since several of you may opt to do the same project, you are not allowed to discuss your work with each other. However, you may consult me, and you may discuss the projects with anyone else who is not enrolled in the course, provided that person is not a past 21-110 student who has done the same project you are working on.

Project Timetable

Project 1 first draft due Friday, February 8
Project 2 first draft due Friday, March 21
Project 3 first draft due Monday, April 21

Please note: The dates above are the latest dates on which you can submit a draft. You may turn in a draft any time before the due date, and in that case, you will get your draft back earlier and have more time to revise the work. You may turn in the final version of any project during any class session. The closing date for final versions of all projects is Friday, May 2.

Project List

In-Class Points

The in-class component of the course will count for 40% of your final grade. Regular attendance is crucial. Missing, say, one class every two weeks has a surprisingly detrimental effect on your in-class average. In nearly every class meeting you will turn in written work, each item contributing in-class points to your total. Sometimes you will be given short assignments to be turned in at the next class meeting. The total number of in-class points that may be earned will probably be over 200. At the end of the semester, your In-Class Average (let's call it ICA) will be computed as follows:

                                     # of in-class points you earned
                          ICA  =  ----------------------------------------- ,
                                  92% of total # of in-class points offered

or 100, whichever is lower. As an example, suppose 226 in-class points were offered over the course of the semester. Take 92% of this total, to obtain 207.92. If you earned 208 or more in-class points, your ICA will be 100. If you earned 207 or fewer in-class points, take your total and divide by 207.92. So if you earned 160 points, your ICA is 160/207.92 = 76.95%. This curious 92% adjustment is in place to recognize the occasional inevitability of missing class, due to illness, university-sponsored trip, religious observance, or some other higher priority in your life. Hence it is not necessary to provide me with documentation of the legitimacy of such absences except in case of extended illness, because the 92% adjustment automatically excuses you from 8% of the course meetings.

Barring these factors, however, you are wise to consciously commit yourself to attending every single class unless something absolutely unavoidable happens, because a better way to use this 8% provision is as a buffer against those times when, on individual in-class activities, you do not score the full number of points. Also, understand that there are no make-ups on in-class work. If you miss a class for any reason, you miss the points for any in-class work done that day. It is also possible for the following to happen: Let's say you miss class on a Monday, and then on Wednesday, at the very beginning of class, some assignment is given which relies on the content of Monday's class. It is possible that you won't be able to earn full points for that assignment, even though it is given on a day you are present. However, to consider a different scenario, suppose a short assignment is given on a Monday to be turned in at the beginning of class Wednesday, and you are absent Wednesday. You may still submit the assignment at the beginning of class on the day you return.

So with these considerations in mind, you are wise to recognize the 8% provision as (1) a matter of convenience to all of us, (2) a reward mechanism for the conscientious, and (3) a mercy mechanism for the unfortunate. But it is not a license for the unconscientious.


FINAL AVERAGE:  computed according to the following weights:



                             20% Project 1
                             20% Project 2
                             20% Project 3
                             40% ICA

The grade scale is then as follows:

                           90.00000 - 100.00000   A
                           80.00000 - 89.99999    B
                           70.00000 - 79.99999    C
                           60.00000 - 69.99999    D
                            0.00000 - 59.99999    R