Use correct notation and definitions - Discrete Math

1. A computer science student is modeling a social network where each person can be friends with at most 5 others, and friendship is always mutual. If the network has 20 people and exactly 35 friendships, which notation correctly expresses the constraint that person $i$ has at most 5 friends?
   Answer: $\sum_{j=1}^{20} a_{ij} \leq 5$ for all $i \in \{1,2,\ldots,20\}$ In an adjacency matrix representation, $a_{ij} = 1$ if persons $i$ and $j$ are friends, 0 otherwise. The sum $\sum_{j=1}^{20} a_{ij}$ counts all of person $i$'s friendships by summing across row $i$. Choice A correctly expresses this constraint. Choice B sums down column $j$, which would constrain how many people are friends with person $j$. Choices C and D are mathematically correct but use graph theory notation rather than the discrete modeling notation typically expected in this context.
2. A scheduling algorithm uses a priority queue implemented as a binary heap. Jobs arrive with priorities and the algorithm always processes the job with minimum priority value first. If the current heap contains jobs with priorities [2, 5, 3, 8, 7, 9, 4] arranged in a valid min-heap structure, what is the correct notation for the heap property that must be satisfied?
   Answer: For any node at index $i$: $\text{priority}[\lfloor i/2 \rfloor] \leq \text{priority}[i]$ when $i > 1$ In a min-heap with 1-based indexing, the heap property requires that every node's priority is less than or equal to its children's priorities. This is equivalently stated as: every node's priority is greater than or equal to its parent's priority. Choice B correctly expresses this using parent-child relationships where $\lfloor i/2 \rfloor$ gives the parent of node $i$. Choice A states the property correctly but assumes children exist (doesn't handle boundary cases). Choice C incorrectly uses $\geq$ instead of $\leq$. Choice D only describes a property of the root, not the general heap property.
3. A database designer uses the notation $R(A, B, C) \rightarrow S(X, Y)$ to indicate a relationship transformation where relation $R$ with attributes $A, B, C$ maps to relation $S$ with attributes $X, Y$. If she defines $\pi_{A,C}(R) = T$ and then writes $T \bowtie_{A=X} S = U$, what operation sequence does this represent in relational algebra?
   Answer: Project $R$ onto columns $A$ and $C$, then perform theta join with $S$ where $A$ equals $X$ The notation $\pi_{A,C}(R)$ represents projection (selecting specific columns), creating relation $T$ with only columns $A$ and $C$ from $R$. The notation $\bowtie_{A=X}$ represents a theta join with the specific condition that attribute $A$ from the left relation equals attribute $X$ from the right relation. Choice A is wrong because $\bowtie_{A=X}$ specifies a condition, not a natural join. Choice C confuses projection with selection. Choice D describes the implementation of join as filtered cartesian product, but the notation specifically indicates a theta join operation.
4. A game theory student models a scenario using the notation $G = (N, (S_i)_{i \in N}, (u_i)_{i \in N})$ where $N = \{1, 2, 3\}$, $S_1 = \{A, B\}$, $S_2 = \{X, Y\}$, and $S_3 = \{P, Q\}$. When analyzing Nash equilibria, she writes $s^* = (s_1^*, s_2^*, s_3^*) \in S_1 \times S_2 \times S_3$. What constraint must $s^*$ satisfy to be a Nash equilibrium?
   Answer: For each player $i$, no unilateral deviation from $s_i^*$ can improve $u_i$ given that other players maintain their strategies When you encounter game theory notation like $G = (N, (S_i)_{i \in N}, (u_i)_{i \in N})$, you're looking at a normal-form game with players $N$, strategy sets $S_i$, and utility functions $u_i$. The key concept being tested is your understanding of Nash equilibrium's fundamental definition. A Nash equilibrium occurs when each player is making their best possible choice given what all other players are doing. This means no player can unilaterally change their strategy and improve their payoff. Answer C captures this perfectly: for each player $i$, no unilateral deviation from $s_i^*$ can improve $u_i$ given that other players maintain their strategies. This is the mathematical essence of Nash equilibrium. Answer A is incorrect because it suggests each player maximizes their utility over all possible strategy profiles in the entire game, which ignores the strategic interdependence that defines Nash equilibrium. Answer B confuses Nash equilibrium with Pareto optimality – these are completely different solution concepts, and Nash equilibria are often not Pareto optimal. Answer D incorrectly describes some notion of fairness or equal payoffs, but Nash equilibrium has nothing to do with equal utilities across players. Remember this key distinction: Nash equilibrium is about mutual best responses (no player wants to deviate unilaterally), while Pareto optimality is about collective efficiency. Many students confuse these concepts, so always focus on the "no profitable unilateral deviation" criterion when identifying Nash equilibria.
5. In a formal verification system, an engineer writes the temporal logic formula $\square(p \rightarrow \diamond q)$ where $p$ represents "system receives input" and $q$ represents "system produces output." What system property does this formula specification require?
   Answer: Whenever the system receives input, it must eventually produce output, though the timing of output is not constrained The formula $\square(p \rightarrow \diamond q)$ means "always, if $p$ then eventually $q$". The $\square$ operator means "always" (globally), $\rightarrow$ is implication, and $\diamond$ means "eventually" (finally). So whenever the system receives input ($p$), it must eventually produce output ($q$), but there's no constraint on timing. Choice A incorrectly adds immediacy requirement. Choice C misinterprets the formula as requiring continuous output during input. Choice D reverses the causality and adds requirements not present in the formula.
6. A bioinformatics researcher models DNA sequences as strings over the alphabet $\Sigma = \{A, T, G, C\}$. She defines a 'valid gene segment' as a substring that starts with 'ATG', ends with one of \{TAA, TAG, TGA\}, and has length divisible by 3. If $L$ represents the set of all valid gene segments, which formal definition correctly captures this language?
   Answer: $L = \{u : u = ATG \cdot w \cdot s, w \in (\Sigma^3)^*, s \in \{TAA, TAG, TGA\}\}$ A valid gene segment must have total length divisible by 3. Since ATG has length 3 and each stop codon (TAA, TAG, TGA) has length 3, the middle portion $w$ must also have length divisible by 3 to maintain the overall divisibility. Choice C correctly ensures this by requiring $w \in (\Sigma^3)^*$, meaning $w$ is a concatenation of 3-character blocks. Choice A allows any $w$ and checks total length, but doesn't ensure proper codon structure. Choice B only checks $|w| \equiv 0 \pmod{3}$ but the total length constraint is implied, not explicit. Choice D is similar to A but uses $\Sigma^+$ requiring non-empty $w$.
7. A database designer models user permissions using a relation $R \subseteq U \times P$ where $U$ is the set of users and $P$ is the set of permissions. The designer states: 'Every user must have at least the basic permission $p_0$, and no user can have permission $p_1$ without also having permission $p_2$.' Which logical expression correctly captures both constraints?
   Answer: $\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]$ The first constraint 'every user must have at least the basic permission $p_0$' translates to $\forall u \in U: (u,p_0) \in R$. The second constraint 'no user can have permission $p_1$ without also having permission $p_2$' means if a user has $p_1$, then they must have $p_2$, which is $\forall u \in U: [(u,p_1) \in R \rightarrow (u,p_2) \in R]$. Choice B reverses the implication direction. Choice C uses existential quantification for the first constraint and bidirectional implication for the second. Choice D is equivalent to A but uses a more complex negated existential form.
8. In formal language theory, a student defines an automaton $M = (Q, \Sigma, \delta, q_0, F)$ and writes $\hat{\delta}(q_0, w) \in F$ for a string $w \in \Sigma^*$. She then claims that $L(M) = \{w \in \Sigma^* : \hat{\delta}(q_0, w) \in F\}$. What does the extended transition function $\hat{\delta}$ compute that differs from the basic transition function $\delta$?
   Answer: Function $\hat{\delta}$ processes entire strings by composing individual symbol transitions, while $\delta$ handles only single symbol transitions The basic transition function $\delta: Q \times \Sigma \rightarrow Q$ defines transitions on single symbols, while the extended transition function $\hat{\delta}: Q \times \Sigma^* \rightarrow Q$ processes entire strings by applying $\delta$ repeatedly: $\hat{\delta}(q, wa) = \delta(\hat{\delta}(q,w), a)$ with $\hat{\delta}(q, \varepsilon) = q$. Choice B incorrectly suggests $\hat{\delta}$ determines acceptance - it just computes the final state. Choice C incorrectly introduces nondeterminism not specified in the definition. Choice D incorrectly suggests ε-transitions, which aren't implied by the standard DFA definition given.
9. A network security analyst models intrusion detection as a Markov chain with states $S = \{\text{Normal}, \text{Alert}, \text{Breach}\}$. The system transitions between states based on a transition matrix $P$ where $P_{ij}$ represents the probability of moving from state $i$ to state $j$ in one time step. If the analyst wants to compute the probability of being in the Breach state after exactly 3 time steps starting from Normal, which notation correctly expresses this quantity?
   Answer: $(P^3)_{\text{Normal},\text{Breach}}$ where $P^3$ is the matrix $P$ multiplied by itself 3 times When you encounter Markov chain problems asking about probabilities after multiple time steps, you're dealing with matrix powers and the Chapman-Kolmogorov equations. The key insight is that to find probabilities after n steps, you need the n-th power of the transition matrix. To find the probability of being in the Breach state after exactly 3 steps starting from Normal, you must account for all possible paths through the state space. This requires computing $P^3$ (the transition matrix multiplied by itself three times) and then selecting the entry $(P^3)_{\text{Normal},\text{Breach}}$. Each matrix multiplication incorporates one additional time step, properly weighting all intermediate paths. Option A incorrectly sums probabilities across different path lengths from 0 to 3 steps, which would give you the probability of ever reaching Breach within 3 steps, not the probability of being there at exactly step 3. Option B misunderstands matrix notation—you can't raise a single matrix entry to a power and expect meaningful results about multi-step transitions. Option D simply multiplies the one-step probability by 3, which ignores the complex path dependencies inherent in Markov chains and would often exceed 1 (impossible for a probability). The correct answer is C: $(P^3)_{\text{Normal},\text{Breach}}$ properly captures the 3-step transition probability. Study tip: Remember that for n-step transition probabilities in Markov chains, always think "matrix to the nth power, then extract the relevant entry." The matrix power handles all the path complexity automatically.
10. A cryptography application models message authentication using a hash function $h: \{0,1\}^* \to \{0,1\}^{256}$. The system is said to be 'collision-resistant' if finding two different messages with the same hash is computationally infeasible. Given that the function processes approximately $2^{20}$ messages daily, which statement correctly describes the collision resistance requirement in formal notation?
    Answer: 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)$ Collision resistance is a computational security property, not a mathematical impossibility. Since $h$ maps an infinite domain to a finite codomain, collisions must exist by the pigeonhole principle. Choice D correctly captures that no polynomial-time algorithm can find collisions with non-negligible probability, where $\lambda$ is the security parameter. Choice A describes a collision-free function, which is impossible. Choice B is imprecise about the adversary model. Choice C focuses on a specific daily limit rather than the general computational hardness requirement.
11. A combinatorics researcher analyzes a generating function $F(x) = \sum_{n=0}^{\infty} a_n x^n$ where $a_n$ counts certain combinatorial objects of size $n$. She discovers that $F(x) = \frac{1}{1-x-x^2}$ and wants to find a recurrence relation for the coefficients. Using the equation $(1-x-x^2)F(x) = 1$, what recurrence relation governs the sequence $(a_n)_{n \geq 0}$?
    Answer: $a_n = a_{n-1} + a_{n-2}$ for $n \geq 2$, with appropriate initial conditions determined by the generating function From $(1-x-x^2)F(x) = 1$, expanding the left side gives $(1-x-x^2)\sum_{n=0}^{\infty} a_n x^n = \sum_{n=0}^{\infty} a_n x^n - \sum_{n=0}^{\infty} a_n x^{n+1} - \sum_{n=0}^{\infty} a_n x^{n+2} = 1$. Collecting coefficients of $x^n$ for $n \geq 2$: $a_n - a_{n-1} - a_{n-2} = 0$, giving $a_n = a_{n-1} + a_{n-2}$. Choice B incorrectly adds a constant term that doesn't appear in the coefficient equation. Choice C incorrectly involves derivatives. Choice D gets the wrong signs in the recurrence relation.
12. In a formal logic system, the statement $\forall x \in \mathbb{Z}^+, \exists y \in \mathbb{Z}^+ : (x | y) \land (y > x)$ is being evaluated, where $a | b$ means "$a$ divides $b$". A student claims this statement is true and provides the construction $y = 2x$ as justification. What is the most precise assessment of this approach?
    Answer: The construction demonstrates the existential quantifier correctly and constitutes a complete proof of the statement The statement says for every positive integer $x$, there exists a positive integer $y$ such that $x$ divides $y$ and $y > x$. The construction $y = 2x$ works for every positive integer $x$: clearly $x | 2x$ and $2x > x$ for all $x \in \mathbb{Z}^+$. This single construction is sufficient to prove the existential statement for all $x$. Choice A misses that this is about existence, not universality over $y$. Choice B incorrectly suggests the proof is incomplete. Choice C misunderstands that one construction proving existence for all $x$ is sufficient for an existential statement.
13. An algorithm designer analyzes a recursive function $T(n)$ that satisfies the recurrence $T(n) = 2T(n/2) + \Theta(n \log n)$ for $n > 1$ with $T(1) = \Theta(1)$. Using the Master Theorem, she needs to compare $f(n) = \Theta(n \log n)$ with $n^{\log_b a}$. Which comparison correctly determines the applicable case?
    Answer: $f(n) = \Theta(n \log n) = \Theta(n^1 \log n)$, so $f(n) = \Theta(n^{\log_2 2} \log n)$, applying Case 2 In this recurrence, $a = 2$, $b = 2$, so $n^{\log_b a} = n^{\log_2 2} = n^1 = n$. We have $f(n) = \Theta(n \log n)$. Since $f(n) = \Theta(n^{\log_b a} \log n) = \Theta(n \log n)$, this matches Case 2 of the Master Theorem exactly. Choice B incorrectly treats $\log n$ as a polynomial factor. Choice C incorrectly suggests $f(n)$ is polynomially smaller than $n$. Choice D incorrectly claims the Master Theorem doesn't apply when it clearly does.
14. In a distributed computing model, a researcher uses the notation $\text{CONF} \vdash_{\alpha} \text{CONF}'$ to represent state transitions, where $\text{CONF}$ and $\text{CONF}'$ are system configurations and $\alpha$ is an action. When she writes $\text{CONF}_0 \vdash_{\alpha_1} \text{CONF}_1 \vdash_{\alpha_2} \text{CONF}_2 \vdash_{\alpha_3} \text{CONF}_3$, what does this sequence notation formally specify?
    Answer: A sequence of valid state transitions showing one possible execution trace through the system's state space When you encounter formal transition notation in discrete mathematics or computer science, you're looking at a way to describe how systems change state over time. The notation $\text{CONF} \vdash_{\alpha} \text{CONF}'$ is a standard way to express "configuration CONF can transition to configuration CONF' by performing action α." The sequence $\text{CONF}_0 \vdash_{\alpha_1} \text{CONF}_1 \vdash_{\alpha_2} \text{CONF}_2 \vdash_{\alpha_3} \text{CONF}_3$ shows a chain of transitions, representing one possible path the system could take through its state space. Each transition is valid (the $\vdash$ symbol confirms this), but this is just one of potentially many possible execution traces from the initial state $\text{CONF}_0$. This makes D correct. A is wrong because the notation doesn't imply determinism—other actions might also be possible from each configuration. The sequence shows what happened, not what must happen. B misunderstands the temporal nature of the notation. The actions occur sequentially, not simultaneously, and only $\alpha_1$ needs to be enabled in $\text{CONF}_0$. C incorrectly suggests parallel execution. The chain notation explicitly shows sequential transitions where each action transforms one configuration into the next. Remember that formal transition systems describe all possible behaviors of a system. When you see a specific sequence like this, it's documenting one particular execution trace—a single path through the larger space of possible system behaviors. Focus on the sequential, one-step-at-a-time nature of these transition chains.
15. In a discrete optimization problem, a researcher defines the constraint set $C = \{(x,y) \in \mathbb{Z}^2 : x^2 + y^2 \leq 25, x \geq 0, y \geq 0\}$ and the objective function $f(x,y) = 3x + 4y$. When she writes $\max_{(x,y) \in C} f(x,y)$, what computational challenge does this notation specifically indicate?
    Answer: The optimization must evaluate integer points only, requiring enumeration of feasible lattice points within bounds The constraint set $C$ restricts $(x,y)$ to integer points ($\mathbb{Z}^2$) in the first quadrant within a circle of radius 5. This creates a finite set of lattice points that must be enumerated: (0,0), (0,1), ..., (0,5), (1,0), ..., (4,3), (5,0), etc. This is an integer programming problem requiring discrete optimization. Choice A is wrong because there are only finitely many integer points in the bounded region. Choice C is wrong because the constraint set is convex (intersection of convex sets). Choice D is wrong because the bounded constraint set makes the linear objective function bounded.
16. A logistics company models package routing using a directed graph where edge weights represent travel times in hours. The company defines $d(u,v)$ as the shortest path distance from vertex $u$ to vertex $v$. If $d(A,C) = 7$, $d(A,B) = 3$, and $d(B,C) = 5$, which statement about the graph structure is necessarily true?
    Answer: The shortest path from $A$ to $C$ does not pass through vertex $B$ Since $d(A,B) + d(B,C) = 3 + 5 = 8 > 7 = d(A,C)$, the path $A \to B \to C$ is longer than the shortest path from $A$ to $C$. Therefore, the shortest path from $A$ to $C$ cannot pass through $B$. Choice A is incorrect because there might be no direct edge, or it could have weight exactly 7. Choice C is incorrect as the given distances don't imply any cycles. Choice D contradicts our analysis since $B$ cannot be on any shortest $A$-to-$C$ path.
17. In complexity theory, a researcher defines $L_1 \leq_m^p L_2$ to denote polynomial-time many-one reducibility between languages $L_1$ and $L_2$. She then states: "If $L_1$ is $\mathbf{NP}$-complete and $L_1 \leq_m^p L_2$, then $L_2$ is $\mathbf{NP}$-hard." What does this logical statement require about $L_2$?
    Answer: 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}$ When you encounter complexity theory problems involving reductions and completeness, focus on the precise definitions: NP-complete means a language is both in NP and NP-hard, while NP-hard means every language in NP reduces to it in polynomial time. The key insight here is understanding what polynomial-time many-one reducibility preserves. Since $L_1$ is NP-complete, every language in NP reduces to $L_1$ (that's what NP-hard means). When we have $L_1 \leq_m^p L_2$, we can compose reductions: for any language $L \in \mathbf{NP}$, we get $L \leq_m^p L_1 \leq_m^p L_2$, which gives us $L \leq_m^p L_2$ by transitivity. Therefore, every NP language reduces to $L_2$, making $L_2$ at least as hard as any NP problem—this is exactly the definition of NP-hard. Choice C captures this correctly. Choice A incorrectly requires $L_2 \in \mathbf{NP}$. Being NP-hard doesn't require membership in NP—$L_2$ could be much harder, even undecidable. Choice B demands bidirectional reducibility, but we only know $L_1$ reduces to $L_2$, not vice versa. Choice D makes an unwarranted connection to the $\mathbf{P} = \mathbf{NP}$ question that doesn't follow from the given information. Study tip: Remember that NP-hard is about being "at least as hard as NP" without requiring membership in NP itself. Many NP-hard problems are actually much harder than NP.
18. In a discrete probability model, events $E_1, E_2, E_3$ satisfy $P(E_1 \cup E_2) = 0.7$, $P(E_2 \cup E_3) = 0.8$, and $P(E_1 \cup E_3) = 0.6$. If $P(E_1 \cap E_2 \cap E_3) = 0.1$, which expression correctly represents $P(E_1 \cup E_2 \cup E_3)$ using the inclusion-exclusion principle?
    Answer: $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$ The inclusion-exclusion principle states: $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) + P(E_1 \cap E_2 \cap E_3)$. Choice D correctly applies this formula. Choice A incorrectly substitutes union probabilities for individual event probabilities. Choice B has the wrong signs. Choice C attempts to use $P(E_1) + P(E_2) + P(E_3) = 1.1$ but this sum could exceed 1 due to overlaps, making the approach invalid.

Start this quiz