CS 2800 covers the mathematics underlying most of computer science. Topics include sets, functions, relations, mathematical notation and proof techniques, induction, propositional and predicate calculus, combinatorics, discrete probability theory, basic number theory, graphs, and finite-state machines. These topics are discussed in the context of applications in various areas of computer science as appropriate.
Time and Place
MWF 1:25–2:15pm, Olin 155.
Pre- or corequisite
One programming course or permission of instructor.
- Dexter Kozen, 5143 Upson, (607) 255-9209. Office hours MWF 2:30-3:30pm
- Michael George, 4105A Upson, (607) 255-9834. Office hours MWF 10:00-11:00am
Kenneth Rosen, Discrete Mathematics and Its Applications, 7th Edition, McGraw-Hill, 2012. ISBN 0-073-38309-0.
Note that, although the text was designed for this course, there will be topics covered in lecture that are not in the text, and there will be topics in the text that are not covered in lecture. You are responsible for topics covered in lecture and for any assigned reading in the text.
The syllabus lists the topics to be covered in lecture and the corresponding chapters in the text. This is subject to change. We will expect you to have read the appropriate sections of the text in advance of the lectures.
Supplementary course material will be posted to the handouts page. Check often for new material.
We will be using Piazza as an online discussion forum. Piazza allows for open discussions of all course-related questions. You are encouraged to post any questions you might have about the course material. The course staff monitor Piazza closely and you will usually get a quick response. If you know the answer to a question, you are encouraged to post it.
By default, your posts are visible to the course staff and other students, and you should prefer this mode so that others can benefit from your question and the answer. However, you can post privately so that only the course staff can see your question, and you should do so if your post might reveal information about a solution to a homework problem. You can also post anonymously if you wish. If you post privately, we reserve the right to make your question public if we think the class will benefit.
Everyone who preregistered for the course should already be signed up. If you have never used Piazza before, or if you did not preregister for the course, visit the Piazza CS 2800 page to sign up.
Piazza is the most effective way to communicate with the staff outside of office hours. Please avoid email if Piazza will do, except for notifications regarding homework extensions and exam conflicts as noted below.
Broadcast messages from the course staff to students will be sent using Piazza and all course announcements will be posted there, so check in often!
You can check your grades, submit homework, and request regrades in CMS. Please check your grades regularly to make sure we are recording things properly. The system also provides some grading statistics. There is a help page with instructions.
Staff members, along with their email addresses and office hours, are listed on Piazza.
There will be regularly scheduled homework sets due at 11:59pm on the due date. Homework must be submitted electronically to CMS.
Late Homework: It is expected that homework will be turned in on time. Assignments can be turned in up to 24 hours late with a penalty of 10% for the assignment. Beyond that time, late homework will not be be accepted except in an emergency. If a genuine emergency exists, please inform the course staff as soon as possible.
Deadline Extensions: Each student is entitled to one extension of the homework deadline during the semester, if the student has a valid excuse and requests the extension at least twelve hours in advance of the deadline. Please notify the instructor by email. In the event of such a request, the deadline will typically be extended 72 hours. The new deadline is hard—no extra late day, and CMS does not allow a grace period to be set for extensions. The definition of valid excuse is quite liberal and will be interpreted to include excessive workload in other classes, travel for academic reasons or for a job interview, minor illness, or other reasons at the instructor's discretion. Extensions for major illness or family emergency do not count against this entitlement.
Submitting Homework: You must submit an electronic version of your homework to CMS. You may either type it using typesetting software—we recommend LaTeX—or write it by hand and scan it. If you handwrite and scan, please write on only one side of the paper (the writing on the other side often bleeds through), make sure the scan is readable with good contrast, and save your scan in .pdf format. It is your responsibility to check that your scan is legible. It is probably a good idea to keep your handwritten original in case of any difficulties. Scanners are available in the computer labs. Submit your scanned .pdf file to CMS.
Collaboration: On the homework, you are encouraged to discuss general approaches and techniques with others, but you must write up the solutions by yourself, with no collaboration. Please see the section on Academic Integrity below for further clarification of this policy.
There will be two 50-minute in-class prelim exams and a 2½-hour final exam. Exam dates are listed on the syllabus page.
Exams are closed book.
No makeup exams will be given. If you need to miss an exam due to illness, family emergency, religious holiday, or other reasonable excuse at the instructor's discretion, we will take an appropriately weighted average of your other two exams. Please notify the instructor by email as early as possible. Please see the Registrar's exam page for policies and procedures.
Your course grade will be based on the homework and exams, weighted as follows.
- 40% homework
- 30% prelims (15% each)
- 30% final exam
Grading Criteria: We will be looking for clear, concise, and correct solutions.
Homework Regrades: If you believe your solution to a homework question was correct and it was marked incorrect, then you should write an explanation of the grading error and submit it electronically in CMS. Regrade requests must be made within one week of the time that the homework scores are released.
Exam Regrades: Write up an explanation of the grading error, attach it to your exam, and submit it to the TA who graded the question. Alternatively, you can leave the exam and written explanation with the instructor. Regrade requests must be made within one week of the time that the exam scores are released.
You may request a regrade for a correct solution that was marked incorrect. In general, we will not consider regrade requests that simply argue about the amount of partial credit assigned.
The utmost level of academic integrity is expected of all students. Violations will be penalized severely. Please read the following carefully.
On the homework, you may discuss general approaches and techniques with others, but the specifics of the solution must be your own work. You must write up (and understand) the solutions by yourself, with no collaboration. In particular, you may not work from written notes taken in discussion with others. Under no circumstances may you hand in work done with or by someone else under your own name or share solutions with anyone else.
You must acknowledge by name anyone with whom you collaborated and any outside sources (apart from the course text) that you consulted, including Internet sources.
All exams are closed book. You may not give nor receive assistance from anyone else during an exam.
You may not give any hints or post any material that might be part of a solution publicly on Piazza. If your question necessarily includes such material, post privately.
If you are unsure about what is permissible and what is not, please ask.
- The Essential Guide to Academic Integrity at Cornell
- Computer Science Department Code of Academic Integrity
- Explanation of AI Proceedings
We provide appropriate academic accommodations for students with special needs and/or disabilities. Requests for academic accommodations are to be made during the first three weeks of the semester and must be accompanied by official documentation. Please register with Student Disability Services in 420 CCC to document your eligibility.