Cornell CS 2800: Discrete Structures
CS 2800 is Cornell's discrete mathematics course for CS majors, covering logic and proof, induction, sets, functions and relations, combinatorics, graph theory, basic probability, and finite-state machines. It's the bridge from coding to the mathematical reasoning the upper-level theory courses assume.
Fennie is independent and not affiliated with Cornell University. This is an unofficial study guide.
What makes it hard
For students whose strength is programming, the shift to writing rigorous proofs is the wall: a proof is either valid or it isn't, and 'I see why it's true' earns nothing without a correct argument. Induction and the probability unit are the common stumbles, and prelims reward precise reasoning over computation, which inverts how most students studied for their coding courses.
What you'll cover
- • Logic and proof techniques
- • Mathematical induction
- • Sets, functions, and relations
- • Combinatorics and counting
- • Graph theory
- • Basic probability theory
- • Finite-state machines
The CS 2800 study guide
How to study for Cornell CS 2800, step by step.
- 1
Treat proof-writing as a skill to drill
CS 2800's core shift is from code that runs to arguments that are valid. Write full proofs, not sketches, from week one, and get them critiqued, because the prelims grade rigor, not intuition.
- 2
Master induction early and deliberately
Induction underlies later units and is a reliable prelim stumble. Practice the structure relentlessly (base case, hypothesis, inductive step) until setting one up from scratch is automatic.
- 3
Build a proof-technique toolbox
Direct, contrapositive, contradiction, induction, counterexample: know which the problem shape wants before you start writing. Choosing the wrong technique is a common reason proofs stall.
- 4
Give the probability unit extra runway
Discrete probability is a conceptual leap for many CS students. Start it early and work many counting and probability problems, since it rewards practice volume more than rereading.
- 5
Practice proofs cold under time
Before each prelim, write proofs from blank paper without notes. Rereading worked solutions teaches recognition, not production, and the exam tests production.
Today
Today's CS 2800 plan
What a Fennie Daily Plan looks like for CS 2800. Yours is built from your own syllabus and adapts every day to your deadlines and progress.
First plan free, no card required. Fennie is independent and unaffiliated with your school.
FAQ
Is CS 2800 at Cornell hard?
It's hard for the specific reason that it's a proof course, not a coding course. Strong programmers often struggle because rigor is graded, not intuition: induction and discrete probability are the usual walls. Drilling proofs from scratch is what closes the gap.
How do I study for CS 2800 prelims?
Write full proofs cold, without notes, before each prelim; production, not recognition, is what's tested. Build a toolbox of proof techniques so you can pick the right one fast, and give discrete probability extra practice since it's a common stumble.
Do I need CS 2800 for the CS major?
Yes. It's a required core course and a prerequisite for the upper-level theory and algorithms courses, which assume its proof and discrete-math foundations fluently. Aim for mastery rather than a bare pass, since CS 3110 and CS 4820 build directly on it.
More Cornell courses
CS 1110: Introduction to Computing: A Design and Development Perspective
CS 1110 is Cornell's Python-based first programming course, covering variables and types, functions, conditionals and loops, objects and classes, recursion, and testing. It's taken by intended CS majors and a large non-major population alike, and it leads into CS 2110 for those continuing in the major.
CS 2110: Object-Oriented Programming and Data Structures
CS 2110 is Cornell's second programming course, taught in Java and cross-listed as ENGRD 2110. It covers object-oriented design, data structures (lists, trees, hash tables, graphs), recursion, and an introduction to algorithmic analysis. It's the gateway most CS and engineering students name as the major's first real workload jump.
CS 3110: Data Structures and Functional Programming
CS 3110 is Cornell's famous functional-programming and data-structures course, taught in OCaml. It covers immutability, recursion, higher-order functions, modules and functors, formal specification and verification, and reasoning about correctness and complexity. It's a required CS core course and a notorious pace step-up after CS 2110.
CS 4820: Introduction to Analysis of Algorithms
CS 4820 is Cornell's upper-level algorithms course, covering greedy algorithms, divide and conquer, dynamic programming, network flow, and NP-completeness and reductions, with a heavy emphasis on proving correctness and analyzing complexity. It's a required CS core course and a capstone of the theory sequence.