Math 55—Discrete Mathematics—Fall 2008


Professor: Mark Haiman

855 Evans Hall, office hours W 1:30-2:15, 2:30-3:00, F 1:30-3:00.

Section Instructors:

Lectures: MWF 12:00-1:00pm, Room 2060 Valley LSB

Discussion sections: See schedule. You can change sections online through TeleBears. When you sign up for a section that is full, you get put on its wait list. Students on the wait list are automatically enrolled when spaces open. If you are near the top of the wait list for your preferred section, you are likely to get in. Otherwise, a good strategy is to check daily for other sections that become open or whose wait list shortens, and switch if you find one that improves your wait list position. If you have problems you can't resolve with the online system, see the Head TA, Ishai Dan-Cohen, in 1039 Evans Hall. His office hours (for the first two weeks of classes) are MWF 3:30-6:30, TTh 2:30-3:30 and 4-6. Don't email him—he is responsible for too many students to reply to email.

Description: This course provides an introduction to logic and proof techniques, basics of set theory, algorithms, elementary number theory, combinatorial enumeration, discrete probability, graphs and trees, with applications to coding theory. It is designed 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. Freshmen 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, 6th Edition

Grading: Based on weekly homework (20%), two midterm exams (20% each), and final exam (40%).
Incomplete (I) grades are rarely given, and only for a documented serious medical problem or genuine personal/family emergency. Falling behind in the course or problems with workload on other courses are not acceptable reasons to request an incomplete.

Exams:

At exams you will be allowed one (ordinary sized) sheet of notes, written on both sides. No other notes, books, calculators, computers or other aids will be permitted.
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. (However, you cannot "miss" a midterm retroactively after turning in the exam).
For review, you can find web pages from this course in earlier years, including exams with solutions, on Richard Borcherds' math courses archive.

Homework: Homework will be due on Mondays and returned in discussion sections on Wednesdays. The deadline to turn in homework for all students is the end of the last discussion section on Monday.
A semi-random 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 somewhat 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 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.

Syllabus

  1. Propositional logic, quantifiers, rules of inference, proof techniques (Rosen Chapter 1)
  2. Sets, functions, countability and uncountable sets (Sections 2.1-2.3, and part of 2.4 on cardinality)
  3. Algorithms, halting problem (Section 3.1), undecidability (covered in lecture)
  4. Division algorithm, modular arithmetic, primes, GCD (Sections 3.4-3.5)
  5. Euclidean algorithm, modular exponentiation, solving conguences, Chinese Remainder Theorem, applications to cryptography (Sections 3.6-3.7)
  6. Induction and recursion, recursive algorithms (Sections 4.1-4.4; revisit 2.4 for summations)
  7. Counting, pigeon hole principle, permutations and combinations, binomial coefficients, distributions, Stirling numbers (Sections 5.1-5.5)
  8. Discrete probability theory, conditional probability, independence, random variables (Sections 6.1-6.2)
  9. Bayes' Theorem and applications (Section 6.3)
  10. Expected value, variance, Chebyshev's inequality (Section 6.4)
  11. Recurrence relations and generating functions (Sections 7.1-7.2 and Examples 10-15 in 7.4)
  12. Inclusion-exclusion, derangements, formula for Stirling numbers (Sections 7.5, 7.6)
  13. Relations, directed graphs, transitive closure, equivalence relations, set partitions, partial orders (Section 8.1, part of 8.3 on digraphs, 8.4-8.6)
  14. Graphs, isomorphism, connectivity (Sections 9.1-9.4)
  15. Trees, spanning trees, minimum-weight spanning trees (Sections 10.1, 10.4-10.5)
  16. 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 (v) counting trees.

Reading and Homework Assignments

By popular demand, I'm also posting here files of the computer demos of RSA, Pollard's factoring algorithm, and Reed-Solomon codes shown in the lectures. These are in two formats:
[ Top of page | Prof. Haiman's home page ]