Math 55: Discrete Mathematics, Spring 2010

Professor Bernd Sturmfels

Office hours: Tuesday 9:45-11:00, Wednesday 11:00-12:00, after class, or by appointment.
Office: 925 Evans Hall
email: bernd@math.berkeley.edu

Our class meets Tuesdays and Thursdays, 8:00-9:30am in 145 Dwinelle

Teaching assistants:

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

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, 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 27
HW2: due February 3
HW3: due February 10
HW4: due February 17
HW5: due March 3
HW6: due March 10
HW7: due March 17
HW8: due March 31
HW9: due April 14
HW10: due April 21
HW11: due April 28
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 18, and covers Chapter 1-3 of Rosen. Midterm 2 is held in class on Thursday, April 1, and covers Chapter 1-6 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 13, in 237 Hearst Gym, and will cover material from the entire course.
Here are the questions and solutions for the final exam.

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, 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:

Lecture Date Homework problems Due date
§ 1.1 January 19 10, 14, 23, 27 January 27
§ 1.2January 19 13, 29 January 27
§ 1.3 January 19 6, 14, 44* January 27
§ 1.4 January 19 7, 9, 23 January 27
§ 1.5 January 21 4, 15 January 27
§ 1.6 January 21 2, 13, 17, 24 January 27
§ 2.1 January 26 5, 8, 21, 28, 38 February 3
§ 2.2 January 26 4, 14, 24, 28, 42 February 3
§ 2.3 January 26 7, 9, 12, 16, 27, 41 February 3
§ 2.4 January 28 9, 16, 18*, 31 February 3
§ 3.4 February 2 9, 11, 12, 17, 21, 29, 31, 32 February 10
§ 3.5 February 4 2, 5, 8, 11, 16, 21, 28, 30, 34 February 10
§ 3.6 February 9 4, 5, 8, 19, 21, 24, 29 February 17
§ 3.7 February 11 2, 7, 10, 17, 18, 24, 26, 32*, 48 February 17
Review February 16 Chapters 1-3
First Midterm Exam: February 18
§ 4.1 February 23 4, 6, 10*, 33, 50 March 3
§ 4.2 February 23 3, 8, 11, 25, 29 March 3
§ 4.3 February 25 4, 6, 7, 13, 20, 21, 31, 32 March 3
§ 4.4 February 25 2, 3, 11, 20 March 3
§ 5.1 March 2 8, 16, 19, 24, 30, 55 March 10
§ 5.2 March 2 9, 16, 18, 21, 25, 26 March 10
§ 5.3 March 4 5, 12, 18, 22, 35, 36 March 10
§ 5.4 March 4 16, 20, 23, 24*, 33 March 10
§ 5.5 March 9 10, 15, 22, 23, 34, 50* March 17
§ 6.1 March 11 10, 20, 21, 24, 34, 38 March 17
§ 6.2 March 11 2, 6, 10, 16, 23 March 17
§ 6.3 March 16 2, 4, 6, 10, 11, 16 March 31
§ 6.4 March 18 4, 6, 13, 24, 26, 28, 29, 38*, 39, 40 March 31
Review March 30 Chapters 1-6
Second Midterm Exam: April 1
§ 7.1 April 6 5, 8, 17, 20, 28, 47 April 14
§ 7.2 April 6 4, 7, 11, 18 April 14
§ 7.5 April 8 8, 20, 24, 26 April 14
§ 7.6 April 8 6, 7, 10*, 15, 26, 27 April 14
§ 8.1 April 13 5, 20, 32, 34, 46 April 21
§ 8.3 April 13 10, 14, 22, 36 April 21
§ 8.4 April 13 17, 18, 19 April 21
§ 8.5 April 15 1, 16*, 24, 62 April 21
§ 8.6 April 15 22, 32, 34, 43 April 21
§ 9.1 April 20 13, 27 April 28
§ 9.2 April 20 5, 20, 29, 31, 36, 44, 48, 55 April 28
§ 9.3 April 22 24, 28, 44, 54 April 28
§ 9.4 April 22 13, 14*, 17, 22, 53 April 28
§ 10.1 April 27 3, 13, 18, 22, 24, 44 not graded
§ 10.4 April 29 4, 11, 12, 17, 18, 24, 25 not graded
§ 10.5 April 29 8, 15, 18, 19 not graded
Final Exam: May 13 at 7:00-10:00pm in 237 Hearst Gym (exam group 16)


The official syllabus for Math 55:
  • Propositional logic, quantifiers, rules of inference, proof techniques (Rosen Chapter 1)
  • Sets, functions, countability and uncountable sets (Sections 2.1-2.3, and part of 2.4 on cardinality)
  • Algorithms, halting problem (Section 3.1), undecidability (covered in lecture)
  • Division algorithm, modular arithmetic, primes, GCD (Sections 3.4-3.5)
  • Euclidean algorithm, modular exponentiation, solving conguences, Chinese Remainder Theorem, applications to cryptography (Sections 3.6-3.7)
  • Induction and recursion, recursive algorithms (Sections 4.1-4.4; revisit 2.4 for summations)
  • Counting, pigeon hole principle, permutations and combinations, binomial coefficients, distributions, Stirling numbers (Sections 5.1-5.5)
  • Discrete probability theory, conditional probability, independence, random variables (Sections 6.1-6.2)
  • Bayes' Theorem and applications (Section 6.3)
  • Expected value, variance, Chebyshev's inequality (Section 6.4)
  • Recurrence relations and generating functions (Sections 7.1-7.2 and Examples 10-15 in 7.4)
  • Inclusion-exclusion, derangements, formula for Stirling numbers (Sections 7.5, 7.6)
  • Relations, directed graphs, transitive closure, equivalence relations, set partitions, partial orders (Section 8.1, part of 8.3 on digraphs, 8.4-8.6)
  • Graphs, isomorphism, connectivity (Sections 9.1-9.4)
  • Trees, spanning trees, minimum-weight spanning trees (Sections 10.1, 10.4-10.5)
  • Additional topics to be included as time permits.