Math 55 - Discrete Mathematics - Fall 2009

Lecture: Tuesday and Thursday 2:00-3:30, 10 Evans

Course Home Page: http://math.berkeley.edu/~strain/55.F09/index.html

Professor: J Strain, Office 1099 Evans, Hours Monday 2:00-4:00 and Thursday 11:00-12:00, Telephone 642-3656.

GSI Offices and Hours:

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 (Note: the international edition omits Chapter 6.)

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, 2.4)
3. Algorithms, halting problem (Section 3.1), undecidability
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)
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, 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, 8.3-8.6)
14. Graphs, isomorphism, connectivity, Euler and Hamilton paths (Sections 9.1-9.5)
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 (v) counting trees.

Grading: Based on weekly homework (20%) and quizzes (10%), two midterm exams (20% each), and final exam (30%). Only the top 10 homeworks and quizzes will be counted, and final exam scores will override lower midterm scores.

Exams:

• Midterm 1: Tuesday, September 22 in class: The exam will cover those sections of Chapters 1-3 on which homework has been assigned, plus enough about big-O notation and pseudocode to read, understand, and analyze the complexity of simple algorithms (as in lecture).
• Midterm 2: Thursday, November 5: Chapters 1-6.3. The exam will cover those sections of Chapters 1-6.3 on which homework was due before the midterm.
• Final Exam: Monday, December 14, 12:30-3:30, Chapters 1-9.
  About 60% of the final will be on material from Chapters 8-9. No 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 final 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.
  

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. Further enrollment issues involving TeleBears should be addressed to Barbara Peavy (peavy@math.berkeley.edu).

Homework: Homework will be due on Wednesdays by 5 pm (exception: Homework #9 will be due Monday November 9 after the second midterm), and returned in discussion sections by the following Monday. Three problems on each homework will be chosen for full grading. The homework problems and ideas for solving them may be discussed with other students, but solutions must be written 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 should contact us well in advance of the first exam so that suitable arrangements can be made.

Announcements and Handouts