Math 55: Discrete Mathematics, Spring 2010

Professor Bernd Sturmfels

Office hours: Tuesday, 9:00-11:00 or Wednesday, 11:00-12:00
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 25

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 25, and covers Chapter 1-4 of Rosen. Midterm 2 is held in class on Thursday, April 8, 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.

Final Exam: The final exam will be held from 7:00pm to 10:00pm on Thursday, May 13, and will cover the material from the entire course.

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 19 10, 14, 23, 27 January 25
§ 1.2January 19 13, 29 January 25
§ 1.3 January 19 6, 14, 44 January 25
§ 1.4 January 19 7, 9, 23 January 25
§ 1.5 January 21 4, 15 January 25
§ 1.6 January 21 2, 13, 17, 24 January 25
§ 2.1 January 26 5, 8, 21, 28, 38 February 1
§ 2.2 January 26 4, 14, 24, 28, 42 February 1
§ 2.3 January 26 7, 9, 12, 16, 27, 41 February 1
§ 2.4 January 28 9, 16, 18, 31 February 1
§ 3.4 February 2 9, 11, 12, 17, 21, 29, 31, 32 February 8
§ 3.5 February 4 2, 5, 8, 11, 16, 21, 28, 30, 34 February 8
§ 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
§ 4.1 February 16 4, 6, 10, 33, 50 February 22
§ 4.2 February 16 3, 8, 11, 25, 29 February 22
§ 4.3 February 18 4, 6, 7, 13, 20, 21, 31, 32 February 22
§ 4.4 February 18 2, 3, 11, 20 February 22
Review February 23 Chapters 1-4
First Midterm Exam: February 25
§ 5.1 March 2 8, 16, 19, 24, 30, 55 March 8
§ 5.2 March 2 9, 16, 18, 21, 25, 26 March 8
§ 5.3 March 4 5, 12, 18, 22, 35, 36 March 8
§ 5.4 March 4 16, 20, 23, 24, 33 March 8
§ 5.5 March 9 10, 15, 22, 23, 34, 50 March 15
§ 6.1 March 11 10, 20, 21, 24, 34, 38 March 15
§ 6.2 March 11 2, 6, 10, 16, 23 March 15
§ 6.3 March 16 2, 4, 6, 10, 11, 16 March 29
§ 6.4 March 18 4, 6, 13, 24, 26, 28, 29, 38, 39, 40 March 29
§ 7.1 March 30 5, 8, 17, 20, 28, 47 April 5
§ 7.2 March 30 4, 7, 11, 18 April 5
§ 7.5 April 1 8, 20, 24, 26 April 5
§ 7.6 April 1 6, 7, 10, 15, 26, 27 April 5
Review April 6 Chapters 1-7
Second Midterm Exam: April 8
§ 8.1 April 13 5, 32, 34, 46 April 19
§ 8.3 April 13 10, 14, 22, 36 April 19
§ 8.4 April 13 17, 18, 19 April 19
§ 8.5 April 15 1, 16, 24, 62 April 19
§ 8.6 April 15 22, 24, 32, 34, 43 April 19
§ 9.1 April 20 13, 27 April 26
§ 9.2 April 20 5, 20, 29, 31, 36, 44, 48, 55 April 26
§ 9.3 April 22 24, 28, 44, 54 April 26
§ 9.4 April 22 13, 14, 17, 22, 53 April 26
§ 10.1 April 27 3, 13, 18, 22, 24, 44 May 4
§ 10.4 April 29 4, 11, 12, 17, 18, 24, 25 May 4
§ 10.5 April 29 8, 15, 18, 19 May 4
Final Exam: May 13 at 7:00 PM in ?????? (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.