## CPS102: Discrete Mathematics for Computer Science

### Textbook:

Discrete Mathematics and Its applications, 6th Edition, Kennth H. Rosen

• Homework: 30%
• Midterm I: 20%, Friday, 02/18/2011, 2:50 pm - 4:05 pm
• Midterm II: 20%, Friday, 04/01/2011, 2:50 pm - 4:05 pm
• Final: 30%, Monday, 05/02/2011, 7:00 pm - 10:00 pm

Please turn in your homeworks at the beginning of the class on the day it is due.
Late homework is not accepted.
The lowest grade of the homework will be dropped.
Homework assignments should be done individually, under Duke's Community Standard.
No collaboration of any kind is allowed on standard homework assignments.

### Important Dates:

 01/26/2011 Drop/Add ends 03/04/2011--03/14/2011 Spring break 03/30/2011 Last day to withdraw 04/27/2011 Undergraduate classes end

### Schdule:

1. 01/13: Logic, quantifiers
2. 01/18: Sets and functions
3. 01/20: Mathematical induction, Homework #1
4. 01/25: Complexity, growth of functions
5. 01/27: Sorting algorithm, part I , Homework #1 Due, Solution
6. 02/01: Sorting algorithm, part II
7. 02/03: Sorting algorithm, part III , Homework #2
8. 02/08: Modular Arithmetic
9. 02/10: Euclidean Algorithm, Homework #2 Due, Solution
10. 02/15: Cryptography
11. 02/17: Homework #3
12. 02/18: Midterm I Solution
13. 02/22: Counting I
14. 02/24: Counting II Homework #3 Due, Solution
15. 03/01: Recurrence relation, linear independence
16. 03/03: Solving linear recurrence relation , Homework #4
17. 03/15: Probability Homework #4 Due, Solution
18. 03/17: Conditional Probability & Independence
19. 03/22: Bayes' Theorem & Random Variable
20. 03/24: Expecations & Variance , Homework #5
21. 03/29: Expectations & Variance II
22. 03/31: Homework #5 Due, Solution
23. 04/01: Midterm II Solution
24. 04/05: Graph
25. 04/07: Matrix , Homework #6
26. 04/12: Connectivity & Isomorphism
27. 04/15: Euler & Hamilton Paths
28. 04/19: Shortest Path Homework #6 Due, Solution