# Important note

This is the first semester in which CS 2800 has mandatory discussion sections. This change has impacts on scheduling, assignments, grades, and other things. As such, there will be a bit of experimentation, and this syllabus is subject to change during the course of the semester. Any changes will be reflected here, announced on Piazza, and announced in class.

You are strongly encouraged to give regular feedback. The easiest way to do so is by filling out the forms in the pinned piazza post. They will remain there all semester.

# Topics

This course is different from many CS courses; especially beginning level courses. We do not require any programming (indeed, it is rarely discussed). Rather, this course has the flavor of a university-level mathematics course.

## Skills

Throughout the course we will focus on

Definitions
clear descriptions of terms. For the most part, all of the words we use will have crisp definitions
Proofs
arguments; sequences of logical steps, starting from agreed upon facts or assumptions and leading to a desired conclusion.

These skills are critical in many areas of computer science. Clear definitions are very similar to specifications of functions, classes, or programs. Writing and working with definitions will help you write good specifications.

The ability to write proofs and reason logically is critical for writing code that works. It is also critical for reasoning about programs more generally. Reading and writing proofs will also make you communicate more clearly, and will help you evaluate evidence and come to solid conclusions.

## Structures

The lecture schedule outlines the topics we will cover. In addition to providing lots of practice and examples for the skills listed above, they are all useful in various areas of computer science:

Basic toolssets, functions, and relations
These basic objects are useful for modeling a large variety of problems. Sets are simply collections of objects, be they the set of pages on a website, a set of users, or more abstract objects like the set of possible traces through a program. Functions model input/output relationships, and can be used to represent programs and data structures. Relations model more general kinds of relationships between objects, such as the "friend" relationship in a social network.
Number theory
We will study properties of the integers, as well as a new kind of number-like object called a modular number. modular numbers are useful for reasoning about remainders; we will see applications to hashing and cryptography. Modular numbers also have applications in digital circuits, for example to implement error correcting codes.
Automata
Automata are simple models of computers. After giving formal definitions, we will study the limits of computation, and will also show how the computational power of automata can be described with the high level language of regular expressions. Automata have applications in compilers, networks, and in the theoretical study of the limits of computation. Regular expressions are also useful for text processing.
Combinatorics
Combinatorics is the art of counting things without listing them. It is useful for the analysis of algorithms.
Probability
Probability allows reasoning about uncertain events, and assigning likelihoods to various outcomes. Probability has applications in artificial intelligence, systems, and the design of randomized algorithms.
Metalogic
We will apply the logical tools we've used all semester to study logic itself. Metalogic has applications in program verification and security, as well as in programming language design.

# 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 do not follow any single textbook particularly closely. The best resource are the lecture notes posted on the course website.

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.

The textbook "Introduction to Automata Theory, Languages, and Computation" by Hopcroft and Ullman is an excellent reference on automata theory.

• two evening prelims (roughly 15% each),
• a final exam (roughly 30%),
• homework assignments due every two weeks (roughly 30%, graded for correctness and clarity)
• discussion quizzes and worksheets (roughly 10%, graded only for completion)

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 directly 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.

Unless specified otherwise, assignments will be due Fridays at 5:00 PM. They should be submitted on Gradescope. We will accept late assignments until Saturday at 5:00 PM. You may submit one late assignment with no penalty; subsequent late assignments will have a 50% penalty applied. In the case of unforseeable circumstances (e.g. a death in the family or a fire in your dorm), you should contact us; we may give additional extensions.

Assignments may be completed individually or in pairs. Both students in a group are expected to understand and have contributed to all parts of the assignment.

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 and exams should be submitted on Gradescope, within a week of when grades are released. We will regrade the entire exam or problem set; your score may go up or down.

# Discussion sections

This semester we are introducing mandatory discussion sections. This is the most requested change to CS 2800. We are still refining the details, so please bear with us if anything changes.

## Discussion Evaluation

Participation
Participation is a combination of attendance, in-section engagement and participation in group work. If participation in class feels intimidating or uncomfortable, please talk to your section leaders.
Worksheets
Worksheets will be distributed in section and are due in section the following week. Worksheets are designed to be completed in groups of three to four students during section time. However, each student is required to turn in their own handwritten solution. Worksheets will be graded for completion, not correctness, but will have TA comments on how to improve your solution. Completion will only be granted if a reasonable attempt has been made at every question on the worksheet. Partial completion will not be granted for only attempting a fraction of the worksheet questions. However, if you turn in a partially completed worksheet, we will provide feedback on the questions that were attempted. Because worksheets are graded for completion, don’t be afraid of messing up! Making mistakes and getting feedback is part of the learning process.
Quizzes
There will be a short, multiple-choice quiz every week. This quiz requires access to a web browser; please bring a mobile device or laptop.

## Expectations

Be present. Not only is attendance mandatory, but presence is also mandatory. This means in addition to showing up to section, we require you to be an active participant in section. In effect, ask questions, engage in discussion and keep personal electronics out of sight unless otherwise told. If you have a disability that requires the use of an electronic device, please contact Student Disability Services at 607-254-4545 and the instructor for a confidential discussion of your individual needs. If a one-time event prevents you from attending section, email your section TAs at least 24 hours before your section.

Be helpful. There are a plethora of ways to assist your fellow peers during section. One major way is by asking questions; if you have a question there is a high chance that your classmates have the same question. If you find

Be respectful. Everyone—the instructor, TAs, and students—must be respectful of everyone else in this class. All communication, in class and online, will be held to a high standard for inclusiveness: it may never target individuals or groups for harassment, and it may not exclude specific groups. That includes everything from outright animosity to the subtle ways we phrase things and even our timing. For example: do not talk over other people; don’t use male pronouns when you mean to refer to people of all genders; avoid explicit language that has a chance of seeming inappropriate to other people; and don’t let strong emotions get in the way of calm, scientific communication. If any of the communication in this class doesn’t meet these standards, please don’t escalate it by responding in kind. Instead, contact the instructor as early as possible. If you don’t feel comfortable discussing something directly with the instructor—for example, if the instructor is the problem—please contact the advising office or the department chair.

## Section Collaboration Policy

Student collaboration is highly encouraged, in fact section worksheets are made to be collaborative. During each section, you will be assigned to a group of 3-4 students with whom you can collaborate as much as you would like, even outside of section time. However, you must turn in your own handwritten solution at the beginning of the following week. If your solution is a verbatim copy of another student’s solution, you will not get completion credit for that week.

Barring the course wiki, internet collaboration is strictly forbidden. In fact, because section worksheets are not graded for correctness, you are only hurting yourself by using online resources.

# Collaboration Policy

You may not obtain or view any part of anyone else's solution. To do so is a violation of the academic integrity code. This includes solutions downloaded from the Internet.

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. You may ask questions during office hours, or discuss the problems with other groups. You may consult reference material that discusses the general concepts, but not published solutions to the assignments or similar problems.

You must clearly cite all sources consulted (with the exception of the course wiki and MCS).

During the second phase, you and your partner should put away your notes and write the solutions 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 another group 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.

When working in a group, both group members are expected to contribute to the solution and to fully understand it.

It is also against the academic integrity policy of the course to transfer any course materials to any third party. This includes problem sets, handouts, lecture notes, etc. All course materials are copyrighted by Michael George.

Violations of the academic integrity policy will be punished. Punishments for first offences may be as severe as failure of the course. Repeat offences can lead to more serious punishments, including expulsion. Cheating is never worth it. If you feel that you cannot complete your work without violating the academic integrity policy, speak to Professor George or another member of the course staff.

# 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.

All accommodation forms should be submitted to both Professor George and to Corey Torres (ct635, Gates 401).