Math 55: Discrete Mathematics, Spring 2009

Professor Bernd Sturmfels

Office hours: Wednesday, 8:30am - 11:00am, or by appointment
Office: 925 Evans Hall, phone 510 642 4687
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 Monday 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 26
HW2: due February 2
HW3: due February 9
HW4: due February 18
HW5: due February 23
HW6: due March 9
HW7: due March 16
HW8: due March 30
HW9: due April 6
HW10: due April 20
HW11: due April 27 (text and pictures)
HW12: due May 4

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 26, and covers Chapter 1-4 of Rosen. Midterm 2 is held in class on Thursday, April 9, and covers Chapter 1-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 8:00 to 11:00am on Wednesday, May 20, in 234 Hearst Gym, and will cover the material from the entire course.
Review Sessions:
Thursday, May 14, 12-2pm, 740 Evans Hall (Bernd Sturmfels)
Friday, May 15, 1-3pm, 145 McCone Hall (Dustin Cartwright)
Monday, May 18, 5:30-7pm, 200 Wheeler Hall (Patrick LaVictoire)
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. The last week is devoted to discrete mathematics in biology. 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 20 10, 14, 23, 27 January 26
§ 1.2January 20 13, 29 January 26
§ 1.3 January 20 6, 14, 44* January 26
§ 1.4 January 20 7, 9, 23 January 26
§ 1.5 January 22 4, 15 January 26
§ 1.6 January 22 2, 13, 17, 24 January 26
§ 2.1 January 27 5, 8, 21, 28, 38 February 2
§ 2.2 January 27 4, 14, 24, 28, 42* February 2
§ 2.3 January 27 7, 9, 12, 16, 27, 41 February 2
§ 2.4 January 29 9, 16, 18, 31 February 2
§ 3.4 February 3 9, 11, 12*, 17, 21, 29, 31, 32 February 9
§ 3.5 February 5 2, 5, 8, 11, 16, 21, 28, 30, 34 February 9
§ 3.6 February 10 4, 5, 8, 19, 21, 24, 29 February 18
§ 3.7 February 12 2, 7, 10*, 17, 18, 24, 26, 32, 48 February 18
§ 4.1 February 17 4, 6, 10*, 33, 50 February 23
§ 4.2 February 17 3, 8, 11, 25, 29 February 23
§ 4.3 February 19 4, 6, 7, 13, 20, 21, 31, 32 February 23
§ 4.4 February 19 2, 3, 11, 20 February 23
Review February 24 Chapters 1-4
First Midterm Exam: February 26
§ 5.1 March 3 8, 16, 19, 24, 30, 55 March 9
§ 5.2 March 3 9, 16, 18, 21, 25, 26 March 9
§ 5.3 March 5 5, 12*, 18, 22, 35, 36 March 9
§ 5.4 March 5 16, 20, 23, 24, 33 March 9
§ 5.5 March 10 10, 15*, 22, 23, 34, 50 March 16
§ 6.1 March 12 10, 20, 21, 24, 34, 38 March 16
§ 6.2 March 12 2, 6, 10, 16, 23 March 16
§ 6.3 March 17 2, 4, 6, 10, 11, 16 March 30
§ 6.4 March 19 4, 6, 13, 24, 26, 28, 29, 38*, 39, 40 March 30
§ 7.1 March 31 5, 8, 17, 20, 28, 47 April 6
§ 7.2 March 31 4, 7*, 11, 18 April 6
§ 7.5 April 2 8, 20, 24, 26 April 6
§ 7.6 April 2 6, 7, 10, 15, 26, 27 April 6
Review April 7 Chapters 1-7
Second Midterm Exam: April 9
§ 8.1 April 14 5, 32, 34, 46 April 20
§ 8.3 April 14 10, 14, 22, 36 April 20
§ 8.4 April 14 17, 18, 19 April 20
§ 8.5 April 16 1, 16, 24, 62 April 20
§ 8.6 April 16 22, 24, 32, 34, 43 April 20
§ 9.1 April 21 13, 27 April 27
§ 9.2 April 21 5, 20, 29, 31, 36, 44, 48, 55 April 27
§ 9.3 April 23 24, 28, 44, 54 April 27
§ 9.4 April 23 13, 14, 17, 22, 53 April 27
§ 10.1 April 28 3, 13*, 18, 22, 24, 44 May 4
§ 10.4 April 30 4, 11, 12, 17, 18, 24, 25 May 4
§ 10.5 April 30 8, 15, 18, 19 May 4
DM in Biology May 5 Special bonus homework May 6
Tropical Math May 7
Final Exam: May 20 at 8:00 AM in 234 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.