Professor: L. Williams (office 913 Evans, e-mail williams@math.berkeley.edu)
Office Hours: Mondays 3:30-4:30pm in 913 Evans, and Tuesdays 2-3:30pm in 961 Evans. (On Tues Feb 20, office hours will instead be 10am to 11:30am)
For extra help: check out the Student Learning Center. You are also welcome to attend the office hours of the instructor or of ANY GSI (see the list of office hours at the bottom of the page).
ANNOUNCEMENTS: Here is a summary of the topics we've covered in this class.
During RRR week, Professor Williams will hold review sessions at the time/place of the usual lecture (VLSB 12:30pm-2pm Tues/Thurs). Additionally, Aaron will have meetings at the time/place of his recitation, and also his usual office hour (11am-1pm Friday). Albert will have meetings at the time/place of his recitation, and also his usual office hour. Melissa will have meetings at the time/place of her recitation, and also her usual office hour. Charles will have his usual office hour 11-12:30pm on Tues/Thurs. Jeremy will have his usual office hours 10am-12pm on Wednesday. Chris will have office hours 11am-1pm on Wednesday (note unusual time).
During finals week, Jeremy will have his usual office hours Wednesday 10am-12pm. Charles will have his usual office hour Tues/Thurs 11am-12:30pm. Chris will have office hours on Wednesday May 9 11am-1pm (note unusual time). All students are welcome at all of the activities listed above.
Here is a sample Midterm 1, and here are the solutions. Midterm 1 will cover all the material we've covered so far (in class or in homework) up through Section 4.3.
Here is a sample Midterm 2 and here are the solutions. Midterm 2 will cover all the material we've covered so far (in class or in homework) up through Section 9.3 and a bit of 9.4.
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.)
Note that 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 an older 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. You ARE are allowed to discuss the homework problems with other students, but if you do this, you must list at the top of your homework the names of any collaborators. If you used sources besides the textbook, you must list those as well.
There will be two in-class midterms. *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 Thursday, May 10, 3-6pm. Note that there are no makeups for the final exam.
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.
According to the College academic calendar, the last day to add or drop this course is Friday, February 16, shortly after the first midterm. The last day to change your grading option via CalCentral is March 23.
I will post some partial lecture notes in advance of each lecture, which you can print out in advance and annotate during lecture if you wish. (Since these notes are not complete, they won't substitute for the lecture itself, but are meant to make your note-taking easier.)
No laptops, phones, or other electronic equipment can be used during lecture or discussion sections unless explicitly permitted by the instructor for in-class activities. The only permanent exceptions are for students with a document disability which requires it. Such students should explain the situation to the instructor or GSI and sit in the first 3 rows.
| Date | Topics | Book | Homework problems | Notes |
| Tues 1/16 | Propositional logic and equivalences | § 1.1, 1.3 | § 1.1 (12, 16, 26, 28), § 1.3 (22, 30, 63, 66) | Lecture 1 |
| Thurs 1/18 | Predicates, quantifiers, rules of inference | § 1.4, 1.5, 1.6 | § 1.4 (8, 16, 44), § 1.5 (8,10,20) | Lecture 2 |
| Tues 1/23 | 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,34) | Lecture 3 |
| Thurs 1/25 | 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, 37) | Lecture 4 |
| Tues 1/30 | Functions, sequences; cardinality | § 2.3, 2.4, 2.5 | § 2.3 (20, 44), § 2.4 (26, 32, 34), § 2.5 (2) | Lecture 5 |
| Thurs 2/1 | Modular arithmetic, integer representations | § 4.1, 4.2, 4.3 | § 4.1 (9, 16, 20, 33, 35), § 4.2 (2, 4, 7, 31) | Lecture 6 |
| Tues 2/6 | Primes, GCD, inverses | § 4.3 | § 4.3 (12, 15, 24, 32, 33, 40, 49, 50) | Lecture 7 |
| Thurs 2/8 | Start § 4.4; Review for exam | Lecture 8 | ||
| Tues 2/13 | MIDTERM 1 | |||
| Thurs 2/15 | Solving congruences, Cryptography | § 4.4, 4.6 | § 4.4 (2, 5, 8, 11, 19, 21, 29, 30, 38) § 4.6 (24) | Lecture 9 |
| Tues 2/20 | Mathematical induction; strong induction | § 5.1, 5.2 | § 5.1 (4, 6, 10, 18, 32, 54), § 5.2 (4, 10, 12, 26) | Lecture 10 |
| Thurs 2/22 | Well-ordering and recursive definitions | § 5.2, 5.3, 6.1 | § 5.3 (4, 6, 8, 12, 20, 25) | Lecture 11 |
| Tues 2/27 | Counting; the pigeonhole principle | § 6.1, 6.2 | § 6.1 (16, 26, 32, 37, 67), § 6.2 (9, 16, 18, 26, 27, 28) | Lecture 12 |
| Thurs 3/1 | Permutations and combinations | § 6.3, 6.4 | § 6.3 (5, 12, 18, 22, 36), § 6.4 (8, 22, 24, 33, 34) | Lecture 13 |
| Tues 3/6 | Generalized permutations and combinations | § 6.5 | § 6.5 (10, 15, 16, 22, 34, 47) | Lecture 14 |
| Thurs 3/8 | Introduction to discrete probability | § 7.1 | § 7.1 (10, 20, 21, 24, 34, 38, 40) | Lecture 15 |
| Tues 3/13 | Probability theory, Bayes' Theorem | § 7.2, 7.3 | § 7.2 (2, 6, 10, 16, 23, 35), § 7.3 (2, 4, 6, 10, 15, 16) | Lecture 16 |
| Thurs 3/15 | Expected value and variance | § 7.4 | § 7.4 (4, 5, 13, 14, 28, 30, 32) | Lecture 17 |
| Tues 3/20 | Recurrence relations | § 8.1, 8.2 | § 8.1 (9, 11, 20, 21, 26), § 8.2 (4, 8, 11, 12, 15) | Lecture 18 |
| Thurs 3/22 | Generating functions; inclusion-exclusion | § 8.4, 8.5, 8.6 | § 8.4 (30, 32, 34, 39), § 8.5 (8, 11, 24), § 8.6 (1, 4, 13, 18, 26) | Lecture 19 |
| Tues 3/27 | NO CLASS (Spring break) | |||
| Thurs 3/29 | NO CLASS (Spring break) | |||
| Tues 4/3 | Relations: their properties and applications | § 9.1, 9.3, start 9.4 | § 9.1 (6, 22, 34, 36, 40), § 9.3 (4, 10, 14, 26, 36) | Lecture 20 |
| Thurs 4/5 | Review for exam | |||
| Tues 4/10 | MIDTERM 2 | |||
| Thurs 4/12 | Closures of relations; equivalence relations | § 9.4, 9.5 | § 9.4 (2, 3, 9, 29), § 9.5 (8, 16, 24, 36, 42, 62) | Lecture 22 |
| Tues 4/17 | Graphs and graph models | § 10.1, 10.2 | § 10.1 (12, 28), § 10.2 (4, 5, 20, 22, 60) | Lecture 23 |
| Thurs 4/19 | Graph isomorphism; Connectivity | § 10.3, 10.4 | § 10.3 (6, 23, 29, 37, 41, 55), § 10.4 (1, 11, 15, 21, 23, 29, 43) | Lecture 24 |
| Tues 4/24 | Eulerian circuits and paths | § 10.5 | § 10.5 (3, 5, 13, 14) (not graded) | Lecture 25 |
| Thurs 4/26 | Review session 1 | |||
| Tues 5/1 | Review session 2 (review for 50 minutes, then 30 minutes office hour) | Notes | ||
| Thurs 5/3 | Review session 3 (review for 50 minutes, then 30 minutes office hour) | Notes | ||
| Thursday 5/10 | FINAL EXAM (3:00pm-6:00pm), Wheeler Auditorium 150 |
| Section | Time | Room | Instructor | Office hours | |
| 101 | MW 8-9am | 9 Evans | Charles Wang | charles@math.berkeley.edu | Tuesdays 9-11am / 828 Evans |
| 102 | MW 9-10am | B51 Hildebrand | Charles Wang | charles@math.berkeley.edu | Tuesdays 9-11am / 828 Evans |
| 103 | MW 4-5pm | 285 Cory | Jeremy Meza | jdmeza@berkeley.edu | Wednesdays 10am-12pm/ 775 Evans |
| 104 | MW 11am-12pm | B51 Hildebrand | Albert Ai | aai@math.berkeley.edu | Thursdays 10am-12pm / 845 Evans |
| 106 | MW 5-6pm | 70 Evans | Jeremy Meza | jdmeza@berkeley.edu | Wednesdays 10am-12pm / 775 Evans |
| 107 | MW 5-6pm | 9 Evans | Melissa Sherman-Bennett | msb@math.berkeley.edu | Tuesdays 3-5pm / 824 Evans |
| 108 | MW 4-5pm | B51 Hildebrand | Melissa Sherman-Bennett | msb@math.berkeley.edu | Tuesdays 3-5pm / 824 Evans |
| 109 | MW 8-9am | TBD | Chris Miller | crmiller@berkeley.edu | Monday and Wednesday 10-11am / 1049 Evans |
| 110 | MW 3-4pm | 385 LeConte | Aaron Brookner | brookner@math.berkeley.edu | Fridays 11am-1pm / 1006 Evans |
| 111 | MW 9-10am | 234 Dwinelle | Chris Miller | crmiller@math.berkeley.edu | Monday and Wednesday 10-11am / 1049 Evans |
| 112 | MW 12-1pm | 251 Dwinelle | Albert Ai | aii@math.berkeley.edu | Thursdays 10am-12pm / 845 Evans |
| 113 | MW 11-12pm | 6 Evans | Aaron Brookner | brookner@math.berkeley.edu | Fridays 11-1pm / 1006 Evans |