Computer Science:50:198:171
Mathematical Foundations of Computer Science
Spring 2012
General Information  Online Resources  Calendar Problem Sessions

General Information

Class Time TTh 9:30-10:50am
Room BSB 336
Course Info Course Information (also in pdf )
Text Mathematics: A Discrete Introduction, 2nd edition, Edward Scheinerman, Brooks/Cole.
Instructor
Name Rajiv Gandhi
Email rajivg AT camden DOT rutgers DOT edu
Office 311 Business and Science Building
Office hours TTh 11:00 - noon
If you can not make it during the office hours, please send me email or see me after class so that we can arrange to meet at another time.

Online Resources

Calendar

This calendar will be updated as the semester progresses. For most lectures a lecture outline will be posted. The lecture outline serves as a record of what is covered in class. It also helps you to focus more on the lecture and less on copying down what is written on the board. Also, some topics covered in class may not be covered in sufficient depth in the text and in that case the lecture outline would be useful. It should not be considered as a substitute for reading the text. I will post the readings a couple of days ahead of the lecture. In the "Reading" column, 'S' stands for the text book by Scheinerman, LL stands for the lecture notes by Lehman and Leighton, and KT stands for Algorithm Design by Kleinberg and Tardos. Solutions to homeworks will be handed out in class on the day the homework is due.

Lec Date Topics Reading Homework
1. Tue, Jan 17 What is a set?, Multiplication Rule S(2.7, 2.9) Hw 1t
2. Thu, Jan 19 Multiplication Rule, Permutations, Set Operations, r-Permutations S(2.7, 2.8) Hw 1h
3. Tue, Jan 24 Inclusion-Exclusion, Combinations S(2.7, 2.11, 3.18, 3.16) Hw 2t
4. Thu, Jan 26 Combinations, Generalized Permutations S(3.16, 3.17) Hw 2h
5. Tue, Jan 31 Generalized Combinations, Proofs that Count S(3.17) Hw 3t
6. Thu, Feb 02 Proofs that Count, Functions,Pigeon hole principle S(5.23, 5.24) Hw 3h
7. Tue, Feb 07 Probability S(6.29, 6.30) Hw 4t
8. Thu, Feb 09 Conditional Probability S(6.31), LL(Ch. 19) Hw 4h
9. Tue, Feb 14 Conditional Probability, Independence S(6.31, 6.30), LL(Ch. 20) Hw 5t
10 Thu, Feb 16 Exam I
11. Tue, Feb 21 Inclusion-Exclusion, Random Variables, Expectation S(6.32, 6.33), LL(Ch. 21,22) Hw 6t
12. Thu, Feb 23 Linearity of Expectation S(6.32, 6.33) Hw 6h
13. Tue, Feb 28 Variance, Geometric and Binomial Distribution S(6.33) Hw 7t
14. Thu, Mar 01 Coupon Collectors Problem, Probability Review, Logic S(Ch. 1) Hw 7h
15. Tue, Mar 06 Proofs S(Ch. 1) Hw 8t
16. Thu, Mar 08 Proofs S(Ch. 1) Hw 8h
Tue, Mar 13 Spring Break
Thu, Mar 15 Spring Break
17. Tue, Mar 20 Exam II
18. Thu, Mar 22 Mathematical Induction S(7.38, 4.21) Hw 9h
19. Tue, Mar 27 Mathematical Induction S(4.21) Hw 10t
20. Thu, Mar 29 Graphs S(Ch. 9) Hw 10h
21. Tue, Apr 03 Trees S(Ch. 9) Hw 11t
22. Thu, Apr 05 Trees, Eulerian Graphs S(9.50, 9.51) Hw 11h
23. Tue, Apr 10 Matchings Hw 12t
24. Thu, Apr 12 Logarithms review, Euclid's GCD alg S(7.35)
25. Tue, Apr 17 Exam III Hw 13t
26. Thu, Apr 19 Extended GCD algorithm (lecture by Darakhshan Mir) Hw 13h
27. Tue, Apr 24 Extended GCD algorithm (lecture by Darakhshan Mir) Hw 14t
28. Thu, Apr 26 RSA Cryptosystem (lecture by Darakhshan Mir)

Problem Sessions

Session Date Problems
1. Thu, Jan 19 problems
2. Thu, Jan 26 problems
3. Thu, Feb 02 problems
4. Thu, Feb 09 problems
5. Thu, Feb 16 problems
6. Thu, Feb 23 problems
7. Thu, Mar 01 problems
8. Thu, Mar 08 problems
9. Thu, Mar 22 problems
10. Thu, Mar 29 problems
11. Thu, Apr 05 problems
12. Thu, Apr 12 problems
13. Thu, Apr 19 problems
14. Thu, Apr 26 problems