Discrete Mathematics¶
A course wiki for SF1610 Diskret matematik (KTH), organised around the seven topics the exam draws from.
Where to start¶
If you are revising for the exam, the fastest route is the topic pages — each one states the definitions and theorems you are expected to quote, gives the standard algorithm or recipe, and works an example taken from a real exam.
If you want to know what the exam actually looks like — the three-part structure, the grade boundaries, and why presentation is worth marks — read Exams first.
The seven topics¶
| Topic | Typical exam problems |
|---|---|
| Logic, sets & relations | Countability proofs, equivalence classes, truth tables, DNF/CNF |
| Number theory & cryptography | Diophantine equations, modular inverses, RSA key generation |
| Combinatorics & probability | Counting with complements, stars and bars, Stirling numbers |
| Graph theory | Euler/Hamilton, planarity and Euler's formula, isomorphism |
| Group theory | Lagrange's theorem, cycle notation, subgroups of \(S_n\) |
| Induction | Divisibility, summation formulas, inequalities |
| Coding theory | Linearity, minimum distance, error detection and correction |
A note on how this course is graded¶
Every exam paper repeats the same warning, so it is worth taking seriously:
For full marks on a problem, the solution must be well-presented and easy to follow. This means in particular that all introduced variables are explained, that the logical structure is clearly presented in words or symbols, and that the reasoning is well-motivated and clearly written.
A correct final answer with no visible reasoning is capped at two points out of four. Most of what these pages show you is how the argument is written down, not just what the answer is.
Notation used throughout¶
Math renders with KaTeX, inline as \(\gcd(15, 17) = 1\) and as a block:
| Symbol | Meaning |
|---|---|
| \(\mathbb{Z}_n\) | The integers modulo \(n\) |
| \(\mathbb{Z}_n^{\times}\) | The units (invertible elements) modulo \(n\) |
| \(\mathcal{P}(A)\) | The power set of \(A\) |
| \(\lvert A \rvert\) | Cardinality of \(A\); also the order of a group |
| \(\langle g \rangle\) | The subgroup generated by \(g\) |
| \(S_n\) | The symmetric group on \(\{1, \dots, n\}\) |
| \(\delta(C)\) | The minimum distance of a code \(C\) |