ECS20 Discrete Mathematics for Computer Science, Winter 2020

  1. Department policy on Permission to Add (PTA) (posted Jan. 6)

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

Graudate student instructors:
Jayneel Vora ,
Ji Wang ,
Imran Adham,

Monday, Wednesday and Friday: 10:00am - 10:50am
Scrub Oak Auditorium 160

Section-A01, Wednesday, 1:10-2:00pm, Olson Hall 250 (Adham)
Section-A02, Monday, 4:10-5:00pm, Hoagland Hall 168 (Vora)
Section-A03, Monday, 1:10-2:00pm, Hariing Hall 1204 (Wang)
Section-A04, Thursday, 12:10-1:00pm, Chemistry 176 (Vora)

Office hours and locations:
Day Time Place
Monday 11:30am-12:30pm
2:30 - 4:30pm
3005 Kemper (Bai)
53 Kemper (Wang)
Tuesday 3:30 - 5:30pm 47 Kemper (Adham)
Wednesday 4:30-5:30pm
3005 Kemper (Bai)
53 Kemper (Vora)
Thursday 2:00-4:00pm 53 Kemper (Vora)
Friday 8:30-9:30am
3005 Kemper (Bai)
53 Kemper (Wang)

S. Kipschutz and M. Lipson,
Discrete Mathematics, Third Edition
McGraw-Hill, 2007

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

Online Info:
Academic misconduct policy

Course outline:
  1. Mathematical data types:
    • Sets (Chap.1)
    • Relations (Chap.2)
    • Functions (Chap.3)
  2. Propositional logic and proof techniques (Chap.4 and Secs.1.8 and 11.3)
  3. Integers and integer algorithms (Chap.11)
  4. Counting techniques and recursion (Chap.5 and 6)
  5. Probability (Chap.7)
  6. Graphs and trees (selected from 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 quizzes and exams are closed-book, no notes allowed. Regrading is only considered within three business days from the return day. The request must be submitted in writing.

Lecture contents, handouts and assignments

Date Topics Handouts/Homeworks
1/6 Instruction begins (Introduction)
Set Theory I (Chapter 1)
Homework #1
1/8 Set Theory II ...
1/10 Relations I (Chapter 2) ...
1/13 Relations II and Quiz #1 ...
1/15 Relations III Homework #2
1/17 Functions I (Chapter 3) Homework #3
1/20 Martin Luther King, Jr. Day (university holiday) ...
1/22 Functions II and Quiz #2 ...
1/24 Propositional logic (Chapter 4) Handout #1
1/27 Proof techniques I and Quiz #3
Handout #2
1/29 Proof techniques II ...
1/31 Midterm exam 1 (Chapters 1 - 3) Homework #4
2/3 Proof techniques III (Mathematical Induction) More examples
Why Math Induction works
2/5 Integers and integer algorithms I (Sec.11.1-11.8) Handout #3
App: integers in cryptology
2/7 Integers and integer algorithms II and Quiz #4
Homework #5
2/10 Techniques of counting I (Chap.5) Handout #4
2/12 Techniques of counting II Combinatorial proofs
2/14 Recursion I (Sec.6.6-6.9) and Quiz #5 Handout #5
Homework #6
2/17 President's Day (university holiday) ...
2/19 Recursion II (Sec.6.6-6.9) ...
2/21 Recursion III and Quiz #6 on Homework #6 Handout #6
Homework #7
2/24 Discrete probability I (Sec.7.1-7.5) Handout #7
2/26 Discrete probability II (Sec.7.7-7.8) Handout #8
2/28 Midterm exam 2 (on topics in Hws 4-6) ...
3/2 Graphs and trees I
(selected topics in Chap.8)
Handout #9
3/4 Graphs and trees II ...
3/6 Graphs and trees III and Quiz #7 Homework #8
3/9 Graphs and trees IV ...
3/11 Final review (Instruction ends) Review outline
Review exercises
3/13 no in-person lecture
Prof. Bai offers office hours 9am-11am
(in-person at Kemper 3005 or by email on canvas)
3/17 1:00pm-4:59pm, take-home final exam
(access and upload your final exam on canvas)
Instruction for uploading a pdf file on canvas
Tips for converting a photo to a pdf file

Maintained by Zhaojun Bai,