MATHEMATICS 152, FALL 2003METHODS OF DISCRETE MATHEMATICSLast revised: September 10, 2003Instructor: 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] 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 necessary. 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.If you are concentrating in Computer Science or Applied Mathematics,you will be expected to complete four programming projects in which youimplement key mathematical ideas from the course in a C++ program witha standard modern graphical user interface. There are detailed instructionsfor doing the user interface in either Windows or Linux, but you will needgood C++ skills (CS 51 or pre-Java AP Computer Science) to implement themathematics. Students who are not Applied Math or CS concentrators willneed to know how to download and run Windows application programs fromthe course Web site, but not how to write them.Course Meetings: The course meets TTh from 1-2:30 P. M. in ScienceCenter 116. There will also be an additional weekly problem session led bya course assistant. We will try to find a time for this session or late Mondayafternoon 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.1Grades: Your course grade will be determined as follows:• required homework, 50 points• class presentations, 20 points• exploratory homework and programming assignments, 40 points• two best quizzes, 20 points each• third quiz, 10 points• final exam, 100 pointsThe total points available are thus 260, and the grading scheme is as follows:Points Minimum Grade234 A221 A-208 B+195 B182 B-169 C+156 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 9Thursday, November 6Tuesday, December 2Final Exam: comprehensive, though weighted toward the later materialTexts:“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)Office Hours:• Tu 2:30-3:30 in Science Center 423• W mornings in Quincy 102 (most any time, but phone 3-3100 first)• M and W evenings in Quincy 102, but phone 3-3100 first)You are encourage to come to office hours to discuss your upcoming presen-tations, but be warned that this should not be left to Tuesday or Thursdaymorning, since that is when my other course Math 191 meets!2Homework and Programming Assignments: Homework will be assignedweekly and will be due at the start of Tuesday’s class. Your 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.In addition, there are two options for the second homework component ofthe grade. This work may be completed as late as Reading Period, thoughit is recommended that you begin long before then. The first option is aset of exploratory problems (2 points each) which will engage your creativity,consisting of some more difficult proofs and some open-ended questions. Thesecond is a set of four programming assignments (10 points each) for thosemore interested in computer science. Students are encouraged to mix andmatch from among the exploratory problems and computer assignments, butApplied Math and CS concentrators must earn at least 25 points from theprogramming assignments.3Approximate Day-by-Day Syllabus:Date Sections TopicsSeptember 16 27.1-27-3 Counting, Symmetries and Platonic Solids18 3.6, 5.5–5.6, Ch. 21 Permutations23 Ch. 20 Groups25 Ch. 13 Congruence Arithmetic30 Ch. 20 SubgroupsOctober 2 1.5, 6.1–6.3 Quotient Groups7 Ch. 22 Rings9 Ch. 23 QUIZ #1 and Fields14 Ch. 23 Finite Fields16 23.6–23.7, supplement Finite Affine Geometry21 23.6–23.7, supplement Finite Affine Geometry23 review Linear Algebra over Finite Fields28 review Linear Transformations30 supplement Group IsomorphismsNovember 4 supplement Group Isomorphisms6 supplement QUIZ #2 and Isomorphisms11 Ch. 13 (Apostol) Set Theory13 Ch. 13 (Apostol) Probability18 Ch. 13 (Apostol) Probability25 Ch. 13 (Apostol) Countability and UncountabilityDecember 2 15.1–15.3 QUIZ #3 and Graph Theory4 15.4 Cycles and paths9 16.6 Weighted graphs, shortest-path algorithms11 16.5 Trees, spanning trees16 supplement Generators and relationsJanuary 7 supplement Graphs and