SUNY Geneseo Department of Mathematics
Fall 2015
Prof. Doug Baldwin
Last modified August 28, 2015
Time and Place: TR 8:30 - 9:45, South 336
Final Meeting: Wednesday, December 16, 12:00 Noon
Instructor: Doug Baldwin
Office: South 307
Phone: 245-5659
Email: baldwin@geneseo.edu
Office Hours: Any time Monday through Friday, 8:00 AM to 5:00 PM, when I’m not committed
to something else. See my
Calendar for details and to make appointments electronically. You don’t need to make
appointments to see me, but may if you want to be sure I’ll be available.
Web Pages:
Lecture Notes: http://www.geneseo.edu/~baldwin/math303/fall2015/lectures.php
Exercises: http://www.geneseo.edu/~baldwin/math303/fall2015/exercises.php
Some problems take longer to solve than others—you’ve probably known this for most of your life. Computational complexity, broadly defined, is the area of mathematics and computer science that gives a precise mathematical meaning to this statement, thereby opening it to mathematical analysis—for example, providing ways to prove that two problems are of equivalent difficulty. More specifically, computational complexity involves (1) the realization that problems group into “classes” of approximately equal difficulty, and (2) the study of relationships between these classes. The good news from computational complexity is that many problems people need to solve are in a class that has very fast solutions; the bad news is that many other important problems are in a class that seems only to have unusably slow solutions; the surprising news is that no-one knows whether it is possible to collapse the latter class into the former, even though all it would take to do so is a fast solution to one problem. This course develops an introductory but nonetheless fairly detailed understanding of these and similar claims and the mathematics that supports them.
Prerequisite(s): Math 239
Learning Outcomes: On completing this course, students who meet expectations will be able to…
The (required) textbook for this course is
Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms (3rd ed.)
The following dates are best estimates. They may well change as students’ actual needs become apparent. Refer to the Web version of this syllabus for the most current information, I will keep it as up-to-date as possible:
| Sep. 1 | Introduction |
| Sep. 3 - Oct. 15 | Analysis of Individual Algorithms |
| Oct. 20 | Hour Exam 1 |
| Oct. 22 - Nov. 3 | Analysis of Problems |
| Nov. 5 | Hour Exam 2 |
| Nov. 10 - Dec. 3 | P, NP, and NP-Completeness |
| Dec. 8 - Dec. 10 | Complexity Classes Beyond NP |
| Dec. 16 | Final Exam |
Your grade for this course will be calculated from your grades on exercises, exams, etc. as follows:
| Final | 30% |
| Hour Exams (2) | 25% each |
| Problem Sets (8 - 12) | 15% |
| Participation | 5% |
In determining numeric grades for individual assignments, questions, etc., I start with the idea that meeting my expectations for a solution is worth 80% of the grade. I award the other 20% for exceeding my expectations in various ways (e.g., having an unusually elegant or insightful solution, or expressing it particularly clearly, or doing unrequested out-of-class research to develop it, etc.); I usually award 10 percentage points for almost anything that somehow exceeds expectations, and the last 10 for having a solution that is truly perfect. I deliberately make the last 10 percentage points extremely hard to get, on the grounds that in any course there will be some students who routinely earn 90% on everything, and I want even them to have something to strive for. I grade work that falls below my expectations as either meeting about half of them, three quarters, one quarter, or none, and assign numeric grades accordingly: 60% for work that meets three quarters of my expectations, 40% for work that meets half of my expectations, etc. This relatively coarse grading scheme is fairer, more consistent, and easier to implement than one that tries to make finer distinctions.
This grading scheme produces numeric grades noticeably lower than traditional grading does. I take this into account when I convert numeric grades to letter grades. The general guideline I use for letter grades is that meeting my expectations throughout a course earns a B or B+. Noticeably exceeding my expectations earns some sort of A (i.e., A- or A), meeting most but clearly not all some sort of C, trying but failing to meet most expectations some sort of D, and apparently not even trying earns an E. I set the exact numeric cut-offs for letter grades at the end of the course, when I have an overall sense of how realistic my expectations were for a class as a whole. This syllabus thus cannot tell you exactly what percentage grade will count as an A, a B, etc. However, in my past courses the B+ to A- cutoff has typically fallen somewhere in the mid to upper 80s, the C+ to B- cutoff somewhere around 60, and the D to C- cutoff in the mid-40s to mid-50s. I will be delighted to talk with you at any time during the semester about your individual grades and give you my estimate of how they will eventually translate into a letter grade.
I will accept exercise solutions that are turned in late, but with a 10% per day compound late penalty. For example, homework turned in 1 day late gets 10% taken off its grade; homework turned in 2 days late gets 10% taken off for the first day, then 10% of what’s left gets taken off for the second day. Similarly for 3 days, 4 days, and so forth. I round grades to the nearest whole number, so it is possible for something to be so late that its grade rounds to 0.
I do not normally give make-up exams.
I may allow make-up exams or extensions on exercises if (1) the make-up or extension is necessitated by circumstances truly beyond your control, and (2) you ask for it as early as possible. At my discretion, I may require proof of the “circumstances beyond your control” before granting a make-up exam or extension.
Assignments in this course are learning exercises, not tests of what you know. You are therefore welcome to work on them in small groups, unless specifically told otherwise in the assignment handout—a well-managed group makes a successful, and thus more educational, project more likely.
In order to avoid confusion when people work together, please indicate clearly what work is yours and what comes from other sources on everything you hand in. The appropriate “indication” depends on how much work is yours and how distinguishable it is from your collaborators’. At one extreme, if a group of people work together on all parts of an assignment, they could hand in one solution with all their names, and a brief statement of what each person contributed, on it. At the other extreme, if you do most of an assignment on your own but get a specific idea from someone else, you might just include a comment or footnote to the effect of “this idea comes from Betty Smith” in whatever you hand in. The bottom line is that everything you take credit for must include some identifiable contribution by you, and you should never claim credit for work or ideas that aren’t yours. I’ll be glad to advise you on what I consider appropriate forms and acknowledgements of collaboration in specific cases if you wish.
Please note that tests are tests of what you know, and working together on them is explicitly forbidden. This means that if you take advantage of the collaboration policy to avoid doing your share of the work on the exercises, you will probably discover too late that you haven’t learned enough to do very well on the tests.
I will penalize violations of this policy. The severity of the penalty will depend on the severity of the violation.
SUNY Geneseo will make reasonable accommodations for persons with documented physical, emotional, or cognitive disabilities. Accommodations will be made for medical conditions related to pregnancy or parenting. Students should contact Dean Buggie-Hunt in the Office of Disability Services (tbuggieh@geneseo.edu or 585-245-5112) and their faculty to discuss needed accommodations as early as possible in the semester.