Step 1
Discrete Mathematics
The mathematics behind algorithms and data structures: logic, proofs, sets, graphs and counting. It answers "why is this correct and why is it fast" in the algorithms course.
- Propositional logic
- Proof techniques
- Induction
- Sets and functions
- Relations
- Counting and probability
- Graphs and trees
Why it matters
Calculus deals with continuous things; computers deal with discrete ones: bits, nodes, steps. You prove an algorithm correct with induction, count its steps with combinatorics and find the shortest route in a network with graph theory. Students who coast through this course struggle in algorithms.
What to know
- Propositional and predicate logic; writing conditions with and, or, implies.
- Direct proof, proof by contradiction and above all induction.
- Sets, functions and relations; equivalence and order relations.
- Permutations, combinations, the pigeonhole principle, basic probability.
- Graphs: degree, paths, cycles, connectivity; trees.
- Recurrences: the basis of algorithm analysis.
Practice and projects
- Do not memorize proofs, write them; have a friend read yours and see if they are convinced.
- Try graph topics in code: store a graph as an adjacency list and check whether it is connected.
- Check answers to counting problems with a small brute-force program.
Common mistakes
- Treating it as math to pass and forget; it comes back in algorithms.
- Skipping the base case or the hypothesis in an induction proof.
- Thinking a few examples prove something; three examples are not a proof.