Discrete Math Quiz: Notation And Definitions

What this quiz covers

This quiz focuses on Notation And Definitions, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

Question 1

1. Finding the maximum value requires checking infinitely many points within the circular constraint region
2. The optimization must evaluate integer points only, requiring enumeration of feasible lattice points within bounds (correct answer)
3. The constraint set is non-convex, making standard linear programming techniques completely inapplicable to this problem
4. The objective function is unbounded above over the constraint set, making optimization impossible without modification

Question 2

1. The system must always produce output immediately whenever it receives input, with no delay permitted between events
2. Whenever the system receives input, it must eventually produce output, though the timing of output is not constrained (correct answer)
3. The system must continuously produce output as long as it is receiving input, maintaining synchronized input-output behavior
4. The system must produce output infinitely often, and each output must be preceded by some input within finite time

Question 3

1. Language $L_2$ must be in $\mathbf{NP}$ and every language in $\mathbf{NP}$ must reduce to $L_2$ in polynomial time
2. Language $L_2$ must be computationally equivalent to $L_1$ under polynomial-time reductions in both directions
3. Language $L_2$ must be at least as hard as any language in $\mathbf{NP}$, though $L_2$ itself need not be in $\mathbf{NP}$ (correct answer)
4. Language $L_2$ must be decidable in polynomial time if and only if $\mathbf{P} = \mathbf{NP}$ holds true

Question 4

1. $a_n = a_{n-1} + a_{n-2}$ for $n \geq 2$, with appropriate initial conditions determined by the generating function (correct answer)
2. $a_n = a_{n-1} + a_{n-2} + 1$ for $n \geq 2$, with the constant term arising from the numerator
3. $a_n = na_{n-1} + n(n-1)a_{n-2}$ for $n \geq 2$, incorporating the derivative structure of the generating function
4. $a_n = 2a_{n-1} - a_{n-2}$ for $n \geq 2$, derived from the linear factors in the denominator polynomial

Question 5

1. Project $R$ onto columns $A$ and $C$, then perform natural join with $S$ on matching attribute names
2. Project $R$ onto columns $A$ and $C$, then perform theta join with $S$ where $A$ equals $X$ (correct answer)
3. Select rows from $R$ where $A$ and $C$ meet criteria, then join with $S$ using equality condition
4. Project $R$ onto columns $A$ and $C$, then perform cartesian product with $S$ filtered by condition $A=X$

Question 6

1. A deterministic execution path where each action uniquely determines the next configuration state from the current one
2. A specification requiring that all three actions must be enabled simultaneously in the initial configuration for execution
3. A parallel execution model where actions $\alpha_1, \alpha_2, \alpha_3$ can occur simultaneously across different system components
4. A sequence of valid state transitions showing one possible execution trace through the system's state space (correct answer)

Question 7

1. The construction is correct and proves the statement is true for all positive integers
2. The construction works for this statement, but the student should verify edge cases more carefully
3. The construction is valid but insufficient since it only provides one example rather than universal proof
4. The construction demonstrates the existential quantifier correctly and constitutes a complete proof of the statement (correct answer)

Question 8

1. Function $\hat{\delta}$ processes entire strings by composing individual symbol transitions, while $\delta$ handles only single symbol transitions (correct answer)
2. Function $\hat{\delta}$ determines acceptance by checking final state membership, while $\delta$ only computes state-to-state movements
3. Function $\hat{\delta}$ handles nondeterministic transitions by exploring multiple computation paths, while $\delta$ is purely deterministic
4. Function $\hat{\delta}$ incorporates ε-transitions for empty string processing, while $\delta$ requires non-empty input symbols for all transitions

Question 9

1. For each player $i$, strategy $s_i^*$ must maximize $u_i(s_1^*, s_2^*, s_3^*)$ over all possible strategy profiles in the game
2. The strategy profile $s^*$ must represent a Pareto optimal outcome maximizing the sum of all players' utilities simultaneously
3. For each player $i$, no unilateral deviation from $s_i^*$ can improve $u_i$ given that other players maintain their strategies (correct answer)
4. Each player $i$ must have equal expected utility under $s^*$, ensuring fairness across all participants in the equilibrium

Question 10

1. $\sum_{j=1}^{20} a_{ij} \leq 5$ for all $i \in \{1,2,\ldots,20\}$ (correct answer)
2. $\sum_{i=1}^{20} a_{ij} \leq 5$ for all $j \in \{1,2,\ldots,20\}$
3. $\deg(v_i) \leq 5$ for all vertices $v_i$ in the friendship graph
4. $|N(i)| \leq 5$ for all $i \in V$ where $N(i)$ is the neighborhood of $i$

Question 11

1. $\forall u \in U: (u,p_0) \in R \land \forall u \in U: [(u,p_1) \in R \rightarrow (u,p_2) \in R]$ (correct answer)
2. $\forall u \in U: (u,p_0) \in R \land \forall u \in U: [(u,p_2) \in R \rightarrow (u,p_1) \in R]$
3. $\exists u \in U: (u,p_0) \in R \land \forall u \in U: [(u,p_1) \in R \leftrightarrow (u,p_2) \in R]$
4. $\forall u \in U: (u,p_0) \in R \land \neg\exists u \in U: [(u,p_1) \in R \land (u,p_2) \notin R]$

Question 12

1. $\forall m_1, m_2 \in \{0,1\}^*: m_1 \neq m_2 \implies h(m_1) \neq h(m_2)$
2. The probability that $\exists m_1 \neq m_2$ such that $h(m_1) = h(m_2)$ is negligible for any polynomial-time adversary
3. $|\{(m_1,m_2) : m_1 \neq m_2 \land h(m_1) = h(m_2)\}| < 2^{20}$ for the daily message set
4. For any polynomial-time algorithm $A$, $\Pr[A() = (m_1,m_2) : m_1 \neq m_2 \land h(m_1) = h(m_2)] \leq \text{negl}(\lambda)$ (correct answer)

Question 13

1. $L = \{ATG \cdot w \cdot s : w \in \Sigma^*, s \in \{TAA, TAG, TGA\}, |ATG \cdot w \cdot s| \equiv 0 \pmod{3}\}$
2. $L = \{ATG \cdot w \cdot s : w \in \Sigma^*, s \in \{TAA, TAG, TGA\}, |w| \equiv 0 \pmod{3}\}$
3. $L = \{u : u = ATG \cdot w \cdot s, w \in (\Sigma^3)^*, s \in \{TAA, TAG, TGA\}\}$ (correct answer)
4. $L = \{ATG \cdot w \cdot s : w \in \Sigma^+, s \in \{TAA, TAG, TGA\}, |ATG \cdot w \cdot s| \bmod 3 = 0\}$

Question 14

1. $f(n) = \Theta(n \log n) = \Theta(n^1 \log n)$, so $f(n) = \Theta(n^{\log_2 2} \log n)$, applying Case 2 (correct answer)
2. $f(n) = \Omega(n \log n) = \Omega(n^{1+\epsilon})$ for $\epsilon = \log n - 1 > 0$, applying Case 3
3. $f(n) = O(n \log n) = O(n^{1-\epsilon})$ for some $\epsilon > 0$, applying Case 1
4. $f(n) = \Theta(n \log n)$ and $n^{\log_b a} = n^1$, but $\log n$ is not polynomial, so Master Theorem doesn't apply

Question 15

1. For any node at index $i$: $\text{priority}[i] \leq \text{priority}[2i]$ and $\text{priority}[i] \leq \text{priority}[2i+1]$
2. For any node at index $i$: $\text{priority}[\lfloor i/2 \rfloor] \leq \text{priority}[i]$ when $i > 1$ (correct answer)
3. For any parent node $p$ with children $c_1, c_2$: $\text{priority}[p] \geq \min(\text{priority}[c_1], \text{priority}[c_2])$
4. For the root node $r$: $\text{priority}[r] = \min\{\text{priority}[i] : i \in \text{heap}\}$

Question 16

1. $P(E_1 \cup E_2 \cup E_3) = 0.7 + 0.8 + 0.6 - P(E_1 \cap E_2) - P(E_2 \cap E_3) - P(E_1 \cap E_3) + 0.1$
2. $P(E_1 \cup E_2 \cup E_3) = P(E_1) + P(E_2) + P(E_3) - 0.7 - 0.8 - 0.6 + 0.1$
3. $P(E_1 \cup E_2 \cup E_3) = 1.1 - P(E_1 \cap E_2) - P(E_2 \cap E_3) - P(E_1 \cap E_3) + 0.1$
4. $P(E_1 \cup E_2 \cup E_3) = P(E_1) + P(E_2) + P(E_3) - P(E_1 \cap E_2) - P(E_2 \cap E_3) - P(E_1 \cap E_3) + 0.1$ (correct answer)

Question 17

1. $\sum_{k=0}^{3} P_{\text{Normal},\text{Breach}}^k$ representing the sum over all possible path lengths
2. $P_{\text{Normal},\text{Breach}}^3$ where the transition probability is raised to the third power
3. $(P^3)_{\text{Normal},\text{Breach}}$ where $P^3$ is the matrix $P$ multiplied by itself 3 times (correct answer)
4. $3 \cdot P_{\text{Normal},\text{Breach}}$ since there are 3 time steps to accumulate probability

Question 18

1. There exists a direct edge from $A$ to $C$ with weight greater than 7
2. The shortest path from $A$ to $C$ does not pass through vertex $B$ (correct answer)
3. The graph contains at least one cycle involving vertices $A$, $B$, or $C$
4. Vertex $B$ lies on some shortest path from $A$ to $C$, but not necessarily the unique one