Professor: L. Williams (office 913 Evans, e-mail williams@math.berkeley.edu)
Office Hours: Monday 4:00-5:00pm, Tuesday 5:00-6:30pm, or by appointment.
For extra help: check out the Student Learning Center. Their study group meets TTh 1-2, room 201A.
Final Exam: Friday, December 16, 7-10pm, in 155 Dwinelle.
This course provides an introduction to logic and proof techniques, basics of set theory, elementary number theory and cryptography, combinatorial enumeration, discrete probability, and graph theory, with a view towards applications. It is designed for majors in mathematics, computer science, statistics, and other related science and engineering disciplines.
Required text: information can be found here. This is a custom
edition of the 7th edition of the textbook Discrete Mathematics and its Applications,
by Kenneth H. Rosen, McGraw-Hill. (More specifically, it is identical
to the 7th edition except a few chapters are missing; as a result,
it is somewhat less expensive than the full-length version.)
Some students have asked me if they can use the 6th edition of the textbook instead. The 6th and 7th editions of Rosen are quite similar, but the order of presentation of topics is slightly different. I will be assigning a number of problems out of the book, so if you have the 6th edition of the textbook, you'll have to look at the 7th edition in order to find out what problems to do.
All solutions that you submit must be your own work and must not be copied from somewhere else. A solution that is blatantly copied from another source will receive zero credit. There will be serious consequences for repeat offenders.
There will be two in-class midterms, on Tuesday, October 4, and on Thursday, November 17. A review session will be held during the class preceding the midterm. *No books, notes, calculators, scratch paper or collaboration are permitted at any exam*. Your student photo ID is required at the midterms and final exam. No make-up midterms will be given; instead, missing midterm scores will be overridden by the final exam score.
The final exam will be on Friday, December 16, 7-10pm. Note that there are no makeups for the final exam, so you must plan your holiday travels accordingly.
Homework 15%, Midterms 25% each, Final 35%. Your lowest two homework scores will be dropped, and the final exam score will override any lower midterm score. This means that, a posteriori, your final exam may count as 60% or 85% instead of 35%. Incomplete grades are rarely given, and only for a documented serious medical problem or genuine personal/family emergency, provided you have a C average on the previous coursework.
| Date | Topics | Book | Homework problems | Notes |
| Thurs 8/25 | Propositional logic and equivalences | § 1.1, 1.2, 1.3 | § 1.1 (12, 16, 26, 28), § 1.3 (22,30,63, 66) | Lecture 1 |
| Tues 8/30 | Predicates, quantifiers, rules of inference | § 1.4, 1.5, 1.6 | § 1.4 (8, 16, 44), § 1.5 (8,10,20) | Lecture 2 |
| Thurs 9/1 | Rules of inference and introduction to proofs | § 1.6, 1.7, 1.8 | § 1.6 (14, 16), § 1.7 (4,14,18,22), § 1.8 (3,27) | Lecture 3 |
| Tues 9/6 | Sets and set operations; start functions | § 2.1, 2.2, 2.3 | § 2.1 (7,8,23,32,41,46), § 2.2 (2,14,16,26,42), § 2.3 (6,8,12,20,37,44) | Lecture 4 |
| Thurs 9/8 | Functions, sequences; cardinality | § 2.4, 2.5 | § 2.4 (26,32,34), § 2.5 (2) | Lecture 5 |
| Tues 9/13 | Modular arithmetic, integer representations | § 4.1, 4.2, 4.3 | § 4.1 (9, 16, 20, 35), § 4.2 (4,7,10,31), § 4.3 (12, 15, 20) | Lecture 6 |
| Thurs 9/15 | Primes, GCD, inverses | § 4.3, 4.4 | § 4.3 (24, 32, 33, 40, 49, 52), § 4.4 (2, 6) | Lecture 7 |
| Tues 9/20 | Solving congruences, Cryptography | § 4.4, 4.6 | § 4.4 (8, 19, 21, 29, 30, 38), § 4.6 (1, 4, 24, 27) | Lecture 8 |
| Thurs 9/22 | Mathematical induction; strong induction | § 5.1, 5.2 | § 5.1 (4, 6, 10, 18, 32, 54), § 5.2 (4, 10, 26) | Lecture 9 |
| Tues 9/27 | Well-ordering and recursive definitions | § 5.2, 5.3 | § 5.3 (4, 6, 8, 12, 20) | Lecture 10 |
| Thurs 9/29 | Review for exam | Lecture 11 | ||
| Tues 10/4 | MIDTERM 1 | |||
| Thurs 10/6 | Counting; the pigeonhole principle | § 6.1, 6.2 | § 6.1 (8, 16, 21, 26, 32, 67), § 6.2 (9, 16, 18, 21, 27, 28) | Lecture 12 |
| Tues 10/11 | Permutations and combinations | § 6.3, 6.4 | § 6.3 (5, 12, 18, 22, 35, 36), § 6.4 (16, 20, 24, 33, 34) | Lecture 13 |
| Thurs 10/13 | Generalized permutations and combinations | § 6.5 | § 6.5 (10, 15, 16, 22, 34, 50, 59) | Lecture 14 |
| Tues 10/18 | Introduction to discrete probability | § 7.1, 7.2 | § 7.1 (10, 20, 21, 24, 34, 38), § 7.2 (2, 6, 10, 16, 23) | Lecture 15 |
| Thurs 10/20 | Probability theory, Bayes' Theorem | § 7.2, 7.3 | § 7.3 (2, 4, 6, 10, 15, 16) | Lecture 16 |
| Tues 10/25 | Expected value and variance | § 7.4 | § 7.4 (4, 5, 13, 28, 32, 44, 46) | Lecture 17 |
| Thurs 10/27 | Recurrence relations | § 8.1, 8.2 | § 8.1 (3, 11, 20, 21, 26, 30), § 8.2 (4, 8, 11, 12, 15) | Lecture 18 |
| Tues 11/1 | Generating functions; inclusion-exclusion | § 8.4, 8.5, 8.6 | § 8.4 (30, 32, 34, 39), § 8.5 (8, 24), § 8.6 (1, 3, 4, 13, 18, 26) | Lecture 19 |
| Thurs 11/3 | Relations: their properties and applications | § 9.1, 9.3 | § 9.1 (22, 34, 36), § 9.3 (10, 14, 26, 36) | Lecture 20 |
| Tues 11/8 | Closures of relations; equivalence relations | § 9.4, 9.5 | § 9.4 (2, 3, 9, 29), § 9.5 (8, 16, 24, 36, 41, 62) | Lecture 21 |
| Thurs 11/10 | Graphs and graph models | § 10.1, 10.2, start 10.3 | § 10.1 (12, 28), § 10.2 (4, 20, 22, 42, 60) | Lecture 22 |
| Tues 11/15 | Review for exam | Lecture 23 | ||
| Thurs 11/17 | MIDTERM 2 | |||
| Tues 11/22 | Graph isomorphism; Connectivity | § 10.3, 10.4 | § 10.3 (23, 37, 41, 55), § 10.4 (1, 11, 15, 21, 23, 29, 43) | Lecture 24 |
| Thurs 11/24 | NO CLASS (Thanksgiving break) | |||
| Tues 11/29 | Eulerian circuits; Trees and the number of labeled trees | § 10.5, §11.1 plus Cayley's formula | § 10.5 (3, 5, 13), § 11.1 (1, 38)Chapter 11 problems | <Lecture 25 | /tr>
| Thurs 12/1 | Review for final | See the sample finals and list of topics below | ||
| Fri 12/16 | FINAL EXAM (7:00pm-10:00pm), place TBD |
Note: these are actual midterms from a previous course.
Note: an unrooted tree just means a tree. You can ignore the parts of the questions which concern rooted trees. You can also ignore the questions that deal with posets. Also, a palindrome is a word which is the same when read forwards and backwards.