# CS 2800 Syllabus, Fall 2017

## Topics

This course covers the mathematical concepts that underlie computer science, including:

• induction
• combinatorics
• basic probability
• sets, functions and relations
• number theory
• regular expressions and finite automata
• graph theory
• basic propositional and first-order logic

Careful mathematical reasoning and argument are a major theme of the course. Students are required to write a large number of clear, rigorous proofs and to work with precise definitions.

## Websites and information

• Lecture summaries and office hours are on the course website

• We will be using Piazza for all course announcements. Piazza is also a good place to ask questions about the course. Please enroll yourself.

## References

We will use the textbook "Mathematics for Computer Science" (MCS) by Lehman, Leighton, and Meyer. It is freely available.

The textbooks "Lecture Notes in Discrete Structures" by Pass and Tseng. and "Discrete Mathematics and Its Applications" by Rosen have been used in past semesters, and may serve as helpful additional references.

We will also periodically post topical references in the lecture notes.

## Exams and Assignments

• two evening prelims (roughly 1/6 each),
• a final exam (roughly 1/3),
• weekly homework assignments (roughly 1/3)

We often grade individual problems on an A/B/C/D scale, with an A indicating mastery, a B indicating a flawed solution that demonstrates a good understanding of the problem, and a C indicating major misunderstanding or lack of clarity, and a D indicating that you drew a picture of your cat.

A/B/C/D problem scores do not translate linearly to final course grades. If you get all A's on the homework and exams, you may not get an A in the course (you'll probably get an A+). If you get all B's, that doesn't guarantee a B. There are many factors that go into my determination of final course grades.

In an ideal world, everybody would get an A+; of course this also means it's possible for everyone to get a C. In my experience, the median final course grade has usually been a B or B+. I will post grade estimates after each of the prelims.

Assignments will be due Monday at noon. They should be submitted on Gradescope. We will accept late assignments with a penalty until Tuesday at noon (the penalty will be calculated so that 2 late assignments will lower the average B student to a B-). In the case of unforseeable circumstances (e.g. a death in the family or a fire in your dorm), you should talk to the professors; we may give additional extensions.

You may create the PDF files however you want (for example by scanning legible handwritten responses), but we encourage you to typeset them using LaTeX. Please check that you have handed in the right file by downloading it and comparing it to the original. Saying that you accidentally handed in the wrong homework does not count as an excuse!

Regrade requests for homework assignments should be submitted on Gradescope, within a week of when grades are released. Regrade requests for exams should be submitted through the homework handback room. We will regrade the entire exam or problem set; your score may go up or down.

## Collaboration Policy

The types of problems assigned in this class lend themselves naturally to a two-step approach. First, you have to understand the question and devise a solution. Second, you have to clearly describe your solution.

During the first phase, you are encouraged to work together and consult outside references. However, you should do the second phase completely on your own.

While writing your solutions, you must not consult any notes.. Do not sit next to the whiteboard that contains the formula that you and a friend devised. Do not look at anything on the web. Do not consult the notes you took during office hours. Don't do anything you wouldn't do in an exam situation. If you find you are stuck, set your submission aside, consult your notes, and then restart the question you were working on.

You may not copy any part of someone else's solution. To do so is a violation of the academic integrity code.

## Special Needs

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.