ECS20 Discrete Mathematics for Computer Science, Winter 2020

Announcements:

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

Instructor:

Professor Zhaojun Bai

Office: 3005 Kemper Hall

Phone: 752-4874

Email: zbai@ucdavis.edu

Graudate student instructors:

Jayneel Vora , jrvora@ucdavis.edu

Ji Wang , jiiwang@ucdavis.edu

Imran Adham, imadham@ucdavis.edu

Lectures:

Monday, Wednesday and Friday: 10:00am - 10:50am

Scrub Oak Auditorium 160

Discussions:

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 5:00-7:00pm	3005 Kemper (Bai) 53 Kemper (Vora)
Thursday	2:00-4:00pm	53 Kemper (Vora)
Friday	8:30-9:30am 4:00-6:00pm	3005 Kemper (Bai) 53 Kemper (Wang)

Textbook:

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

Prerequisite:

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

Online Info:

Academic misconduct policy

canvas

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:

Grading breakdown:

• Quizzes: 36%
• Midterm: 24%
• Final exam: 40%

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	...