Discrete Structures

Computer Science 2800
Cornell University
Fall 2011

Instructor: John Hopcroft
Office Hours: Wed 10 - 11 and Friday 2:30 - 3:30 in 5144 Upson Hall

Lecture Time: MWF 1:25-2:15
Lecture Place: Hollister Hall B14
Course Web page: http://www.cs.cornell.edu/courses/cs2800/2011fa/

Head TA: Ms. June Andrews contact: [ja378 cornell.edu]

Other TAs and Office hours: Staff Page

Office hours:

Monday 11:00-12:00 - Yipu, Upson 328B
Monday 12:00-1:00 - Doo San, Upson 328B
Tuesday 11:00-12:00 - Dan, Upson 328B
Tuesday 4:00-5:00 - Brooke, Upson 328B
Wednesday 10:00-11:00 - Prof Hopcroft, Upson 5144
Wednesday 3:30-4:30 - Felipe & Limin, Upson 328B
Wednesday 4:30-5:30 - Jisun, Upson 328B
Thursday 11:00-12:00 - Scott, Upson 328B
Thursday 3:00-4:00 - Jung & Ziyu, Upson 328B
Friday 10:00-11:00 - Mark, Erika, & Jaya, Upson 328B
Friday 2:30-3:30 - Prof Hopcroft, Upson 5144
Friday 3:30-4:30 - Eunsol, Upson 328B
Friday 3:30 - 5:30 - June, Rhodes 657
Saturday 2:00-3:00 - Laura, Upson 328B
Sunday 10:00 - 11:00 - Doo San, Upson 328B

Course Email
Please email questions to:
CS2800-L@cornell.edu
Your question will be forwarded to all TAs, for the quickest possible response.

Textbook

Discrete Mathematics and Its Applications, Rosen; McGraw-Hill (edition does not matter)

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

Graded homework assignments can be picked up in class.

All homeworks must follow the style guide: Style Guide

All regrades must be submitted within 7 days of returned homework, with the regrade sheet filled out and attached: Regrade Sheet

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

Late days are granted only under very special circumstances.

Weights: homeworks 50%, mid-terms 2*10% and final 20%. And we will invent where the last 10% comes from(TBD).

Grades will be pulled from a straight scale 90-A, 80-B, 70-C, etc

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)

Definitions: (Useful Definitions to be added to as the course progresses)

Induction: (A complete explanation of Induction by Doo San)

Lecture Notes for Fall 2011, the final selection of provided lecture notes:

Lecture Wed Sept 21: (Applications, Encryption, and Primes)
Lecture Fri Sept 23: (Encryption, Euler's Phi Function, Fermat's Little Theorem)
Lecture Mon Sept 26: (RSA, Birthday Paradox, Euclid's Extended Algorithm)
Lecture Wed Sept 28: (Coming from Mark: Intro to Combinatorics)
Lecture Fri Oct 7: (Friday before break, check the review for Oct 12)
Lecture Wed Oct 12: (Balls & Buckets, Groups, Symmetries, Tic-Tac-Toe, and Burnside's Lemma)
Lecture Mon Oct 17: (Monty Hall, Poker, and the Birthday Paradox)
Lecture Wed Oct 19: (Probability Space and Functions)
Lecture Mon Oct 24: (Problems Represented as Graphs)

Lecture notes for the Spring semester can be downloaded here.

Sections of the book for Spring, with page numbers of the 6th edition:

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)