Discrete structures: counting, graphs and algorithms

Lesson sequence

Each linked lesson opens on its own page. Expand its details here when you want to check the objectives before choosing.

1. Compare sizes by pairing objects

   Lesson details and objectives

   Use bijections for finite counting and distinguish countable from uncountable sets.

   • Use bijections for finite counting and distinguish countable from uncountable sets.
   • State assumptions and justify the general counting or structural argument.

   6 practice tasks.

2. Count outcomes without overlaps or omissions

   Lesson details and objectives

   Separate disjoint alternatives from sequential choices and use complements.

   • Separate disjoint alternatives from sequential choices and use complements.
   • State assumptions and justify the general counting or structural argument.

   6 practice tasks.

3. Decide what makes outcomes different

   Lesson details and objectives

   Derive ordered and unordered selection counts and account for repeated symbols.

   • Derive ordered and unordered selection counts and account for repeated symbols.
   • State assumptions and justify the general counting or structural argument.

   6 practice tasks.

4. Read coefficients as choices

   Lesson details and objectives

   Derive the binomial expansion and connect algebraic and combinatorial identities.

   • Derive the binomial expansion and connect algebraic and combinatorial identities.
   • State assumptions and justify the general counting or structural argument.

   6 practice tasks.

5. Correct multiple counting systematically

   Lesson details and objectives

   Count unions of overlapping sets and explain alternating corrections.

   • Count unions of overlapping sets and explain alternating corrections.
   • State assumptions and justify the general counting or structural argument.

   8 practice tasks.

6. Force a collision without finding it

   Lesson details and objectives

   Choose the right boxes and prove sharp bounds.

   • Choose the right boxes and prove sharp bounds.
   • State assumptions and justify the general counting or structural argument.

   8 practice tasks.

7. Turn a recursive definition into a proved formula

   Lesson details and objectives

   Solve first-order recurrences and use initial conditions in second-order models.

   • Solve first-order recurrences and use initial conditions in second-order models.
   • Distinguish observed examples from a general structural proof.

   6 practice tasks.

8. Package a sequence as coefficients

   Lesson details and objectives

   Use formal power series to encode counting and recurrences.

   • Use formal power series to encode counting and recurrences.
   • Distinguish observed examples from a general structural proof.

   6 practice tasks.

9. Count incidences instead of guessing edges

   Lesson details and objectives

   Define simple graphs and prove degree identities and parity constraints.

   • Define simple graphs and prove degree identities and parity constraints.
   • Distinguish observed examples from a general structural proof.

   6 practice tasks.

10. Recognize minimal connected structure

    Lesson details and objectives

    Distinguish walks and paths and prove the characteristic properties of trees.

    • Distinguish walks and paths and prove the characteristic properties of trees.
    • Distinguish observed examples from a general structural proof.

    10 practice tasks.

11. Separate using every edge from visiting every vertex

    Lesson details and objectives

    Apply Euler parity conditions and recognize the limits of Hamiltonian heuristics.

    • Apply Euler parity conditions and recognize the limits of Hamiltonian heuristics.
    • Distinguish observed examples from a general structural proof.

    6 practice tasks.

12. Use colors to detect structural obstructions

    Lesson details and objectives

    Prove the odd-cycle characterization and separate coloring from drawing aesthetics.

    • Prove the odd-cycle characterization and separate coloring from drawing aesthetics.
    • Distinguish observed examples from a general structural proof.

    6 practice tasks.

13. Order dependencies without inventing an order for cycles

    Lesson details and objectives

    Construct topological orders and prove why the algorithm detects cycles.

    • Construct topological orders and prove why the algorithm detects cycles.
    • Prove the method's invariant or hypotheses and test boundary cases.

    6 practice tasks.

14. Prove what a loop preserves and why it stops

    Lesson details and objectives

    Combine initialization, maintenance, exit reasoning and a decreasing measure.

    • Combine initialization, maintenance, exit reasoning and a decreasing measure.
    • Prove the method's invariant or hypotheses and test boundary cases.

    6 practice tasks.

15. Separate a growth bound from a timing claim

    Lesson details and objectives

    Use quantified O, Ω and Θ definitions and count operations.

    • Use quantified O, Ω and Θ definitions and count operations.
    • Prove the method's invariant or hypotheses and test boundary cases.

    6 practice tasks.

16. Compute a gcd while preserving its meaning

    Lesson details and objectives

    Use remainder reduction and back-substitution to construct integer certificates.

    • Use remainder reduction and back-substitution to construct integer certificates.
    • Prove the method's invariant or hypotheses and test boundary cases.

    6 practice tasks.

17. Calculate with residue classes without invalid cancellation

    Lesson details and objectives

    Prove modular operations and characterize multiplicative inverses.

    • Prove modular operations and characterize multiplicative inverses.
    • Prove the method's invariant or hypotheses and test boundary cases.

    6 practice tasks.

18. Combine congruences and certify integer solutions

    Lesson details and objectives

    Use coprimality for unique residues and gcd conditions for linear equations.

    • Use coprimality for unique residues and gcd conditions for linear equations.
    • Prove the method's invariant or hypotheses and test boundary cases.

    6 practice tasks.