Office Hours: 873 Evans; T/Th 2:00-3:30
GSI | Office | Hours |
Ben Castle | 741 Evans | Tuesdays, 3:30 -- 5:30 |
Ravi Fernando | 1093 Evans | Thursdays, 4:00 -- 6:00 |
Luhang Lai | 1037 Evans | Mondays & Wednesdays, 4:00 -- 5:00 |
Jeremy Meza | 1047 Evans | Tuesdays, 10:00 -- 12:00 |
Alexander Rusciano | 787 Evans | Wednesdays, 3:00 -- 5:00 |
Benjamin Siskind | 937 Evans | Fridays, 10:00 -- 12:00 |
Dun Tang | 1006 Evans | Mondays & Wednesdays, 6:00 -- 7:00 |
For extra help: check out the Student Learning Center.
Important:
Midterms: October 1 and November 12. In class.Logic, mathematical induction, sets, relations, and functions,
introduction to graphs,
elementary number theory,
combinatorics,
algebraic structures,
discrete probability theory.
I have separated those onto different lines, because each concerns a distinct subject of mathematics. This should give you an idea of how much we have to cover in this course.
You are responsible for everything in the sections assigned, which you should read before class. I will use the lectures to hit the high points, work examples, and clear up points of confusion. You are encouraged to ask questions during class, even though it is a large lecture. If I spend the whole class answering questions, I will consider it time well spent. You are also encouraged to email me a day before class to say which aspects of the text you would most like emphasized or clarified.
One main goal of this course is for you to learn to write mathematical proofs. If a problem says "prove" or "show that" or a similar phrase, it means you are to give a logically correct and coherent argument, written in complete sentences. I remind you that a complete sentence begins with a capital letter, has a subject and verb, and ends in a period.
Unlike in previous courses, you are not expected to immediately see how to solve a problem. Even just
understanding what a mathematical statement means takes work --- thinking through examples, trying
to break the conclusion by varying the hypotheses, etc. --- and figuring out how to prove or disprove a statement
is a creative exercise, not a rote application of material. You will be confused, you will get stuck, and that
is part of the process.
Often you will have to try several approaches before you find an idea that works.
This takes time, so do not start the homework the day before it is due.
Required text: Discrete Mathematics, by Kenneth H. Rosen, 8th edition (customized for UC berkeley)
Information can be found here.
The custom edition differs from the usual 8th edition only in the omission of some sections. Other (7th, 6th) editions have largely similar content, but have different numbering of sections and problems. Textbook problems will be assigned, so be sure to have access to an 8th edition copy.
You are welcome to discuss the homework problems with other students, but you must write up solutions independently. You must list the names of anyone with whom you discussed the problems (be they students, GSIs, professors, people on the internet) and any other sources you used, aside from the textbook. Your solutions must not be copied from any other student or any other source. A solution which is copied will receive zero credit. There will be significantly more serious consequences for repeat offenders.
There will be two in-class midterms. During exams, no use of books, notes, calculators, electronic devices of any kind, or collaboration is permitted. You also cannot use your own scratch paper, some will be provided. 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 12/20, at 8-11 am. There are no makeups for the final exam.
Homework 10%, Quizzes 10%, Midterms 25% each, Final 30%.
Your lowest three homework scores and lowest two quiz scores will
be dropped. The
final exam score will override any lower midterm score. This means that your final exam may
count as 55% or 80% instead of 30%.
There will be no makeups of homework, quizzes, midterms, or finals.
(Except when mandated by the DSP office.)
The grade distribution will be consistent with the historical average of the class, which can be found at berkeleytime.
Laptops, phones, and other electronic equipment distract not only you, but everyone around you. They are not permitted in class. The only exceptions are for students with a documented disability which requires it. Such students should explain the situation to the instructor or GSI and sit in the first 3 rows.
Some adjustments to the schedule below are to be expected. In particular, if we end up going slower
than expected, presentation of new material may extend into review days.
The starred problem (announced after the homework due date) is the one graded.
Solutions to past homeworks can be found at the bottom of the page.
Date | Topics | Reading | Homework |
Thurs 8/29 | Truth & logic | 1.1, 1.3 |
§1.1 : 2, 6, 12, 16, 20, 24, 30, 36 §1.3 : 2, 4, 8, 22, *32, 64, 66 |
Tues 9/3 | Quantifiers | 1.4, 1.5 |
§1.4 : 6, 10, 16, 32, 52 §1.5 : 8, 10, 16, 24, 28 |
Thurs 9/5 | Validity & proof | 1.6, 1.7, 1.8 |
§1.6 : 14, 16, 34 §1.7 : *6, 16, 22, 36 §1.8 : 4, 10, 14 |
Tues 9/10 | Sets & functions | 2.1, 2.2, 2.3 |
§2.1 : 2, 12, 18, 20, 40, 44 §2.2 : 2, 18, 24, 28, 50 |
Thurs 9/12 | Sequences, cardinality | 2.3, 2.4, 2.5 |
§2.3 : 2, 12, 14, *34, 36 §2.4 : 26, 28, 44 §2.5 : 2, 4 |
Tues 9/17 | Modular arithmetic & base b | 4.1, 4.2 |
§4.1 : 2, 10, 14, 18, 30, 32, 44, 50 §4.2 : 2, 6, 26, 32, 56 |
Thurs 9/19 | Primes, GCD, inverses | 4.3 | §4.3 : 2, 10, 24, 26, 32, 50, *54 |
Tues 9/24 | Algebra mod n; Cryptography | 4.4, 4.6 | § 4.4 : 2, 6, *14, 16, 17, 18, 19, 38, 40, 46 § 4.6 : 26 |
Thurs 9/26 | Review | ||
Tues 10/1 | MIDTERM 1 | ||
Thurs 10/3 | Induction | 5.1, 5.2 | § 5.1 : 10, 14, 18, 34, 64, 76 § 5.2 : 4, 14, 30, 36, 38 |
Tues 10/8 | Recursive definition | 5.3 | § 5.3 : 2, 6, 8, *14, 28, 45, 49, 58 |
Thurs 10/10 | Class cancelled due to wind | ||
Tues 10/15 | Counting! | 6.1, 6.2 |
§ 6.1 : 4, 16, 26, 32, 48, 66 § 6.2 : 2, *14, 24, 34, 40 |
Thurs 10/17 | Permutations and combinations | 6.3, 6.4 |
§ 6.3 : 9, 18, 24, 32, 38 § 6.4 : 8, 16, 24, 34, 36 |
Tues 10/22 | More permutations and combinations | 6.5 | § 6.5 : 8, 10, 12, 22, 30, 32, 52, 56, *60, 68 |
Thurs 10/24 | Intro to Probability | 7.1 | § 7.1 : 10, 20, 21, 24, 34, 38, 40 |
Tues 10/29 | Probability theory, Bayes' Theorem | 7.2, 7.3 |
§ 7.2 : 5, 10, 12, 18, 24, 34, 38 § 7.3 : 4, 6, 8, 12, 16 |
Thurs 10/31 | Expectation and variance | 7.4 | § 7.4 : 6, 10, *16, 22, 30, 37, 38, 39 |
Tues 11/5 | Recurrence relations | 8.1, 8.2 |
§ 8.1 : 4, 6, 8, 12, 18, 20, 28, 50, 52 § 8.2 : *8, 10, 36 |
Thurs 11/7 | Generating functions | 8.4 | § 8.4 : 4, 6, 16, 24, 28, 32, 36, 46 |
Tues 11/12 | MIDTERM 2 | ||
Thurs 11/14 | Graphs | 10.1, 10.2 |
§ 10.1 : *10, 13, 16, 32 § 10.2 : 4, 6, 18, 20, 26, 30, 44, 64 |
Tues 11/19 | Graph isomorphism, connectivity | 10.3, 10.4 |
§ 10.3 : 6, 14, 18, 26, 32, 36, 44,
§ 10.4 : 2, 4, 10, 20, 34, 60, 64 |
Thurs 11/21 | Eulerian circuits and paths | 10.5 | § 10.5 : 8, 10, 14, 26, 34, 46, 48 |
Tues 11/26 | Planar graphs | 10.7 | § 10.7 : 4, *8, 14, 24, 26, 28, 36 |
Thurs 11/29 | NO CLASS (Thanksgiving) | ||
Tues 12/3 | Graph coloring | 10.8 | |
Thurs 12/5 | (possibly) The Tutte polynomial | ||
Fri 12/20 | FINAL EXAM (8am-11am) |