CS240: ace the component, not just read the notes
Your complete guide to University of Wisconsin-Madison's introduction to discrete mathematics course. See where the marks are, work real practice questions, and study with an AI tutor that knows CS240.
Sia generates CS240 practice questions, walks through propositional and sets step by step, and quizzes you on the material the component that weights most heavily.
Worked example
An algorithm on an input of size n splits it into two halves, solves each recursively, and does O(n) work to combine. Which recurrence describes its running time, and what does it solve to?
Read the structure off the description: two recursive calls, each on half the input, plus linear combining work.
Unfold it: each level does O(n) total combining work, and there are log n levels because the input halves each time.
Multiply: O(n) per level times log n levels gives O(n log n). This is exactly the merge sort recurrence.
The trap: Writing one recursive call instead of two, which describes binary search rather than a divide-and-conquer algorithm that solves both halves. Constructing the recurrence correctly is the step that decides the answer; solving it afterwards is mechanical, which is why the outcome names constructing recurrences before solving them. classic slip!
Overview
What CS240 is, and where it sits
COMP SCI/MATH 240 is the discrete mathematics course shared by the computer sciences and mathematics departments, and it is the bridge between programming and theory. It carries 3 credits at intermediate level and takes calculus as its prerequisite.
The content spans logic, sets, partial order and other relations, and functions, then the basic machinery of mathematics itself, definitions, proofs, sets, functions and relations, applied to discrete structures: integers, bits, strings, trees and graphs. Propositional logic, Boolean algebra and predicate logic follow, then mathematical induction and recursion, invariants and algorithmic correctness, recurrences and asymptotic growth analysis, and the fundamentals of counting.
The published outcomes state the real demand plainly. The first is demonstrating proficiency with the basic skills for constructing and evaluating mathematically rigorous arguments and proofs. Others include proving properties by induction across several domains including loop invariants and program correctness, constructing and solving recurrences, applying asymptotic analysis, and connecting a simple language to a finite state machine or regular expression in both directions. This is the course that makes later algorithms and theory courses possible.
Always treat your own course outline and the exam timetable as authoritative.
Difficulty & time commitment
Is CS240 hard, and how much time does it take?
CS240 is manageable if you keep a weekly rhythm and treat the back half as the main event. The pattern is consistent: it starts gently and steepens, and the heaviest assessment is the part that separates grades.
The difficulty curve and the assessment weighting point the same way: the back half is harder and worth more. Front-loading effort there is the highest-return decision in the course.
Is this course for you
Who tends to do well, and who tends to struggle
You will likely do well if
- You are willing to write proofs badly for a few weeks before writing them well.
- You do problem sets rather than reading solutions.
- You can hold a formal definition precisely rather than approximately.
- You connect the abstraction back to code, which the invariant material rewards.
You may struggle if
- You came from the programming sequence expecting more of the same.
- You skip the logic weeks as preliminaries; every later definition uses them.
- You memorise proof templates without understanding what makes them valid.
- You leave induction until you need it for recurrences.
- Write one full proof per week by hand and have someone else read it for gaps.
- For each theorem, construct a counterexample to a weakened version; it shows which hypothesis matters.
- Practise turning an algorithm into a recurrence, which is the step that carries the marks.
- Do the finite state machine translations in both directions until they are symmetric in your head.
Syllabus
The 9 topics, topic by topic
The exam-weight marker on each topic shows where the marks concentrate. The amber topics carry the highest exam weight.
T1 · Propositional and predicate logic
Course descriptionThe formal language everything else is written in, plus Boolean algebra.
T2 · Sets, relations and functions
Course descriptionIncluding partial orders. The vocabulary of every definition later in the course.
T3 · Proof technique
Learning outcome 1Constructing and evaluating rigorous arguments. The first outcome, and the skill the course exists to install.
T4 · Mathematical induction
Learning outcome 2Proving properties of formulas, recursively defined structures, loop invariants and program correctness.
T5 · Discrete structures: integers, bits, strings, trees, graphs
Learning outcome 3The objects computing actually manipulates, treated formally.
T6 · Recurrences and asymptotic growth
Learning outcome 4Constructing a recurrence from an algorithm, solving simple ones, and reading the growth rate off the result.
T7 · Algorithmic correctness and termination
Learning outcome 4Proving that an algorithm does what it claims and stops, using invariants.
T8 · Counting
Learning outcome 5Basic combinatoric techniques applied to counting problems.
T9 · Finite state machines and regular expressions
Learning outcome 6Translating between a simple language, a machine that recognises it, and a regular expression, in both directions.
How it's assessed
Assessment structure
A component-by-component weighting breakdown is not published for this course. Rather than estimate one, we publish only what the course itself states. Check your current course outline for the exact percentages.
No component weighting is published. The university catalogue publishes course description, credits, requisites, course designation and learning outcomes, but not assessment weights, and instructor syllabi carrying them are set per section and per term. Rather than estimate a breakdown or reuse a superseded one, none is asserted here. Check the syllabus your instructor posts for this term. Not published in the catalogue. Format is set per section by the instructor.
How to actually pass it
A weekly rhythm, two checklists, and the traps to avoid
The course rewards consistency over cramming, and practice over re-reading. Here is the loop that works, then what to have nailed before each exam.
The weekly loop
Before the mid-semester checklist
- Propositional and predicate logic, and Boolean algebra
- Sets, relations including partial orders, and functions
- Basic proof techniques, written out in full
- Induction over formulas and over recursive structures
Before the final heaviest topics
- Invariants and algorithmic correctness
- Constructing and solving recurrences
- Asymptotic growth analysis
- Counting techniques
- Finite state machines and regular expressions, translated both ways
The mistakes that cost marks
Constructing the wrong recurrence. The number of recursive calls and the size of each subproblem decide the answer. Getting them right is the whole task.
Induction without a proper base case. A proof that skips or fudges the base case proves nothing, and it is the most common lost mark in the course.
Treating definitions as approximations. In discrete mathematics the definition is the object. Paraphrasing it changes what you have proved.
Reading proofs instead of writing them. Recognising a valid argument and producing one are different skills, and only the second is examined.
Formula & concept sheet
The vocabulary and formulas you must own
- Propositional logic
- Reasoning about statements combined with connectives such as and, or and not.
- Predicate logic
- Logic with quantifiers, allowing statements about all or some members of a domain.
- Partial order
- A relation that is reflexive, antisymmetric and transitive; not every pair need be comparable.
- Mathematical induction
- Proving a property for all n by establishing a base case and an inductive step.
- Loop invariant
- A condition true before and after each iteration, used to prove a loop correct.
- Recurrence
- An equation expressing a quantity in terms of its value on smaller inputs.
- Asymptotic growth
- How a quantity grows as input size increases, ignoring constants.
- Combinatorics
- The mathematics of counting arrangements and selections.
- Finite state machine
- An abstract machine recognising a language, equivalent in power to a regular expression.
Common acronyms: {'term': 'QR-B', 'def': 'Quantitative Reasoning Part B designation'} · {'term': 'ADT', 'def': 'Abstract data type'} · {'term': 'L&S', 'def': 'College of Letters & Science'}.
Where it fits
Prerequisites, related courses & why it matters
Requires MATH 217 or MATH 221.
Your CS240 study toolkit
Study the course with Sia, not just read about it
Each tool already knows CS240: your syllabus, your texts, and where the marks are. Grouped by how you study, from first contact to exam week.
FAQ
Frequently asked questions
What is the prerequisite?
MATH 217 or MATH 221, that is, calculus.
Is this a mathematics course or a computer science course?
Both. It is cross-listed as COMP SCI 240 and MATH 240, and it applies mathematical technique to the structures computing uses: integers, bits, strings, trees and graphs.
How much proof is involved?
A great deal. The first published outcome is demonstrating proficiency with the basic skills for constructing and evaluating mathematically rigorous arguments and proofs.
Why do computing students need it?
It is a requisite for later theory courses, and the induction, invariant and recurrence techniques are what algorithm analysis is built on.
How is it graded?
No weighting is published in the catalogue; assessment is set per section.
Is it still running?
Yes. The catalogue records it as last taught in Summer 2026.
Study CS240 with Sia
Work through propositional, sets, proof technique and the rest of the course with a tutor that knows it and quizzes you on the topics the assessments weight most heavily.
Start studying with Sia
