Maths syllabus

Updated

July 30, 2026

Syllabus — Maths for computer science & programming

Status: Canonical outline for Volume 3.
Voice: Concept-first journey notes (definitions → worked examples → exercises).
Shape: ~90 study days · no programming labs · gates beat calendars.

Important

Each day teaches mathematical concepts with worked examples and exercises.
Optional calculator/Python only to check arithmetic — never the lesson itself.

Coverage map (topics this volume owns)

This volume aims at full undergraduate discrete-math literacy for CS/programming (Rosen / MIT MCS spine), without calculus, full linear algebra, automata theory courses, or production crypto.

Area Topics included
Arithmetic foundations ℤ, ℚ; precedence; associativity; absolute value & triangle inequality; fractions; percent; sci notation; primes; FTA; Euclid infinite primes; gcd/lcm; division algorithm; floor/ceiling; residues; binary/hex; two’s complement & overflow; bitwise ops idea; exponents/logs & bits; abs/rel error; FP model & ε_mach idea
Algebra Expressions; linear equations/inequalities; abs-value inequalities; 2×2 systems; det, Cramer, 2×2 matrix form & inverse; polynomials; Horner; factoring; rational expressions; partial fractions setup; functions (piecewise, inverse idea); linear/quadratic; exponential/compound interest; Σ (linearity, geometric, telescoping, double sums)
Logic & proofs Propositional logic; XOR; tautology; Boolean algebra; DNF/CNF lite; NAND completeness awareness; equivalence; predicates; ∀∃; nested quantifiers; ∃!; direct / contrapositive / contradiction / cases / existence; weak & strong induction; structural induction (lists/trees); loop invariants; well-ordering link; fallacies
Discrete structures Sets; power set; Russell awareness; Cartesian products; relations (RST, antisym); matrix/digraph of a relation; closures (esp. transitive); equivalence & partitions; ℤ/nℤ; posets/Hasse; chains; lattices lite; inj/surj/bij; composition/inverse; countability; Cantor diagonal; pigeonhole (basic + generalized); types↔︎sets analogy
Combinatorics Product/sum; complementary counting; permutations (linear, circular, repetition); derangements (!n, IE); combinations; multiset / stars and bars; binomial theorem; Pascal & hockey-stick; Catalan numbers lite; inclusion-exclusion; surjections / Stirling awareness; counting functions/states/passwords; recurrences; characteristic equation; generating functions lite; story / bijective proofs
Graphs Undirected/directed/multi; degree/handshaking; graphic sequences (Havel–Hakimi); paths/cycles/connectivity; trees & equivalent characterizations; spanning trees; Cayley n^{n-2}; Kruskal/Prim cut property idea; BFS/DFS + edge types awareness; DAGs/topo order; Dijkstra + negative-weight caution; bipartite; matchings; Hall’s theorem statement; Euler (full criterion) / Hamilton (Dirac–Ore statements, hardness awareness); planarity/color (4-color statement); CS modeling (deps, CFG, routing, state graphs)
Number theory for CS Divisibility proofs; FTA; Euclid lemma; Euclidean + extended Euclid; Bézout; mod arithmetic; linear congruences; inverses; Wilson statement; Fermat; Euler φ formula; Euler’s theorem; order mod n; hashing + birthday bound; DH/RSA story (no production code); CRT constructive; LCG / Hull–Dobell statement; entropy vs PRNG ideas
Asymptotics & discrete probability Big-O/Ω/Θ/o/ω; growth ladder; Stirling use; loop→Σ→bounds; amortized idea (array doubling); Master theorem (3 cases); recursion trees; Akra–Bazzi awareness; finite probability; conditional/Bayes; independence; union bound; expectation; linearity; indicators; binomial/geometric; variance; coupon collector; Markov & Chebyshev statements

Optional beyond this volume (not required for capstone): full multi-variable linear algebra; formal languages & automata; measure-theoretic probability; production cryptography engineering; competitive-programming grind as primary goal.

Why this order

Principle What we do
Friction first Arithmetic + algebra before proofs
Logic before counting Justification habits early
Discrete over continuous Sets, graphs, mods, O-notation as spine
Examples before drill Worked solutions, then exercises
Prove small, often Short proofs throughout Stage III+
Capstone = dossier Written output you can defend

Stage map

Stage Days Theme Gate means
0 — How to study Definitions → examples → exercises habit
I 1–10 Number sense & arithmetic Fluent ops + bases
II 11–22 Algebra & functions Solve / functions / Σ
III 23–34 Logic & proofs Tables + quantifiers + 3 proof styles
IV 35–46 Sets, relations, functions Discrete structures fluency
V 47–58 Combinatorics Counting with justification
VI 59–70 Graph theory Model + traverse + trees/DAGs
VII 71–80 Number theory for CS Euclid, mods, crypto literacy
VIII 81–90 Asymptotics, discrete probability, capstone Dossier complete

How to study (before Day 1)

See How to study maths for CS.

Habit Practice
Definitions first Write the definition before examples
Worked examples Cover solution; redo cold
Exercises By hand; then check
Error log What you thought vs truth
Gate retests One old gate problem weekly

Stage I — Number sense & arithmetic (Days 1–10)

Day Focus Core skills
1 Integers, order of operations Precedence, associativity, signs
2 Fractions & rationals Ops, reduce, rates, equality \(ad=bc\)
3 Decimals, percent, scientific notation Conversions, scales
4 Factors, primes, gcd/lcm FTA statement, identities
5 Integer division & remainders Division algorithm; language % caveat
6 Binary & hex Conversions, nibbles
7 Binary arithmetic; two’s complement idea Fixed-width overflow
8 Exponents & logs as scales Laws; \(\log_2\) and bits
9 Absolute/relative error Rounding discipline
10 Gate I Mixed review 1–9

Stage II — Algebra & functions (Days 11–22)

Day Focus Core skills
11 Variables & expressions Substitution, structure
12 Linear equations Solve, check, identities/contradictions
13 Inequalities & intervals Flip rule, interval notation
14 2×2 linear systems + matrix form Sub/elim; det; Cramer; \(2\times2\) inverse
15 Polynomials Degree, Horner, division lite
16 Factoring Patterns; factor theorem idea
17 Rational expressions Domain; partial fractions setup
18 Functions Domain/range; piecewise; inverse idea
19 Linear & quadratic functions Slope; vertex; discriminant
20 Exponential intuition Growth; compound interest; logs inverse
21 Summation \(\sum\) Closed forms; telescoping; double sums
22 Gate II Mixed algebra / matrix 2×2 / \(\sum\)

Stage III — Logic & proofs (Days 23–34)

Day Focus Core skills
23 Propositions & truth tables Connectives, tautology
24 Boolean algebra De Morgan, simplify
25 Logical equivalence Law chains / tables
26 Predicates & quantifiers Translate, negate
27 Nested quantifiers Order, witnesses
28 Direct proof Parity, divisibility
29 Contrapositive & contradiction Method choice
30 Cases & existence Exhaustion, construction
31 Weak induction Base + step; state \(P(n)\); well-ordering
32 Strong induction, structural induction, loop invariants Fib, stamps, lists/trees, algorithms
33 Fallacies Debug arguments
34 Gate III Tables + quantifiers + 3 proofs

Stage IV — Sets, relations, functions (Days 35–46)

Day Focus Core skills
35 Sets & builder notation \(\in\), roster, empty set
36 \(\cup\cap\setminus\) complement, power set Identities, \(2^{\|S\|}\)
37 Cartesian products Tuples, counts
38 Relations RST + closures Matrix/digraph; transitive closure
39 Equivalence & partitions Classes; \(\equiv\pmod n\) link
40 Partial orders, Hasse, lattices lite Dependency; topo link
41 Injective/surjective/bijective Finite cardinal compare
42 Composition & inverse Pipelines; left/right inverses
43 Countability \(\mathbb{Q}\) countable; Cantor diagonal
44 Types/sets programming analogy Specs vocabulary
45 Pigeonhole (basic + generalized) Collisions; modular pigeon
46 Gate IV Structures mixed set

Stage V — Combinatorics (Days 47–58)

Day Focus Core skills
47 Product & sum rules Justification trees
48 Permutations + derangements \(P(n,k)\), circular, \(!n\)
49 Combinations \(\binom{n}{k}\); grid paths
50 Binomial + Catalan lite Pascal; Dyck/parens/BST stories
51 Stars and bars Nonneg/positive; multisets
52 Inclusion-exclusion 2–3 sets; surjections; \(!n\)
53 Counting functions/states/passwords CS scenarios; \(\log_2\) size
54 Recurrence relations intro Fib, Hanoi, divide-conquer setup
55 Solving recurrences + GF lite Char. eq.; ordinary GF sketch
56 Combinatorial (story) proofs Double counting; hockey-stick
57 Mixed counting workshop Method selection
58 Gate V Counting portfolio

Stage VI — Graph theory (Days 59–70)

Day Focus Core skills
59 Graphs & degree Handshaking lemma
60 Paths, cycles, connectivity Components
61 Trees, spanning trees, Cayley, MST idea Characterizations; cut property
62 BFS & DFS Levels; edge types awareness
63 DAGs & topological order Scheduling; critical path idea
64 Weighted graphs; Dijkstra Invariant; negative-weight caution
65 Bipartite; matchings; Hall Structure + small Hall example
66 Euler / Hamilton Euler criterion; Dirac/Ore; hardness
67 Planarity / coloring \(\chi\); 4-color; register story
68 Graphs in CS Deps, CFG, networks, state graphs
69 Modeling workshop Word problems → graphs
70 Gate VI Model + analyze

Stage VII — Number theory for CS (Days 71–80)

Day Focus Core skills
71 Divisibility, primes, FTA statement Proofs lite
72 Euclidean (+ extended); complexity Bézout; \(O(\log n)\)
73 Modular arithmetic Congruences; linear solve
74 Inverses mod \(n\); Wilson stmt Exist iff coprime
75 Fermat / Euler / φ formula Reduce exponents; order
76 Hashing maths Collisions; birthday bound
77 DH & RSA story Parameters; no production code
78 CRT constructive Coprime moduli; applications
79 Randomness vs structure LCG; Hull–Dobell stmt
80 Gate VII Mods + Euclid + literacy Q

Stage VIII — Asymptotics, discrete probability, capstone (Days 81–90)

Day Focus Core skills
81 Big-O, \(\Omega\), \(\Theta\), \(o\), \(\omega\) Formal bounds + proofs
82 Growth classes Ladder; Stirling use
83 Loops → \(\sum\) → bounds; amortized idea Read-only fragments
84 Master theorem (3 cases) Recursion trees; Akra–Bazzi note
85 Discrete probability Axioms; union bound
86 Conditional probability; Bayes Base rates; total probability
87 Expectation; variance; coupon collector Indicators; Markov/Chebyshev stmt
88 Capstone outline Select dossier items
89 Capstone draft Write full solutions
90 Capstone final Polish + retrospective

Capstone dossier (required)

  1. Key definitions (logic, sets, graphs, \(O\)-notation)
  2. Three proofs (direct; contrapositive or contradiction; induction)
  3. Two counting solutions with full justification
  4. One graph model of a CS-ish situation
  5. One modular computation (+ inverse if exists)
  6. One complexity argument for a small code fragment
  7. Retrospective + 30-day continued plan

Explicitly out of scope (spine)

  • Full \(\varepsilon\)-\(\delta\) calculus / real analysis
  • Abstract algebra as a course (groups/rings/fields beyond \(\mathbb{Z}/n\mathbb{Z}\) and modular units)
  • Measure-theoretic / continuous probability
  • Production cryptography implementation (this volume is math literacy only — RSA/DH story, not engineering)
  • Full multi-variable linear algebra / eigenstuff (we do own \(2\times2\) systems, det, inverse)
  • Formal languages & automata as a course
  • Competitive programming grind as primary goal
  • Programming labs or coding projects as the lesson format

Depth targets (writing)

Kind Target
Concept day ~300–450 lines: definitions, proofs, 8–15 worked examples, 15–25 exercises
Gate day ~280–400 lines: mixed portfolio, multi-section
Capstone days Structured dossier scaffolds; Day 90 verification + retrospective

Companion resources

  • Mathematics for Computer Science (Lehman, Leighton, Meyer)
  • Rosen, Discrete Mathematics and Its Applications
  • Concrete Mathematics (Graham, Knuth, Patashnik) — later depth

Writing rule for chapters

  1. Definition → worked examples → exercises → checkpoint.
  2. No labs / no coding projects as core content. Theory, proofs, worked arithmetic/reasoning, and written exercises only.
  3. Prefer short proofs and concrete numbers.
  4. Stage gates are mixed exercise dossiers for retesting.
  5. Optional calculator/Python only to check arithmetic after solving by hand — never the lesson itself.
  6. Target depth: concept days typically ~300–450 lines of prose + math; gates/capstones may be structured exercise dossiers of similar length.