Discrete Structures

Computer Science 2800
Cornell University
Spring 2013

Final exam is on Friday May 17, 2:00 pm – 4:30 pm in Statler Auditorium

Instructor: Rafael Pass

Time: MWF 1:25-2:15
Place: Uris Hall G01

Office hour: you can meet me after class, or on Mondays at 2:20-3:00 in Upson 5139

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

Head TA: Karn Seth

Other TAs and Office hours: Staff Page

Course Admin: Maria Witlox (mpr13 at cornell.edu)

Textbook

Pass and Tseng: Lecture Notes in Discrete Structures.

These notes may be updated during the semester.

(Please let me know if you find any typos or mistakes.)

The following textbook is also useful (but is not required):

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

Course Administration

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 Maria so he can register you.  You can check your grades in CMS. 

Homeworks and Grading

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

• Prelim 1 is on Feb 20
• Prelim 2 is on April 10
• Final exam is on Friday May 17, 2:00 pm – 4:30 pm in Statler Auditorium

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 6 (beginning of class),
• HW2 due on Feb 13 (beginning of class)
• Prelim I on Feb 20 (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 Feb 27 (beginning of class)
• HW4 due on March 6 (beginning of class)
• HW5 due on March 13 (beginning of class)
• HW6 due on April 3 (beginning of class)
• Prelim II on April 10 (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 17 (beginning of class)
• HW8 due on April 24 (beginning of class)
• HW9 due on May 1 (beginning of class)
• Final exam is on Friday May 17 from 2:00 pm to 4:30 pm
• 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.

To request a regrade for homeworks or prelims, download and print the regrade request form and follow the instructions on it.

Weights (subject to change): homeworks 30%, mid-terms 2*15%, final 35% + 5% quality of solutions.

Homework Policy

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.

Syllabus and Reading (subject to change)

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

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