Discrete Mathematics

Math 55: Discrete Mathematics, Spring 2012

Professor Bernd Sturmfels

Office hours: Monday 9:00-11:00, Wednesday 11:00-12:00.
Office: 925 Evans Hall
email: bernd@math.berkeley.edu

Our class meets Tuesdays and Thursdays, 8:00-9:30am in 10 Evans.


Review for final exam: Everyone is welcome at any of the following events:

The GSIs hold their regular office hours during RRR week. In addition, special office hours are held by Andrew Marks on Wednesday, May 2, 11-1; by Bernd Sturmfels on Tuesday, May 8, 8-10; by Ralph Morrison on Wednesday, May 9, 2-4.

Graduate Student Instructors:

For extra help: check out the Student Learning Center. Their study group meets 1:00-2:00pm Tuesdays and Thursdays in 201A Chavez.

Text book: Kenneth H. Rosen, Discrete Mathematics and its Applications, 7th edition (custom version), McGraw-Hill.

Homework: 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, and that it is your own work, but only one of the problems (marked after the due date by a star) is fully graded. Homework solutions will be posted here on the respective due date:
HW1: due January 25
HW2: due February 1
HW3: due February 8
HW4: due February 15
HW5: due February 22
HW6: due March 7
HW7: due March 14
HW8: due March 21
HW9: due April 11
HW10: due April 18
HW11: due April25
HW12: not graded

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 is held in class on Thursday, February 23, and covers up to Chapter 5 of Rosen. Midterm 2 is held in class on Thursday, March 22, and covers up to Chapter 7 of Rosen. A review session is held on Tuesday before each midterm. No books, notes, calculators, scratch paper or collaboration are permitted at any exam. Student photo ID and a blue-covered exam booklet are 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.
Midterm 1: Questions and solutions.
Midterm 2: Questions and solutions.

Final Exam: The final exam will be held from 7:00pm to 10:00pm on Thursday, May 10, in 220 Hearst Gymnasium and will cover material from the entire course.
Final Exam: Questions and solutions.


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.

Course outline: The textbook covers the subject in detail. Students are expected to prepare for each lecture by reading the assigned sections in advance. In lecture, I will outline what is important, give my own perspective, 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:

Lecture Homework problems Due date
1.1. Propositional Logic January 17: 10, 18, 26, 38 January 25
1.2. Applications of Prop. Logic January 17: 34 January 25
1.3. Propositional Equivalences January 17: 24, 30, 40, 63 January 25
1.4. Predicates and Quantifiers January 17: 14, 28, 32 January 25
1.5. Nested Quantifiers January 19: 8, 10*, 20 January 25
1.6. Rules of Inference January 19: 4, 16, 20 January 25
1.7. Introduction to Proofs January 24: 6, 14, 18, 24 February 1
1.8. Proof Methods and Strategies January 24: 8, 10*, 34, 42 February 1
2.1. Sets January 26: 10, 23, 32, 46 February 1
2.2. Set Operations January 26: 2, 16, 26, 42 February 1
2.3. Functions January 26: 6, 8, 12, 20, 44 February 1
2.4. Sequences and Summations January 31: 26, 32, 34, 46 February 8
2.5. Cardinality of Sets January 31: 10, 28 February 8
4.1. Divisibility and Modular Arithmetic February 2: 10, 16, 20, 40* February 8
4.2. Integer Representations February 2: 4, 7, 10, 28 February 8
4.3. Primes and GCD February 2: 12, 32, 44, 52 February 8
4.4. Solving Congruences February 7: 6, 19, 20, 29, 30, 38* February 15
4.6. Cryptography February 9: 1, 4, 23, 24, 27 February 15
5.1. Mathematical Induction February 14: 4, 6, 10, 18, 32, 54 February 22
5.2. Strong Induction and Well-Ordering February 14: 4, 10, 26 February 22
5.3. Recursive Definitions February 16: 4, 6, 8, 12, 20*, 51 February 22
Review February 21: Chapters 1,2,4,5
First Midterm Exam: February 23
6.1. The Basics of Counting February 28: 8, 16, 24, 45, 50 March 7
6.2. The Pigeonhole Principle February 28: 4, 7, 22, 38*, 40 March 7
6.3. Permutations and Combinations March 1: 6, 18, 24, 42 March 7
6.4. Binomial Coefficients March 1: 8, 24, 33 March 7
6.5. Generalized Permutations March 6: 10, 22, 34, 42, 50, 66 March 14
7.1. Intro to Discrete Probability March 8: 12, 21, 26, 36 March 14
7.2. Probability Theory March 8: 2, 8, 13, 16*, 24, 34 March 14
7.3. Bayes' Theorem March 13: 2, 6, 8, 17, 18 March 21
7.4. Expected Value and Variance March 15: 4, 14, 16*, 28, 30, 44, 48 March 21
Review March 20: Chapters 6,7
Second Midterm Exam: March 22
8.1. Recurrence Relations April 3: 5, 8, 12, 20, 30 April 11
8.2. Solving Linear Recurrences April 3: 2, 8, 11, 18, 46 April 11
8.4. Generating Functions April 5: 6*, 8, 14, 20, 22, 36 April 11
8.5. Inclusion-Exclusion April 10: 8, 10, 20, 26 April 18
8.6. Applications of I-E April 10: 6*, 10, 13, 20 April 18
9.1. Relations April 12: 3, 4, 10, 22, 42, 44 April 18
9.3. Representing Relations April 12: 4, 18, 32 April 18
9.4. Closures of Relations April 17: 9, 10*, 17, 24 April 25
9.5. Equivalence Relations April 17: 6, 16, 44, 55, 62 April 25
10.1. Graphs and Graph Models April 19: 13, 14, 28 April 25
10.2. Graph Terminology April 19: 10, 20, 26, 35, 42 April 25
10.3. Graph Isomorphism April 24: 9, 22, 44, 58, 68 not graded
10.4. Connectivity April 24: 8, 14, 22, 38 not graded
10.5. Euler and Hamilton Paths April 26: 8, 10, 26, 46 not graded
10.6. Shortest-Path Problems April 26: 4, 18 not graded
Final Exam: Thursday, May 10 at 7:00-10:00pm in 220 Hearst Gymnasium. (exam group 16)