Math 55—Discrete Mathematics—Fall 2012

Professor: Mark Haiman

855 Evans Hall, office hours MW 10:30-11:30

Section Instructors:

Lectures: MWF 2-3pm, Room 100 Lewis Hall

Discussion sections: Mondays and Wednesdays, see full or short schedule. You can change sections online through TeleBears. If you are wait-listed for the section you prefer, I recommend sticking with it if there are only a few others ahead of you; otherwise, check periodically to try to find a section with a shorter wait list.

Description: This course provides an introduction to logic and proof techniques, basics of set theory, algorithms, elementary number theory (with applications to cryptography and error correcting codes), combinatorial enumeration, discrete probability, and graph theory. It is intended for majors in mathematics, computer science, and other related science and engineering disciplines.

Prerequisites: Mathematical maturity appropriate to a sophomore math class. 1A-1B recommended but not required. First year students with strong high school math background and a possible interest in majoring in mathematics may also wish to consider taking this course.

Textbook: Kenneth H. Rosen, Discrete Mathematics and Its Applications, UC Berkeley Edition. The Berkeley custom edition is the same as the Seventh Edition with chapters 11 and 12 omitted. If you have a copy of the full Seventh Edition, that is fine too.

Grading: Based on weekly homework (20%), two midterm exams (20% each), and final exam (40%).

Incomplete grades are rarely given, only for a documented serious medical problem or personal/family emergency, and require that you have passing scores on work not missed. Falling behind in the course or problems with workload in other courses are not acceptable reasons to request an incomplete.

Here is the exact grading formula: first I will convert each of your four scores (homework, two midterms, and final) to a grade point score in the range 0—5.0, based on the grade cutoffs for each exam and homework. Grade cutoffs for homework will be chosen so that the overall homework grade distribution is similar to the overall exam grade distribution.

If you missed midterm 1, your grade point score for midterm 2 replaces it. If you missed midterm 2, your grade point score for the final replaces it.

As it turns out, many students this semester had one unrepresenatively low midterm score. Since I don't want such a score to count heavily against you, if your lowest grade point score is a midterm (but not if it is your homework or final), I will raise it to the lowest of your other three scores. If you missed midterm 1, and your lowest score is midterm 2, the raised midterm 2 score counts for one of the midterms, and the unchanged midterm 2 score for the other. In theory, if you missed both midterms, your final would count for midterm 2 and you would have a zero for midterm 1. However, according to the lowest midterm score policy, this zero is raised to the lower of your final exam and homework grade point scores.


The final exam will cover the whole course, with extra emphasis on material not previously covered on midterms.

Exam questions will be similar in difficulty to the more routine types of homework problems.

At midterm exams you are allowed one (ordinary sized) sheet of notes, written on both sides. For the final exam you can use two note sheets. No other books, notes, calculators, cell phones, audio players or other aids are permitted. There will be space to write answers on the exams themselves, but you will need to bring your own scratch paper.

No make-up exams will be given. If you miss one midterm, your score on the following exam will count in place of that midterm, i.e., Midterm 2 in place of Midterm 1, or Final Exam in place of Midterm 2. You cannot "miss" a midterm retroactively after turning in the exam.

Homework: Homework is due on Mondays, either in section, or to your GSI at their office or mailbox, according to their instructions, by 6pm. Homework will be returned in discussion sections on Wednesdays.

A subset of the problems on each homework will be chosen for full grading, and scored out of 10 points each. The remaining problems will only be checked quickly and will count 2 points each. The choice of problems for grading will not be announced in advance, but will be indicated on the solutions. I am more likely to choose for grading those problems requiring more thought.

You are free to discuss the homework problems and ideas for solving them with other students, but you must write up your solutions individually. It is not acceptable to copy solutions worked out by others or found in a solution manual or on the internet.

Special accomodations: Students requiring special accomodations for exams must provide documentation from the Disabled Students' Program (DSP), and should contact me well in advance of the first exam so that suitable arrangements can be made.


  1. Propositional logic, quantifiers, rules of inference, proof techniques (Rosen Chapter 1)
  2. Sets, functions, countability and uncountable sets (2.1-2.3, 2.5)
  3. Algorithms, halting problem, undecidability and complexity (Chapter 3 and parts of Chapter 13)
  4. Division algorithm, modular arithmetic, primes, GCD (4.1-4.3)
  5. Euclidean algorithm, modular exponentiation, solving conguences, Chinese Remainder Theorem, applications to cryptography (4.5-4.6)
  6. Induction and recursion, recursive algorithms (Chapter 5 and 2.4)
  7. Counting, pigeon hole principle, permutations and combinations, binomial coefficients, distributions, Stirling numbers (Chapter 6)
  8. Discrete probability theory, conditional probability, independence, random variables (7.1-7.2)
  9. Bayes' Theorem and applications (7.3)
  10. Expected value, variance, Chebyshev's inequality (Section 7.4)
  11. Recurrence relations and generating functions (8.1-8.4)
  12. Inclusion-exclusion, derangements, formula for Stirling numbers (8.5-8.6)
  13. Relations, directed graphs, transitive closure, equivalence relations, set partitions, partial orders (Chapter 9)
  14. Graphs, isomorphism, connectivity (10.1-10.4)
  15. Additional topics to be included as time permits, most likely drawn from the following: (i) primality testing and factoring algorithms, (ii) matrices and error-correcting codes, (iii) shortest-path problems, (iv) planar graphs and the four and five-color theorems.

Reading and Homework Assignments

[ Top of page | Calendar | Prof. Haiman's home page ]