Professor: L. Williams (office 913 Evans, e-mail williams@math.berkeley.edu)
Office Hours: Wednesday 4:30pm-5:30pm, Thursday 2:00pm-3:30pm, or by appointment.
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 a view towards applications in engineering and the life sciences. It is designed for majors in mathematics, computer science, statistics, and other related science and engineering disciplines.
Required text: Kenneth H. Rosen, Discrete mathematics and its applications, 6th edition, McGraw-Hill. We will cover material from Chapters 1-10.
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.
Five quizzes will be given at random times in the main lecture. Their main objective is to encourage attendence. There will be no make-up quizzes.
Midterm 1 will be held in class on Monday, October 4, and covers Chapters 1-3, and Sections 4.1 and 4.2 of Chapter 4 of Rosen. Midterm 2 is held in class on Monday, November 15, and covers Chapters 1-8 of Rosen. A review session is 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 mean on Midterm 1 was 58.7, the median was 63, and the standard deviation was 23.5. A *very* rough estimate of how a numerical grade *might* translate into a letter grade is the following: 77 is the cutoff for A-, 58.7 is the cutoff for B-, 31 is the cutoff for C-.
The final exam will be on Monday, December 13, from 11:30 to 2:30, in 155 Dwinelle.
Quizzes 5%, Homework 10%, Midterms 25% each, Final 35%. We will count only the top 10 homeworks, 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 |
Fri 8/27 | Propositional logic | § 1.1, 1.2 | § 1.1 (8, 12, 22, 24), § 1.2 (22,30) |
Mon 8/30 | Predicates and quantifiers | § 1.3, 1.4 | § 1.3 (8, 16, 44), § 1.4 (8,10,20) |
Wed 9/1 | Rules of inference | § 1.5 | § 1.5 (14, 16) |
Fri 9/3 | Introduction to proofs | § 1.6 | § 1.6 (4, 14, 18, 22) |
Mon 9/6 | NO CLASS (Labor Day holiday) | ||
Wed 9/8 | Sets and set operations (HW 1 due, § 1.1 - § 1.6) | § 2.1, 2.2 | § 2.1 (6, 8, 21, 28, 38), § 2.2 (2, 14, 16, 26, 42) |
Fri 9/10 | Functions; Sequences and Summations | § 2.3, 2.4 | § 2.3 (6, 8, 12, 16, 26, 40), § 2.4 (10, 16, 18, 32) |
Mon 9/13 | The integers and division | § 3.4 | § 3.4 (9, 12, 16, 21, 31, 32) |
Wed 9/15 | Primes, greatest common divisors (HW 2 due, § 2.1 - § 2.4) | § 3.5 | § 3.5 (2, 4, 8, 11, 16, 20, 28, 31, 34) |
Fri 9/17 | Integers and algorithms | § 3.6 | § 3.6 (4, 5, 8, 23, 24, 29) |
Mon 9/20 | Applications of number theory | § 3.7 | § 3.7 (2, 4, 6, 10, 17, 19, 23, 24, 26, 28, 46) |
Wed 9/22 | Applications of number theory (HW 3 due, § 3.4 - § 3.6) | § 3.7 | |
Fri 9/24 | Mathematical induction | § 4.1 | § 4.1 (4, 6, 10, 18, 32, 40, 50) |
Mon 9/27 | Strong induction and well-ordering | § 4.2 | § 4.2 (4, 7, 10, 19, 26, 29, 37) |
Wed 9/29 | Recursive definitions and algorithms (HW 4 due, § 3.7-§ 4.1) | § 4.3, 4.4 | § 4.3 (4, 6, 8, 12, 20, 21, 27, 31), § 4.4 (7, 8) |
Fri 10/1 | Review | ||
Mon 10/4 | MIDTERM 1 | ||
Wed 10/6 | The basics of counting | § 5.1, 5.2 | § 5.1 (8, 16, 19, 24, 30, 55) |
Fri 10/8 | The pigeonhole principle; permutations (HW 5 due, § 4.2-§ 4.4) | § 5.2, 5.3 | § 5.2 (9, 16, 18, 21, 25, 26), § 5.3 (5, 12, 18, 22, 35, 36) |
Mon 10/11 | Permutations, combinations, binomial coefficients | § 5.3, 5.4 | § 5.4 (16, 20, 23, 24, 33) |
Wed 10/13 | Generalized permutations, combinations (HW 6 due, § 5.1-§ 5.3) | § 5.5 | § 5.5 (10, 15, 22, 23, 34, 50) |
Fri 10/15 | Introduction to disrete probability | § 6.1 | § 6.1 (10, 20, 21, 24, 34, 38) |
Mon 10/18 | Probability theory | § 6.2 | § 6.2 (2, 6, 10, 16, 23) |
Wed 10/20 | Bayes' Theorem (HW 7 due, § 5.4, § 5.5, § 6.1) | § 6.3 | § 6.3 (2, 4, 6, 10, 15, 16) |
Fri 10/22 | Expected value and variance | § 6.4 | § 6.4 (4, 13, 24, 26, 28, 29, 38, 39, 40) |
Mon 10/25 | Recurrence relations | § 7.1 | § 7.1 (5, 8, 12, 20, 28, 47) |
Wed 10/27 | Solving linear recurrence relations (HW 8 due, § 6.2, 6.3, 6.4) | § 7.2 | § 7.2 (4, 8, 11, 12, 15) |
Fri 10/29 | Generating functions | § 7.4 | § 7.4 (5, 30, 32, 33, 34, 37, 39) |
Mon 11/1 | Inclusion-exclusion | § 7.5, 7.6 | § 7.5 (8, 24), § 7.6 (6, 8, 10, 15, 26) |
Wed 11/3 | Relations and their representations (HW 9 due, § 7.1, 7.2, 7.4) | § 8.1, 8.3 | § 8.1 (20, 32, 34), § 8.3 (10, 14, 26, 36) |
Fri 11/5 | Closures of relations; equivalence relations | § 8.4, 8.5 | § 8.4 (1, 2, 6, 29), § 8.5 (1, 8, 16, 24, 36, 62) |
Mon 11/8 | Finish equivalence relations | § 8.5 | |
Wed 11/10 | Partial orderings | § 8.6 | § 8.6 (2, 22, 32, 34, 44) |
Fri 11/12 | Review (HW 10 due, § 7.5, 7.6, 8.1, 8.3, 8.4, 8.5) | ||
Mon 11/15 | MIDTERM 2 | ||
Wed 11/17 | Graphs and graph models | § 9.1 | § 9.1 (12, 13, 27, 28) |
Fri 11/19 | Graph terminology and special types of graphs | § 9.2 | § 9.2 (4, 5, 20, 22, 29, 31, 36, 44, 48, 54, 55) |
Mon 11/22 | Representing graphs and graph isomorphism | § 9.3 | § 9.3 (23, 31, 37, 41, 55) (not graded) |
Wed 11/24 | Connectivity and Eulerian circuits (HW 11 due, § 8.6, 9.1, 9.2) | § 9.4, 9.5 | § 9.4 (15, 19, 53), § 9.5 (3,5,7,9) (not graded) |
Fri 11/27 | NO CLASS (Thanksgiving break) | ||
Mon 11/29 | Trees and the number of labeled trees | § 10.1 plus Cayley's Formula | § 10.1 (1, 38) |
Wed 12/1 | Review | ||
Fri 12/3 | Review | ||
Mon 12/13 | FINAL EXAM (11:30am-2:30pm), 155 Dwinelle |