ECS20 Discrete Mathematics for Computer Science, Winter 2015

Office hours and locations:

Lecture contents, handouts and assignments
Date Topics Handouts/Homeworks
1/5 Introduction
Set Theory I (1.1-1.3)
Homework #1
1/7 Set Theory II (1.4-1.7) ...
1/9 Relations I (2.1-2.4) ...
1/12 Relations II (2.5, 2.6, 2.8, 2.9) Homework #2
1/14 Relations III ...
1/16 Functions I (3.1, 3.2) ...
1/19 MLK Holiday, no class ....
1/21 Functions II (3.3, 3.4) Homework #3
1/23 Functions III (3.5, 3.6) ...
1/26 Logic I (Chap.4) ...
1/28 Midterm exam 1 Review outline #1
1/30 Logic II and Proof techniques I Handout on proof techniques
Homework #4/Part I (no need to turn in)
Homework #4/Part II, Due 4:00pm, Feb.6
2/2 Proof techniques II Why mathematical induction is valid
More examples on mathematical induction
Additional reading: sections 1.8 and 11.3.
2/4 Integers and integer algorithms I (11.4--11.8) Summary notes
App: modular function in cryptology
2/6 Integers and integer algorithms II Homework #5
2/9 Counting techniques I (Chap.5) Lecture Notes
2/11 Counting techniques II ...
2/13 Counting techniques III Handout and additional examples
Exampels of combinatorial proof
2/16 Presidents' Day, no class ...
2/18 Recursion I (6.6--6.8) Homework #6
Handout on recursion
2/20 Recursion II Example: Euclidean algorithm
2/23 Recursion III and review Midterm #2 Review outline
2/25 Midterm exam 2 Homework #7
2/27 Growth of functions (3.8--3.9) Handout on the growth of functions
3/2 Intro to Discrete Probability (7.1-7.3) Handout on discrete probability
3/4 Graphs and trees I (8.2, 8.3, 8.11) Homework #7 due
Handout on graphs and trees
Homework #8
3/6 Graphs and trees II (8.4,8.5) ...
3/9 Graphs and trees III (8.7, 8.9) Homework #9 (last one)
Handout on graphs and trees (updated)
3/11 Graphs and trees IV (8.8) ...
3/13 ... Final review outline
3/16, Mon. Instruction ends Homework #9 due
3/17, Tue. Official hours at Kemper Room 53
9am -- 11am, and 2pm -- 4pm
3/18, Wed. Office hours 9am -- 11am at Kemper 53
Final exam, 1:00-3:00, 1003 Giedt

Professor Zhaojun Bai
Office: 3005 Kemper Hall
Phone: 752-4874
Email: zbai at

Graudate student instructors:
Chengming Jiang, cmjiang at (section A01)
Saeedeh Komijani, skomijani at (section A02)
Stewart He, sthe at (section A03)



Class webpages and homework box:

S. Kipschutz and M. Lipson,
Schaum's outline of Theory and Problems of Discrete Mathematics, Third Edition
McGraw-Hill, 2007

Grade of C- or better in Mathematics 16A, 17A or 21A

Course outline:
  1. Mathematical data types:
    • Sets (Chap.1)
    • Relations (Chap.2)
    • Functions (Chap.3)
  2. Propositional logic and proof techniques (Chap.4, Sec.1.8)
  3. Integers and integer algorithms (Chap.11)
  4. Counting techniquesand recursion (Chaps.5 and 6)
  5. Probability (Chap.7)
  6. Graphs and trees (Chap.8-10)

Course objectives:
The purpose of the course is to introduce fundamental techniques in discrete mathematics for applications in computer science. One of the central objectives is to learn methods of proof that transform intuition into mathematical proof, and to stress the distinction between proof and opinion. Hence the course will be mathematical in two senses: first, it will contain specific techniques in discrete mathematics, and second, through examples and exercises, it will raise the students general mathematical sophistication, i.e., ability to deal with and create complex and convincing arguments.

Grading breakdown: All exams are closed-book, no notes allowed.
Regrading is only considered within one week (7 days) from the return day. The request must be submitted in writing.

Maintained by Zhaojun Bai,