CMPSC 360: Discrete Mathematics for Computer Science
Spring 2015

Course Summary

  • Concepts and techniques used in computer science and their applications.
  • Topics include logic, proofs, modular arithmetic, polynomials, graphs, counting, probability, countability, computability.
  • Applications include RSA, error-correcting codes, secret sharing, hashing, load balancing, limits of computation.
Induction illustration

Course Staff

Office Phone Email Office Hours
Instructor Sofya Raskhodnikova IST 343F x3-0608 sofya@cse M 3PM-5PM
Instructor Yanling Wang IST 346B x5-7364 yuw17 MTu 11AM-12PM
TA Doug Mercer IST 359 dougmercer Th 3PM-5PM
TA Om Thakkar IST 359 x5-9185 omthkkr W 10AM-12PM
TA Yibo Wu IST 343D yxw185 TuF 10AM-11AM

Textbooks

There is no book covering all the material in this course. Instead we will follow the Berkeley CS70 Lecture notes (BN0, BN1, BN2, etc. in the reading assignments below refer to Berkeley Notes 0, 1, 2, etc.). You can download them from Angel. We also will use the following free textbooks:

Tentative Schedule

Lec.DateSyllabusReadingHandouts/Homework
1 Jan 12 Introduction. Propositional logic. (Slides). BN0,BN1, Hammack § 2.6. (Optional: Hammack § 1-2.5). General Course Information, Collaboration and Honesty Policy, HW0 out
2 Jan 14 Propositional logic. (Slides). BN1. (Optional: Hammack § 2.7-2.12.) HW0 due, HW 1 out.
3 Jan 16 Propositional logic, start proofs (Slides). BN2
Jan 19 No class: MLK Day
4 Jan 21 Proofs. (Slides). BN2. (Also recommended: Hammack § 4-6.) HW1 due, HW2 out.
5 Jan 23 Proofs. (Slides). BN2. (Also recommended: Hammack § 7-9.)
6 Jan 26 Induction. (Slides). BN3. (Also recommended: Hammack § 10.)
7 Jan 28 Induction. (Slides). BN3. (Also recommended: Hammack § 10.) HW 2 due, HW 3 out
8 Jan 30 Strong induction. (Slides). BN3. (Also recommended: Hammack § 10.)
9 Feb 2 Stable marriage. (Slides). BN4
10 Feb 4 Stable marriage. (Slides). BN4 HW 3 due, HW 4 out
11 Feb 6 Stabel marriage. Modular arithmetic. (Slides). BN4, BN5
12 Feb 9 GCD, inverses and extended GCD. (Slides). BN5
13 Feb 11 Chinese Remainder Theorem. (Slides). BN5 HW 4 due, practice midterm out
14 Feb 13 Public-key cryptography. RSA. (Slides by Dr. Wang; Dr. Raskhodnikova was at AAAS Annual Meeting, giving a talk on privacy). BN6
15 Feb 16 Polynomials. (Slides). BN7
16 Feb 18 Review. (Slides). BN7 HW5 out
Feb 18 Exam 8:15-10:15pm in 119 Osmond
17 Feb 20 Polynomials. Secret sharing. (Slides). BN7
18 Feb 23 Secret sharing. (Slides). BN7
19 Feb 25 Error-correcting codes: erasures. (Slides). BN8 HW5 due, HW6 out
20 Feb 27 Error-correcting codes: general errors. (Slides). BN8
21 March 2 Error-correcting codes. (Slides). BN8
22 March 4 Graphs. (PSU classes canceled for the day.) BN on graphs HW6 due, HW7 out
23 March 6 Graphs. (Slides). BN on graphs
March 9-13 No class: Spring Break
24 March 16 Graphs. (Slides). BN on graphs
25 March 18 Graphs. (Slides). BN on graphs HW7 due, HW8 out
26 March 20 Counting. (Slides). BN12. (Also recommended: Hammack § 3.1-3.4.)
27 March 23 Counting. Combinatorial proofs. (Slides). BN13
28 March 25 Counting. Inclusion-Exclusion Principle. (Slides). Hammack § 3.5 HW8 due, practice midterm 2 out
29 March 27 Basic probability. (Slides). BN13
30 March 30 Basic probability. (Slides). BN13
31 Apr 1 Review. (Slides). HW9 out
Apr 1 Exam 8:15-10:15pm in 119 Osmond
32 Apr 3 Combining events. Conditional probability. (Slides). BN14
33 Apr 6 Conditional probability. Bayes' rule. (Slides). BN14
34 Apr 8 Bayes' rule. Total probability rule. (Slides). BN14 HW9 due, HW10 out
35 Apr 10 Independence. Mutual and pairwise independence. Product rule. (Slides). BN14
36 Apr 13 Applications: hashing and load balancing. (Slides). BN15
37 Apr 15 Applications: hashing and load balancing. (Slides). BN15 HW10 due, HW 11 out
38 Apr 17, Random variables. Distribution of a random variable. Binomial distribution. (Slides). BN16
39 Apr 20 Expectation. Linearity of expectation. (Slides). BN16
40 Apr 22 Review of random variables and expectations. (Slides). BN16 HW11 due, HW12 out
41 Apr 24 Variance. (Slides). BN17
42 Apr 27 Variance. Independent random variables. (Slides). BN17 Practice final exam out.
43 Apr 29 Infinity and countability, diagonalization, existence of undecidable problems, Halting problem. (Slides). BN10, BN11 (from Spring 2015) HW12 due (not graded).
44 May 1 Review. (Slides).
May 4 Final Exam 10:10am-12:00pm in 010 SPARKS
Sofya Raskhodnikova