MATHEMATICS 152, FALL 2004METHODS OF DISCRETE MATHEMATICSLast revised: September 8, 2004Instructor: Paul BambergOffices: SC 423, 495-1748 and Quincy House 102, 493-3100. Quincy 102opens off the Quincy House courtyard, near the raised cubical library.Email: [email protected] Hours:• Tu 2:30-3:30 in Science Center 423• Tu 10AM-noon, Wed 9AM-2PM and Th 8AM-noon in Quincy 102 (phone3-3100 first).• Tu evenings in Quincy 102, but phone 3-3100 first)You are encouraged to come to office hours, especially to Quincy House, todiscuss your upcoming presentations.Early morning and evening availability are not guaranteed until the Red Soxare out of the playoffs.Course Website: http://www.courses.fas.harvard.edu/-math152 (That’sa tilde before math152)Goals and Prerequisites: This course will introduce you to a variety oftopics in higher mathematics that are “discrete” in the sense that they are notdependent on limits and approximation. Ideas from geometry, group theory,rings and fields, graph theory, linear algebra, combinatorics, and probabilitywill be studied, and surprising connections will emerge.You are expected to have a background in linear algebra (probably Math21b, but perhaps a course that you took elsewhere) and an interest in theo-retical mathematics. Previous experience with proofs is not ne cessary. One ofthe aims of the course is to introduce you to the techniques of proof in highermathematics.Because the subject matter of the course is discrete, calculus is irrelevant.Computing Assignments: If you are concentrating in Computer Science orApplied Mathematics, you will be encouraged to complete three programmingprojects in which you implement key mathematical ideas from the course ininteractive Web pages using PHP. There are detailed instructions for doingthe user interface in either Windows or Linux, but you will need programmingexperience (CS 50 or AP Computer Science) to implement the mathematics.As an alternative, for roughly half credit, you can implement just the math-ematics in programs with no user interface at all. PHP is an easy languageto learn, so no experience with it is necessary. You can see what the finished1projects will look like by following the link under Programming Projects onthe course Web site.If you program in C++ and have access to Microsoft Visual C++ or toKDevelop under Linux, you can do the projects in C++. There are detailedinstructions on the course Web site. If you choose to use Java, you are com-pletely on your own, but it has been done!Course Meetings: The course meets TTh from 1-2:30 P. M. in Science Center310. There will also be an additional weekly problem session led by the courseassistant, Vivian Bertseka. We will try to find a time for this session on lateMonday afternoon or early Monday evening that is convenient for everyone.The course will be run in a seminar style, with most of the topics presentedby students in the class. This means that your classmates will be counting onyou to prepare carefully and that you will gain lots of experience in presentingproofs at the blackboard.Grades: Your course grade will be determined as follows:• required homework, 50 points• class presentations, 20 points• exploratory homework and programming assignments, 50 points• two best quizzes, 20 points each• third quiz, 10 points• final exam, 100 pointsThe total points available are thus 270, and the grading scheme is as follows:Percentage Minimum Grade92% A86% A-80% B+74% B68% B-62% C+56% CExams: There will be three in-class quizzes and one final exam. The quizzeswill be roughly one-half hour each, and the final is scheduled for three hours.Three Quizzes: Thursday, October 14Tuesday, November 9Thursday, December 9Final Exam: comprehensive, though weighted toward the later material2Texts:“Discrete Mathematics,” Norman L. Biggs, second edition, Oxford Uni-versity Press, 2002, ISBN# 0-19-850717-8 (at the Coop)“Calculus, Volume II, 2nd Ed.” Tom M. Apostol, Wiley, 1969, ISBN#0-536-00008-5 (Ch. 13 only – will be available as a course pack)Homework and Programming Assignments: Homework will be assignedweekly and will be due at the start of Tuesday’s class. The CA will returnyour corrected homework to you at the following class.You are encouraged to discuss the course with other students, your CAand the instructors, but you should always write your homework solutions outyourself in your own words.Required homework problems are the ones due weekly and are a necessarycomponent of keeping up with the course.There are two options for the second homework component of the grade.The first option is a set of exploratory problems (2 points each) which willengage your creativity, consisting of some more difficult proofs and some open-ended questions. The second is a set of three programming assignments (45points total) for those more interested in computer science. You are encour-aged to mix and match from among the exploratory problems and computerassignments to achieve a total of 50 points.Due dates for the exploratory problems and computer assignments areflexible, but to get full credit you must earn• at least 10 points before the first quiz• at least 20 points before the second quiz• at least 30 points before the third quiz• at least 40 points before the end of reading period.This lets you save 10 points’ worth to do in reviewing for the final exam, andthere will be a few exploratory problems of the last topic that are good practicefor the final.3Approximate Day-by-Day Syllabus:Date Reading TopicsSeptember 21 Counting, Symmetries and Platonic Solids23 3.6, 5.5–5.6, Ch. 21 Permutations28 Ch. 20 Groups30 Ch. 13 Congruence ArithmeticOctober 5 Ch. 20 Subgroups7 Ch. 20 Quotient Groups12 Ch. 22 Rings14 Ch. 23 QUIZ #1 and Fields19 Ch. 23 Finite Fields21 23.6–23.7, supplement Finite Affine Geometry26 23.6–23.7, supplement Finite Affine Geometry28 any linear algebra text Linear Algebra over Finite FieldsNovember 2 any linear algebra text Linear Transformations4 supplement Group Isomorphisms9 supplement QUIZ #2 and Isomorphisms16 supplement Isomorphisms18 Ch. 13 (Apostol) Set Theory23 Ch. 13 (Apostol) Probability30 Ch. 13 (Apostol) ProbabilityDecember 2 Ch. 13 (Apostol) Countability and Uncountability7 15.1–15.3 QUIZ #3 and Graph Theory9 15.4 Cycles and paths14 16.3-16.5 Trees, spanning trees16 supplement Generators and relations21 supplement Graphs and