Discrete Mathematics: Practice Problems

Discrete Mathematics — Practice Problems

12 practice problems covering propositional logic, set theory, functions, graph theory, and algorithm analysis. These problems test understanding of fundamental concepts in discrete mathematics.

Intuition

The logic beneath all computation: Discrete mathematics is the logic beneath all computation, it’s how we reason about algorithms, prove programs correct, and understand the structure of data. Without it, you’re building on sand.

Why it matters: Every area of computer science uses discrete math, algorithms use graph theory, databases use relations, compilers use formal logic, and cryptography uses number theory. It’s the common language that connects all CS subfields.

The key insight: Proof by induction is the workhorse of computer science correctness proofs, if you can prove the base case and the inductive step, you’ve proved something for all inputs, no matter how large.

Logic and Proofs

Sets and Functions

Graph Theory and Algorithms

Complexity and Recurrences

Common Mistakes

Confusing injective with surjective functions: Injective (one-to-one) means each element in the codomain is mapped to by at most one element in the domain. Surjective (onto) means each element in the codomain is mapped to by at least one element. Don’t mix up the two.

Forgetting that graph connectivity requires a path between ALL pairs: A connected graph has a path between every pair of vertices. A graph with just one edge connecting two vertices is connected only if those are the only vertices.

Mixing up planar with planar-embedded: A planar graph can be drawn without edge crossings. A planar embedding is a specific drawing without crossings. Don’t assume all drawings of a planar graph are planar embeddings.

Forgetting vacuous truth in logic: “All unicorns are purple” is vacuously true if no unicorns exist. In predicate logic, ∀x P(x) is true if the domain is empty, regardless of P. This surprises many students.

Confusing implication with equivalence: P → Q is true whenever P is false or Q is true. P ↔ Q requires both P → Q and Q → P. Don’t assume P → Q implies Q → P (the converse).

Related Topics

See Also

• Computing
• Computing
• Discrete Mathematics

Detailed Content

Core Concepts

Worked Examples

Common Mistakes

• Rushing through foundational material
• Not practising problems after reading
• Failing to connect concepts across topics

Further Reading