Self-Assessment Quiz: Where Discrete Math Goes Next

Twenty questions to check that the map stuck — that you can recognize each direction and recall its one big idea. This is a survey chapter, so the bar is recognition, not derivation. Answer before opening the key. Aim for 16+.

Question 1

Combinatorial optimization is best described as:

A) optimizing a smooth function over the real numbers using derivatives B) finding the optimal object from a finite-but-enormous feasible set defined by combinatorial constraints C) any problem that can be solved in polynomial time D) the study of continuous probability distributions

Question 2

A foundational fact about a linear program with a finite optimum is that the optimum:

A) lies in the interior of the feasible region B) occurs at a corner (vertex) of the feasible polytope C) is always an integer D) can never be found efficiently

Question 3

Which theorem proved earlier in this book is an instance of LP strong duality?

A) the pigeonhole principle B) the max-flow min-cut theorem C) Euler's theorem on planar graphs D) the fundamental theorem of arithmetic

Question 4 (True/False, justify)

True or false: Weak duality alone lets you prove a particular solution is optimal, provided you also exhibit a feasible point of the other program with the same objective value. Justify in one sentence.

Question 5

The Shannon entropy of a discrete source $X$ with outcome probabilities $p_i$ is:

A) $\sum_i p_i$ B) $\sum_i p_i \log_2 p_i$ C) $-\sum_i p_i \log_2 p_i$ D) $-\sum_i \log_2 p_i$

Question 6

A source has $n$ equally likely outcomes. Its entropy is:

A) $1$ bit B) $n$ bits C) $\log_2 n$ bits D) $0$ bits

Question 7

A fair coin and a loaded (90/10) coin are compared. Which has higher entropy, and why?

A) the loaded coin, because 0.9 is close to 1 B) the fair coin, because its outcome is maximally uncertain (more surprise per flip) C) they are equal, because both have two outcomes D) the loaded coin, because it carries more information about the bias

Question 8

Shannon's source-coding theorem says that for the source $\{1/2, 1/4, 1/8, 1/8\}$ (entropy $1.75$ bits/symbol), the average bits per symbol of any code:

A) can be made arbitrarily small with enough cleverness B) cannot go below $1.75$ on average C) must be exactly $2$ (a fixed-length code) D) depends only on the number of symbols, not their probabilities

Question 9

For a binary symmetric channel that flips each bit with probability $p$, the capacity is $C = 1 - H(p)$. At $p = 1/2$ the capacity is:

A) $1$ bit per use B) $0.5$ bits per use C) $0$ bits per use D) undefined

Question 10 (True/False, justify)

True or false: With a clever enough error-correcting code, you can transmit reliably at a rate above a channel's capacity $C$. Justify in one sentence.

Question 11

The Ramsey number $R(s, t)$ is defined as the smallest $n$ such that every red/blue coloring of the edges of $K_n$ contains:

A) a red $K_s$ and a blue $K_t$ B) a red $K_s$ or a blue $K_t$ C) a monochromatic spanning tree D) exactly $s + t$ monochromatic triangles

Question 12

In the proof that $R(3,3) \le 6$, the pigeonhole principle is applied to:

A) the six vertices, placed into two color classes B) the five edges incident to a chosen vertex, in two colors, forcing three of one color C) the three edges of the candidate triangle D) the $\binom{6}{2} = 15$ edges of the whole graph

Question 13

The probabilistic method proves a desired coloring exists by showing the expected number $X$ of bad substructures satisfies $E[X] < 1$. The conclusion "$X = 0$ for some coloring" requires $X$ to be:

A) a real number B) a probability C) a nonnegative integer D) at least 1

Question 14

A defining feature of the probabilistic method is that it is:

A) constructive — it always hands you the object explicitly B) non-constructive — it proves existence without exhibiting the object C) only applicable to graphs D) a special case of the simplex algorithm

Question 15

A category consists of objects, arrows (morphisms), a composition rule, and identity arrows, subject to two laws. Those two laws are:

A) commutativity and distributivity B) associativity of composition and an identity arrow on each object C) closure and invertibility D) reflexivity and transitivity

Question 16

A functor $F$ between categories preserves identities and composition. The composition law is:

A) $F(g \circ f) = F(f) \circ F(g)$ B) $F(g \circ f) = F(g) \circ F(f)$ C) $F(g \circ f) = F(g) + F(f)$ D) $F(g \circ f) = g \circ f$

Question 17

Python's map over lists is an everyday example of a functor. The optimization map(g, map(f, xs)) == map(lambda x: g(f(x)), xs), called map fusion, is sound because:

A) it happens to work on the test cases B) it is the functor composition law, which holds for every functor C) Python guarantees it for all functions D) lists are finite

Question 18 (Short answer)

RSA's security rests on one hardness assumption that a large quantum computer would undermine. Name the assumption and the quantum algorithm that breaks it.

Question 19 (Short answer)

Chapter 37 told you NP-hard problems likely have no efficient exact algorithm. Name two practical responses to that fact, each tied to a tool surveyed in this chapter.

Question 20 (Short answer)

In one sentence, state the chapter's core advice for the reader's path forward — the "common pitfall" about how many of the four directions to pursue.

Answer Key

Topics to review by question