Math 55 - Discrete Mathematics - Fall 2010


Lectures: Monday, Wednesday, Friday 11am-12:00pm, in 10 Evans

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.

Teaching assistants:

FINAL REVIEW SESSIONS:


Course 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 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.

Textbooks

Required text: Kenneth H. Rosen, Discrete mathematics and its applications, 6th edition, McGraw-Hill. We will cover material from Chapters 1-10.

Problem Sets

Homework will be assigned weekly. Up to twenty problems covering the lecture material of each week will be due at the beginning of your section on Wednesday of the following week. No late homework can be accepted. Your TA will verify that you are working the assigned problems, but only one of the problems (marked after the due date by a star) is fully graded. Homework solutions will be posted below on the respective due date.

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.

Quizzes

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.

Midterms

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-.

Final

The final exam will be on Monday, December 13, from 11:30 to 2:30, in 155 Dwinelle.

Grading

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.

Syllabus

The textbook covers the subject in detail, so I expect students to prepare for each lecture by reading the assigned sections in advance. In lecture, I will outline what is important, give my own perspective on some topics, present examples, and answer questions. Participation in the class, even in this large lecture course, is strongly encouraged. Here is the detailed plan for the entire semester:
DateTopics BookHomework 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