ECS20 Discrete Mathematics for Computer Science, Spring 2018


Announcement:
  1. 4/26: more examples of math induction is posted. Why Induction is Valid
  2. 4/26: Prof. Bai is not available for office hour on May 1 (Tuesday). Before the mid-term on May 3, he will hold the office hours from 4-5:30, April 27 (Friday) and 5-6:30, April 30 (Monday).
  3. 4/30: Partial solutions of homework #4 is available on canvas/files
  4. 4/30: CS Tutoring is hosting a midterm review session for ECS20 this Wednesday (05/02) from 7:10 - 8:30 PM in 1227 Hart Hall

Instructor:
Professor Zhaojun Bai
Office: 3005 Kemper Hall
Phone: 752-4874
Email: zbai@ucdavis.edu

Graudate student instructors:
Ibrahim Ahmed , ibahmed@ucdavis.edu
Deepika Chandrasekaran, dchandrasekaran@ucdavis.edu
Domenic Cianfichi, djcianfichi@ucdavis.edu

Lectures:
Tuesday and Thursday: 9:00am - 10:20am
Wellman 2

Discussions:
Sec.-A01, Monday, 3:10-4:00pm, Olson 205
Sec.-A02, Friday, 11:00-11:50am, Olson 223
Sec.-A03, Tuesday, 1:10-2:00pm, Hart 1130
Sec.-A04, Tuesday, 5:10-6:00pm, Cruess 107

Office hours and locations:
Day Time Place
Monday 9:00-11:00
2:00-3:00
Kemper 55, Deepika
Kemper 3052, Ibrahim
Tuesday 1:30 - 3:00
3:00 - 5:00
Kemper 3005, Bai
Kemper 3052, Ibrahim
Wednesday 5:30-6:30 Kemper 3052, Domenic
Thursday 10:30-12:00
2:00 - 4:00
Kemper 3005, Bai
Kemper 3052, Domenic
Friday 2:00 - 3:00 Kemper 55, Deepika

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 Infor:
Annoucements, handouts and homework assignments will be posted at the following sites. They get updated frequently throughout the quarter:
http://www.cs.ucdavis.edu/~bai/ECS20
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: All 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
4/3 Introduction
Set Theory I
Reading: Chapter 1
Homework #1
4/5 Set Theory II
Relations I
Reading: Chapter 2
(skip sec. 2.7 and 2.10)
4/10 Relations II
Quiz 1 on Homework #1
Homework #2
4/12 Relations III and Functions I Reading: Sections 3.1 - 3.6
4/17 Functions II
Quiz 2 on Homework #2
Homework #3
4/19 Logic and proof techniques I
Reading: Chapter 4 and Section 1.8
Handout: logic
Handout: proof
4/24 Logic and proof techniques II
Quiz 3 on Homework #3
Homework #4
4/26 Logic and proof techniques III
More Examples on Induction
Why Induction is Valid
Announcement
5/1 Integers and integer algorithms I
Midterm review
Reading: Sections 11.1-11.8
Handout: integers
5/3 Midterm Midterm review outline
covers Homework #1-#4
5/8 Integers and integer algorithms II
Counting techniques I
App: integers in cryptology
Handout: counting
Homework #5
5/10 Counting techniques II
Reading: Chapter 5
Examples of combinatorial proof
5/15 Recursion I
Quiz 4 on Homework #5
Reading: Sections 6.6, 6.7 and 6.8
Handout: recurision
Homework #6
5/17 Recursion II
Complexity of the Euclidean algorithm
5/22 Growth of functions
Quiz 5 on Homework #6
Reading: Section 3.9
Handout: big-O
Homework #7
5/24 Graphs and trees I Reading: Chapter 8
Handout: graphs 1/3
5/29 Graphs and trees II
Quiz 6 on Homework #7
Handout: graphs 2/3
Homework #8
5/31 Graphs and trees III
Handout: graphs 3/3
6/5 Introduction to algorithms, guest lecturer: Prof. Koehl
Quiz 7 on Homework #8
Handout: algorithms
Reading: sections 3.8 and 3.9
6/7 no class, final review sessions are scheduled on June 11 and June 12 Final review outline
Final review exercises
6/11 Monday, 9:30-11:00am, Office hour, 55 Kemper Hall (Deepika)
Monday, 6:00-7:30pm, Review session, 179 Chemistry (Bai)
...
6/12 Tuesday, 3:30-5:00pm, Review session, 179 Chemistry (Bai)
Tuesday, 5:00-6:30pm, Office hour, 3052 Kemper (Ibrahim)
...
6/13 Wednesday, 11:30 - 1:00, Office hour, Room 55 (Domenic)
Wednesday, 1:30 - 3:00, Office hour, Room 3005 (Bai)
...
6/14 6:00-8:00pm, Final exam 2 Wellman

Maintained by Zhaojun Bai, bai@cs.ucdavis.edu