ECS20: Discrete Mathematics for Computer Science, Spring 2008
- Lecture:
- 115 Hutchison, M.W.F. 10:00am - 10:50am
- Discussion:
- Sec.20-A01, 80 ScoSci, Friday, 1:10pm - 2:00pm
- Sec.20-A02, 1060 Bainer, Friday, 2:10pm - 3:00pm
- Professor:
- Zhaojun Bai,
3005 Kemper Hall, 752-4874, bai@cs.ucdavis.edu
- Office Hours:
- Mondays and Wednesdays, 2-3
- Fridays, 11 - 12
- Teaching Assistant:
- Mr. Kefeng Tan, kftan@ucdavis.edu
- Office hours: Wednesdays 3:00 - 5:00, Thursdays 1:00 - 3:00
- Place: 53 Kemper Hall
- TA Website
- Textbook :
-
Kenneth H. Rosen, Discrete Mathematics and Its Applications, Sixth Edition
- Prerequisite
- Math 21A
- Course Outline
- The foundations: logics and proofs
- Basic structures: sets, functions and sequences
- The fundamentals: algorithms and the integers
- Induction and recursion
- Counting techniques
- Introduction to graphs and trees
- Course objectives:
-
The purpose of the course is to introduce fundamental techniques
in discrete mathematics for application in computer science.
One of the central objectives is to teach methods of proof that transform
intuition into 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 exercies, it will raise the students general
mathematical sophistication, i.e., ability to deal with and create complex
and convicing arguments.
- Homeworks and Exams:
- There will be about 8 homework assignments.
- The material in this class can only be learned by doing
lots of problems, so the homework is very important.
- Your homework should be your own work. You are permitted to
work in groups on homework. It is a matter of
intellectual honesty to (a) write your homework strictly by yourself, and
(b) acknowledge in it any ideas you
got from others (including books and papers in the literature).
- Homeworks are to be turned in at the beginning
of lecture on the due date,
or be deposited in the ECS20 Homework Box in Room 2131, Kemper Hall
by 4:00pm on the due date (no email,please).
-
No late homework will be accepted!
- If you cannot complete an assignment by the due date, hand in whatever
you have done in order to receive partial credit.
- Selected problems on each assignment will be graded and
credited.
- All exams are closed-book, no notes allowed.
- There will be no early or late makeup midterm;
instead the average of your grades on
homeworks, the other midterm and final will be used.
- Grading:
- Grading breakdown:
- homework: 30%
- Midterm exams: 40%
- Final exam: 30%
Regrading of homeworks and midterm exams is only considered
within one week (7 days) from the return day. The request must
be submitted in writing.
- On-line Info:
- Class webpage: http://www.cs.ucdavis.edu/~bai/ECS20
class annoucements, lecture notes, homework assignments etc, will
be available at this site.
- Discussion group: ucd.class.ecs20.d (to be confirmed)
Watch this space for the progress of the course, notes and assignments
- 3/31:
- Course organization and annoucements
- Lecture: proposition and compound propositions
- Notes #1
- Reading: section 1.1
- 4/2:
- Lecture: logical equivalences, predicates and quantifiers
- Notes #2
- Reading: sections 1.2 and 1.3
- Homework #1,
due 4:00pm, April 9 (extend to April 11)
- 4/4
- Lecture: (1) predicates and quantifiers (cont'd), and (2) Sets
- Reading: section 2.1
- 4/7
- Lecture: Sets and set operations
- Notes #3
- Reading: sections 2.1 and 2.2.
- 4/9
- Lecture: Functions
- Notes #4
- Reading: section 2.3
- Announcement: No TA's office hour today. Please come to see
Professor if you have question.
- 4/11,
- Lecture: Sequences and summations
- Notes #5
- Reading: section 2.4
- Homework #1 due
- Homework #2, due 4:00pm, April 18
- 4/14
- Lecture: Summations, and Algorithms
- Reading: section 2.4 and section 3.1
- 4/16
- Lecture: Algorithms and complexity
- Notes #6
- Reading: section 3.1 and section 3.3
- 4/18
- Lecture: Algorithms, complexity and big-O notation
- Reading: sections 3.1, 3.2 and 3.3
- Notes #7
- Homework #2 due
- Homework #3, due 4:00pm, April 28
- 4/21
- 4/23
- 4/25
- Lecture: (1) Big-O, Big-Omega, Big-Theta notations.
(2) Integer division
- Reading: (1) section 3.2, and (2) section 3.4
- 4/28
- Lecture: Integer division and modular arithmetic
- Reading: section 3.4
- Notes #8
- Homework #4, due 4:00pm, May 5
- 4/30
- Lecture: Greatest common divisor
- Reading: section 3.5 and the Euclidead algorithm part of section 3.6
- Notes #9
- 5/2
- Lecture: Proof techniques
- Reading: sections 1.6-1.7
- Notes #10
- 5/5
- 5/7
- Lecture: Recursively defined functions, Fibonacci numbers and
complexity of the Euclidean algorithms
- Reading: section 4.3 (first half)
- Notes #12
- 5/9
- Lecture: Recursive and iterative algorithms
- Reading: section 4.4
- Notes #13
- 5/12
- 5/14,
- 5/16
- Lecture: Basic counting
- Reading: section 5.1
- Notes #14
- 5/19
- Lecture: The pigeonhole principle and Permutations and
Combinations
- Reading: sections 5.2 and 5.3
- Notes #15 and
Notes #16
- 5/21
- Lecture: Permutations and Combinations, Binomial coefficients
- Reading: sections 5.3 and 5.4
- Notes #16
- Homework #7, due 4:00pm, May 30
- 5/23
- Lecture: Recurrence relations and solving linear
recurrence relations I
- Reading: sections 7.1 and 7.2
- Notes #17
- 5/26, Monday Holiday, no class
- 5/28
- Lecture: Solving linear recurrence relations II.
- Reading: section 7.2
- Notes #17
- 5/30
- Lecture: Solving linear recurrence relations III.
- Reading: section 7.2
- Homework #7 due
- Homework #8, due 4:00pm, June 5 (last one)
- 6/2
- Lecture: Intro. to Graph I
- Notes
- 6/4,
- Lecture: Intro. to Graph II
- Notes
- Instruction ends
- Office hours for the final week held at Room 2236, Kemper Hall
- June 10, 10-12
- June 12, 10-12
- Review outline
- A sample final:
Problems and
Solutions
- 6/12 (Thursday), 1:00-3:00pm, Final Exam,
115 Hutchinson
Reminder: It is a closed-book exam, no notes
allowed
Maintained by Zhaojun Bai, bai@cs.ucdavis.edu