SP19:Lecture 1 Introduction

From CS2800 wiki

Course overview

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.


Throughout the course we will focus on

clear descriptions of terms. For the most part, all of the words we use will have crisp definitions
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.


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 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 is the art of counting things without listing them. It is useful for the analysis of algorithms.
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.
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.

Course logistics


  • Lecture
    • No devices with screens
    • No side conversation
    • Please ask questions
  • Website
    • Contains lecture notes, syllabus, etc.
    • We're using a new system, please report problems on Piazza
  • Piazza
    • Used for class discussion
    • This is how you contact us
    • Homeworks will be posted here
    • Announcements and logistics will be posted here
    • You should enroll yourself
  • Gradescope
    • This is where you will submit homework and get grades and feedback
    • You should enroll yourself; the course code is on the Main Page. Use your NetID as your student ID.
    • You are required to submit pdf files; you may create them however you like, as long as they are legible. We encourage you to learn LaTeX; we will post templates for the homework for you to use if you wish.


Your course grade will be based on:

  • two evening prelims (roughly 1/6 each),
  • a final exam (roughly 1/3),
  • weekly homework assignments (roughly 1/3)
    • We will drop your lowest homework score when computing your final grades.
  • "good citizenship" can help or hurt if you are right at a grade cutoff; this includes a small number of things like filling in the course evaluation. We will explicitly announce what is required for good citizenship.

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.

Unless specified otherwise, assignments will be due Mondays at 5:00 PM. They should be submitted on Gradescope. We will accept late assignments until Tuesday at 5:00 PM. You may submit two late assignments 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.

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.