CS 70
Discrete Mathematics
for Computer Science

 Prof. Luca Trevisan

Spring 2007
Tuesdays and Thursdays  3:30-5:00pm, 
2 LeConte



- [ News ] - [ Course information ] - [ Homework ] - [ Lecture notes ] - [ Vahab's sections ] - [ Alex's section ] -


5/18 The final exam is today, Friday 5/18, 12:30pm-3:30pm. The exam is at 105 Northgate. Here's how to get from Soda to 105 Northgate directly:

Follow the green arrow. The green X marks the location of the room; the red zone is the CITRIS construction site:

5/12 An extra review session will be held on Thursday, May 17th, 3-6pm. This is specifically designed for those who can not come to the Sunday's review session or have last minute questions. Location: 306 Soda Hall.
5/11Final review problems have been posted ([ PS ] [ PDF ]). The review session will work best if you attempt to solve each of them before the review session. These problems are not exhaustive — a particular topic not getting covered here does not mean that it will be completely absent from the final.
5/11 All homework solutions (1-12) are now posted below.
CS70 finals week schedule
Sun 05/06 Mon 05/07 Tue 05/08 Wed 05/09 Thu 05/10 Fri 05/11 Sat 05/12
  1-2p - Vahab's regular OH, 511 Soda

3-4p - Alex's regular OH, 511 Soda

3:30p-5p - Last lecture, 2 LeConte 5p - HW12 due, 283 Soda

4:30p-7:30p - Last supplementary section, 320 Soda

Sun 05/13 Mon 05/14 Tue 05/15 Wed 05/16 Thu 05/17 Fri 05/18 Sat 05/19
5-8p - Final exam review session, 306 Soda; Review problems - [ PS ] [ PDF ]       2p-4p - Luca's extra OH, 679 Soda

3p-6p - Extra review session (Vahab). Location: 306 Soda

8:30p-10p - Alex's extra OH, Cafe Milano

12:30p-3:30p - FINAL EXAM in 105 Northgate; you may use up to three hand-written 8.5"x11" pages of notes summer

5/7Homework 12 has been updated to clarify the wording of problem 1(b). The deadline for homework 12 has been extended to Wednesday 05/09, at 5pm.
5/3Homework 12 (the last homework!) has been posted, and will be due on Tuesday 05/08.
5/3Notes for Lecture 27. Corrected typo in Notes for Lecture 24
5/3 Notes for Lecture 26
4/28 Homework 11 posted. It will be due on Thursday, May 3rd. You can use the normal c.d.f. calculator for some of the problems.
4/24No class and no office hours on Thursday April 26 because of the faculty retreat
4/24 For the rest of the semester, I (Alex) will run an extra, non-required "supplementary section" on Wednesdays, 4:30pm-6pm. The first one will be tomorrow, Wed 04/25, in 320 Soda. I will not prepare a specific plan for the sections, so bring your own questions. One rule — no questions about the current homework. Anything else goes.
4/19 Notes for lectures 23 and 24 are posted
Homework 10 posted.
4/12 Homework 9 posted.
4/10 Midterm 2 is today, in-class. You may use 2 pages of notes. The midterm will cover all of the material through last Tuesday's lecture (variance), with an emphasis on material presented after the the first midterm.
4/9 Quick solutions to the midterm review problems have been posted: [PDF]
4/6 Some midterm review problems have been posted: [PDF]; more might be posted later.
4/4 Homework 7 and 8 solutions have been posted.
4/3 Reminder: Midterm 2 will be in class next Tuesday, 4/10. There will be a review session on Monday, 4/9, 4pm-6pm, 306 Soda. Review problems will be posted shortly.
3/22 Homework 8 posted (will be due after spring break)
3/21 Notes for lectures 18 and 19 posted
3/15 HW7 is posted.
3/13Posted notes for lecture 16
3/12 Posted notes for lecture 15
3/8 Posted HW6 below; note that, for this week only, it will be due on Wednesday, March 14, at 2:30pm
3/7 Posted notes for lecture 14
3/5 HW5 has been graded and may be picked up from the box outside 581 Soda (along with other homeworks that weren't picked up in section)
3/4 Vahab's office hour is moved from Monday 1-2 pm to Tuesday 11am-12pm for the last minute questions. Location: 511 Soda.
3/3 Additional office hours before the midterm:
Prof. Trevisan - Monday (03/05), 4:30pm-5:30pm, 679 Soda.
Alex - Monday (03/05), 10am-11:30am, 611 Soda.
3/2 Solutions to all of the homeworks up to now are now posted below
3/2 More midterm review problems are now available. Please look through all the problems in parts 1 and 2 of the review handout, try to solve the ones that you feel you need review on the most, and bring all your questions to the midterm review session tonight.
Midterm review, part 2: [PS] [PDF]
Midterm review, part 1: [PS] [PDF] (fixed bugs in problem 2)
A recap of topics we've covered thus far: [PS] [PDF]
3/1 Reminder: Midterm 1 will be in-class on Tuesday 3/6. The midterm will be closed-lecture-notes, but you may bring a 8.5"x11" sheet of notes (single-sided).
3/1 There'll be a midterm review session tomorrow (Friday, 03/02) in 306 Soda from 5pm until 7pm (we may stay around until 8pm if there's enough demand)
2/28 Some midterm review problems have been posted: [PS] [PDF]; more will be posted later
2/27 If you still don't have enough people in your group for the secret sharing exercise on HW5, you may use the shares for "Alice", "Bob", and "Charlie" (SIDs 10000001, 10000002, and 10000003, respectively).
2/22 Graded homeworks get passed out in discussion sections. If you don't pick yours up in section, it will be in a box outside Alex's office (581 Soda).
Homework 5 has been posted (and updated again at 3pm on Thursday 02/22)
Enter your student ID to get your secret share for HW5:
2/22 Notes for lectures 9 and 11 re-posted with better-quality pictures. Notes for lecture 12 posted
2/20 Posted notes for lecture 11
2/16 Alex's office hours for Monday 02/19 (President's Day) will be 10pm-11pm at Cafe Milano (on Bancroft across from Sproul Hall) instead of the usual 3-4pm slot in Soda.
2/14 Posted Homework 4
2/8 Midterm dates posted below


Textbook: The lecture notes are the main reference. The following textbook is also recommended for further reading



Homeworks are due in the CS70 drop box in 283 Soda at 2:30pm on Tuesdays. Graded homeworks are returned in section; homeworks not picked up in section will be in a box outside 581 Soda.


  1. Jan 16, Lecture 1. Contents of the course. Boolean operations. [notes]. Rosen 1.1
  2. Jan 18, Lecture 2. Proof techniques (contrapositive, contradiction, cases). [notes]. Rosen 1.2-1.7
  3. Jan 23. Lecture 3. Mathematical induction. [notes]
  4. Jan 25. Lecture 4. Strong induction. [notes]
  5. Jan 30. Lecture 5. The stable matching problem. [notes]
  6. Feb 1. Lecture 6. More on the stable matching algorithms. Modular arithmetic. [notes]
  7. Feb 6. Lecture 7. Euclid's GCD algorithm. [notes - same as for lecture 6]
  8. Feb 8. Lecture 8. Finding inverses — the extended GCD algorithm. [notes - same as for lecture 6]
  9. Feb 13. Lecture 9. Polynomials. [notes]
  10. Feb 15 Lecture 10. Secret Sharing. [notes - same as for lecture 9]
  11. Feb 20. Lecture 11. Error-correcting codes. [notes]
  12. Feb 22. Lecture 12. Introduction to graphs. [notes]
  13. Feb 27. Lecture 13. Necessary and sufficient conditions for a graph to have an Eulerian tour or path. [notes - same as for lecture 12]
  14. Mar 1. Lecture 14. The hypercube. Hamiltonian cycles and paths. [notes]
    Mar 6. Midterm 1
  15. Mar 8. Lecture 15. Introduction to counting. [notes]
  16. Mar 13. Lecture 16. Inclusion-exclusion formula. Introduction to probability. [notes]
  17. Mar 15 Lecture 17. The Monty Hall problem. Conditional probabilities and independence. [notes - see notes for previous class and next class]
  18. Mar 20. Lecture 18. Mutual independence. Computing the probability of the union and intersection of events. [notes]
  19. Mar 22. Lecture 19. Random variables and expectation. [notes]
  20. Apr 3. Lecture 20. Independence of random variables, variance, standard deviation, concentration around the expectation. [notes]
  21. Apr 5. Lecture 21. The binomial distribution and the Poisson distribution. [Notes]
    Apr 10. Midterm 2
  22. Apr 12. Lecture 22. The geometric distribution and the coupon collector's problem. [Notes]
  23. Apr 17. Lecture 23. I.i.d. random variables and the law of large numbers. [notes]
  24. Apr 19. Lecture 24. Continuous random variables and the Normal distribution. [notes]
  25. Apr 24. Lecture 25. The central limit theorem. [same notes as lecture 24]
    Apr 26 No lecture
  26. May 1. Lecture 26. The Chernoff bound. Lying with statistics. [notes]
  27. May 3. Lecture 27. Infinity and diagonalization. [notes]

tentative schedule

Lectures 15-17 (March 8-15): counting and basic probability

Lectures 18-19 (March 20-22): conditional probability

Lectures 20-22 (April 3-12): expectation, linearity of expectation, variance, concentration of probability

April 10: Midterm 2. Syllabus: lectures 1-20

Lectures 23-25 (April 17-24): IID random variables, Chernoff bounds, and applications

Lectures 26-29 (April 26-May 8): infinity, diagonalization and halting problem