Cornell University

Spring 2011

Instructor: Rafael Pass

Time: MWF 1:25-2:15

Place: **Upson B17** (and not Phillips
203 as listed in the course catalog)

Course Web page: http://www.cs.cornell.edu/courses/cs2800/2011sp/

Head TA: Edward Lui

Other TAs and Office hours: Staff Page

Course Admin: Randy Hess (rbhess at cs.cornell.edu)

Discrete Mathematics and Its Applications, Rosen;
McGraw-Hill (6^{th} edition)

We are using the course management system, **CMS**. Please login to
http://cms.csuglab.cornell.edu/
and check whether you are registered. There will be a list of courses you are
registered for, and Com S 2800 should be one of them. If not, please send
your full name and Cornell netid to Randy so he can register you. You can
check your grades in CMS.

There will be **9
homeworks**, 2 in-class **prelims**
and a **final exam**.

- Prelim
1 is on
**Feb 23** - Prelim
2 is on
**April 13** - Final
exam is at
**2pm on Tuesday, May 17 in Barton Hall 100 West-Main Floor**, and is 2.5 hours long

The homeworks can be found in CMS. Graded homework assignments can be picked up in Upson 360 on weekdays during 12pm – 4pm.

Important dates

- HW1 due on Feb 9 (beginning of class),
- HW2 due on Feb 16 (beginning of class)
**Prelim I**on Feb 23 (in class)- Practice problems: Rosen: 2.2.13 (= Section 2.2, #13), 2.3.19, 2.4.35, 8.1.9, 8.5.3, 8.4.29, 1.6.27, 1.7.7, 4.1.31, 4.2.3, 4.3.7
- HW3 due on March 2 (beginning of class)
- HW4 due on March 9 (beginning of class)
- HW5 due on March 16 (beginning of class)
- HW6 due on April 8 (beginning of class)
**Prelim II**on April 13 (in class)- Practice problems: Rosen: 3.4.5 (= Section 3.4, #5), 3.5.31, 3.6.23b, 3.7.7, 5.1.31, 5.2.15, 5.3.33, 5.4.7, 7.5.7, 6.1.9
- HW7 due on April 20 (beginning of class)
- HW8 due on April 29 (beginning of class)
- HW9 due on May 6 (beginning of class)
**Final exam**is at 2pm on Tuesday, May 17 in Barton Hall 100 West-Main Floor, and is 2.5 hours long- Practice problems: Rosen: 2.1.9 (= Section 2.1, #9), 2.2.15, 2.3.11, 2.4.37, 8.5.1, 1.6.23, 1.7.17, 4.1.5, 4.2.3, 4.3.9, 3.4.7, 3.5.17, 3.6.23a, 3.7.5, 5.1.35, 5.2.5, 5.3.11, 5.4.21, 7.5.5, 6.1.21, 6.2.23, 6.3.9, 6.4.7, 1.1.27c, 1.2.15, 1.3.9, 9.2.35, 9.3.35, 9.5.39, 9.8.11, 12.3.21, 12.3.31, 12.4.5

Homeworks need to be handed in before the beginning of class.

Late days are granted only under very special circumstances, but to compute the final HW grade, we drop the HW with the lowest score.

** **

Weights: homeworks 35%, mid-terms 2*15% and final 35%.

You are free to collaborate with other students on the homework, but you must turn in your own individually written solution and you must specify the names of your collaborators. It is a violation of this policy to submit a problem solution that you are unable to explain orally to a member of the course staff. It is a violation of the Academic Integrity Code to copy any one else’s solution.

- Sets, Functions and Relations : (Rosen: Ch 2.1-3, 2.4:158-160, 8.1,8.5,8.4:544-548)
- Proof techniques: Basic proof strategies (Rosen: Ch 1.6-7), Induction (Rosen: Ch 4.1-2,4.3:294-299)
- Number theory (Rosen: Ch 3.4-5, 3.6:227-229, 3.7)
- Counting/combinatorics (Rosen: Ch 5.1-4, 7.5)
- Probability (Rosen: Ch 6)
- Logic (Rosen: Ch 1.1-4)
- Graph theory (Rosen: Ch 9.1-5,9.8)
- Finite automata and regular languages (Rosen: Ch 12.2-4)

Each module corresponds to 4-5 lectures (i.e., 1.5 week).