Programming, Data Structures and Algorithms using Python · Quiz 1 · May 2024

**Answer: D** **Topic:** Relational Databases — *Cascading Deletes with Self-Referencing Foreign Key* ### Step-by-Step Solution **Step 1:** In the given table with primary key `X` and foreign key `Z REFERENCES X ON DELETE CASCADE`, deleting a row with `X = v` automatically deletes every row whose `Z = v`, recursively. **Step 2:** Trace the chain reaction starting from the deletion of `(4, 2, 4)` (`X = 4`): 1. Deleting `X = 4` triggers the deletion of `(5, 2, 4)` because its `Z = 4`. 2. Deleting `X = 5` triggers the deletion of `(1, 1, 5)`, `(2, 2, 5)`, and `(3, 1, 5)` because their `Z = 5`. 3. Deleting `X = 1` triggers the deletion of `(6, 1, 1)` and `(7, 4, 1)` because their `Z = 1`. 4. Deleting `X = 7` triggers the deletion of `(8, 4, 7)` because its `Z = 7`. **Step 3:** Thus, **all the remaining rows will be deleted**, making **D** correct. **Key Takeaway / Tip:** Follow the foreign-key dependency chain $4 \leftarrow 5 \leftarrow \{1, 2, 3\} \leftarrow \{6, 7\} \leftarrow 8$ step by step until no matching `Z` values remain. A: **Incorrect:** Option A ((2,2,5) and (3,1,5)) does not satisfy the conditions derived in the step-by-step analysis for Cascading Deletes with Self-Referencing Foreign Key (correct choice: D). B: **Incorrect:** Option B ((5,2,4), (1,1,5), (2,2,5) and (3,1,5)) does not satisfy the conditions derived in the step-by-step analysis for Cascading Deletes with Self-Referencing Foreign Key (correct choice: D). C: **Incorrect:** Option C ((6,1,1),(7,4,1) and (8,4,7)) does not satisfy the conditions derived in the step-by-step analysis for Cascading Deletes with Self-Referencing Foreign Key (correct choice: D). D: **Correct:** Option D (All the remaining rows will be deleted       **PDSA** **Section Id :** 64065359209 **Section Number :** 2 **Section type :** Online **Mandatory or Optional :** Mandatory **Numbe...) matches our derived result under Cascading Deletes with Self-Referencing Foreign Key. Follow the foreign-key dependency chain $4 \leftarrow 5 \leftarrow \{1, 2, 3\} \leftarrow \{6, 7\} \leftarrow 8$ step by step until no matching `Z` values remain.

**Answer: C** **Topic:** Asymptotic Analysis — *Transitivity and Sum Rule of Big-O Notation* ### Step-by-Step Solution **Step 1:** Analyze **Statement 1 (Transitivity of Big-O)**: - If $f(n) = O(g(n))$, then $f(n) \le c_1 g(n)$ for large $n$. - If $g(n) = O(h(n))$, then $g(n) \le c_2 h(n)$ for large $n$. - Combining both gives $f(n) \le c_1 c_2 h(n)$, so $f(n) = O(h(n))$. **Statement 1 is true**. **Step 2:** Analyze **Statement 2 (Sum Rule of Big-O)**: - If $f(n) \le c_1 h(n)$ and $g(n) \le c_2 h(n)$ for large $n$, then $f(n) + g(n) \le (c_1 + c_2)h(n)$, so $f + g = O(h)$. **Statement 2 is true**. **Step 3:** Therefore, **Both Statements 1 and 2 are true** (**C**). **Key Takeaway / Tip:** Big-O notation is transitive and closed under finite addition. A: **Incorrect:** Option A (Only statement 1 is true.) does not satisfy the conditions derived in the step-by-step analysis for Transitivity and Sum Rule of Big-O Notation (correct choice: C). B: **Incorrect:** Option B (Only statement 2 is true) does not satisfy the conditions derived in the step-by-step analysis for Transitivity and Sum Rule of Big-O Notation (correct choice: C). C: **Correct:** Option C (Both Statements 1 and 2 are true) matches our derived result under Transitivity and Sum Rule of Big-O Notation. Big-O notation is transitive and closed under finite addition. D: **Incorrect:** Option D (Both Statements 1 and 2 are false) does not satisfy the conditions derived in the step-by-step analysis for Transitivity and Sum Rule of Big-O Notation (correct choice: C).

**Answer: B** **Topic:** Asymptotic Analysis — *Recursive vs. Iterative Fibonacci Time Complexity* ### Step-by-Step Solution **Step 1:** Determine the asymptotic time complexity $f(n)$ of **Code-A** (naive binary recursion `fib(n-1) + fib(n-2)`): $$f(n) = \Theta(\phi^n) = O(2^n)\text{ (exponential time)}$$ where $\phi = \frac{1 + \sqrt{5}}{2} \approx 1.618$. **Step 2:** Determine the asymptotic time complexity $g(n)$ of **Code-B** (dynamic programming / iterative loop from `2` to `n-1` appending `L[-2] + L[-1]` in $O(1)$ time per step): $$g(n) = \Theta(n)\text{ (linear time)}$$ **Step 3:** Compare growth rates: since linear $g(n) = \Theta(n)$ grows strictly slower than exponential $f(n) = \Theta(\phi^n)$, we have **$g(n) = O(f(n))$** (while $f(n) \ne O(g(n))$). **Step 4:** Thus, **B** (`g(n) = O(f(n))`) is correct. **Key Takeaway / Tip:** Memoizing or tabulating previous Fibonacci values (`Code-B`) reduces the time complexity from exponential $O(\phi^n)$ to linear $O(n)$. A: **Incorrect:** Option A (

) does not satisfy the conditions derived in the step-by-step analysis for Recursive vs. Iterative Fibonacci Time Complexity (correct choice: B). B: **Correct:** Option B (

) matches our derived result under Recursive vs. Iterative Fibonacci Time Complexity. Memoizing or tabulating previous Fibonacci values (`Code-B`) reduces the time complexity from exponential $O(\phi^n)$ to linear $O(n)$. C: **Incorrect:** Option C (

) does not satisfy the conditions derived in the step-by-step analysis for Recursive vs. Iterative Fibonacci Time Complexity (correct choice: B). D: **Incorrect:** Option D (

) does not satisfy the conditions derived in the step-by-step analysis for Recursive vs. Iterative Fibonacci Time Complexity (correct choice: B).

**Answer: D** **Topic:** Searching Algorithms — *Binary Search for a Missing Element in a Sorted Array* ### Step-by-Step Solution **Step 1:** We are given a sorted array $L$ of $n$ elements from $1, 2, \dots, n+1$ (or $1$ to $n$ with one interior element missing). In a prefix with no missing element, the value at 0-based index $i$ is $L[i] = i + 1$; once an element is skipped, $L[i] > i + 1$. **Step 2:** Because the condition $L[i] == i + 1$ is monotonic (True for all indices before the missing number, False for all indices after it), we can use **Binary Search** to find the first index $i$ where $L[i] > i + 1$. **Step 3:** Binary search halves the search range at each step, running in **$O(\log n)$** time. **Step 4:** Therefore, **D** (`O(log n)`) is correct. **Key Takeaway / Tip:** Whenever a sorted array exhibits a monotonic property (such as $L[i] - i$ jumping from $1$ to $2$), binary search finds the transition point in $O(\log n)$ time. A: **Incorrect:** Option A (

) does not satisfy the conditions derived in the step-by-step analysis for Binary Search for a Missing Element in a Sorted Array (correct choice: D). B: **Incorrect:** Option B (

) does not satisfy the conditions derived in the step-by-step analysis for Binary Search for a Missing Element in a Sorted Array (correct choice: D). C: **Incorrect:** Option C (

) does not satisfy the conditions derived in the step-by-step analysis for Binary Search for a Missing Element in a Sorted Array (correct choice: D). D: **Correct:** Option D (

) matches our derived result under Binary Search for a Missing Element in a Sorted Array. Whenever a sorted array exhibits a monotonic property (such as $L[i] - i$ jumping from $1$ to $2$), binary search finds the transition point in $O(\log n)$ time.

**Answer: D** **Topic:** Sorting Algorithms — *Best-Case Time Complexity of Selection Sort* ### Step-by-Step Solution **Step 1:** Inspect the given `selectionsort(L)` code: - The outer loop `for i in range(n):` runs for $i = 0, 1, \dots, n-1$. - For each $i$, the inner loop `for j in range(i+1, n):` unconditionally compares `L[j] < L[minpos]` for all $n - 1 - i$ remaining elements, regardless of whether the array is already sorted. **Step 2:** Sum the total number of comparisons across all iterations: $$\sum_{i=0}^{n-1} (n - 1 - i) = \frac{n(n - 1)}{2} = \Theta(n^2)$$ **Step 3:** Therefore, even when the input list is already sorted in ascending order, Selection Sort takes **$O(n^2)$** time (**D**). **Key Takeaway / Tip:** Unlike Insertion Sort (which runs in $O(n)$ on an already-sorted array), Selection Sort has no early-exit mechanism and always performs $\Theta(n^2)$ comparisons. A: **Incorrect:** Option A (

) does not satisfy the conditions derived in the step-by-step analysis for Best-Case Time Complexity of Selection Sort (correct choice: D). B: **Incorrect:** Option B (

) does not satisfy the conditions derived in the step-by-step analysis for Best-Case Time Complexity of Selection Sort (correct choice: D). C: **Incorrect:** Option C (

) does not satisfy the conditions derived in the step-by-step analysis for Best-Case Time Complexity of Selection Sort (correct choice: D). D: **Correct:** Option D (

) matches our derived result under Best-Case Time Complexity of Selection Sort. Unlike Insertion Sort (which runs in $O(n)$ on an already-sorted array), Selection Sort has no early-exit mechanism and always performs $\Theta(n^2)$ comparisons.

**Answer: B** **Topic:** Data Structures — *Matching Applications to Appropriate Data Structures* ### Step-by-Step Solution **Step 1:** Match each real-world application to its most natural data structure: 1. **Checking if a word is a palindrome**: Pushing characters onto a **Stack (iii)** and popping them reverses the word in LIFO order to check equality (`1 - iii`). 2. **Finding order in which courses should be taken**: Prerequisite dependencies have direction ($A \to B$), modeled as topological sorting on **Directed Graphs (iv)** (`2 - iv`). 3. **Social media network**: Mutual friendship connections are symmetric, modeled using an **Undirected Graph (ii)** (`3 - ii`). 4. **Traffic Management**: Vehicles waiting at an intersection or toll booth are processed in FIFO order using a **Queue (i)** (`4 - i`). **Step 2:** Thus, the correct matching is **1 - iii, 2 - iv, 3 - ii, 4 - i**, which corresponds to **B**. **Key Takeaway / Tip:** Course prerequisites require a Directed Acyclic Graph (DAG) (`iv`), whereas symmetric friendship networks use an Undirected Graph (`ii`). A: **Incorrect:** Option A (1 - ii, 2 - iii, 3 - iv, 4 - i) does not satisfy the conditions derived in the step-by-step analysis for Matching Applications to Appropriate Data Structures (correct choice: B). B: **Correct:** Option B (1 - iii, 2 - iv, 3 - ii, 4 - i) matches our derived result under Matching Applications to Appropriate Data Structures. Course prerequisites require a Directed Acyclic Graph (DAG) (`iv`), whereas symmetric friendship networks use an Undirected Graph (`ii`). C: **Incorrect:** Option C (1 - i, 2 - ii, 3 - iv, 4 - iii) does not satisfy the conditions derived in the step-by-step analysis for Matching Applications to Appropriate Data Structures (correct choice: B). D: **Incorrect:** Option D (1 - iii, 2 - ii, 3 - iv, 4 - i) does not satisfy the conditions derived in the step-by-step analysis for Matching Applications to Appropriate Data Structures (correct choice: B).

**Answer: B** **Topic:** Graph Algorithms — *Classifying DFS Edges Using Pre and Post Numbers* ### Step-by-Step Solution **Step 1:** Recall how DFS discovery (`pre`) and finishing (`post`) timestamps classify a directed edge $(u, v)$: - **Tree / Forward edge**: $v$ is a descendant of $u$, so $[\text{pre}[v], \text{post}[v]] \subset [\text{pre}[u], \text{post}[u]]$. - **Back edge**: $v$ is an ancestor of $u$, so $[\text{pre}[u], \text{post}[u]] \subset [\text{pre}[v], \text{post}[v]]$. - **Cross edge**: the intervals $[\text{pre}[u], \text{post}[u]]$ and $[\text{pre}[v], \text{post}[v]]$ are completely disjoint. **Step 2:** Compare the given intervals for $u$ and $v$: - $[\text{pre}[u], \text{post}[u]] = [3, 6]$ - $[\text{pre}[v], \text{post}[v]] = [1, 10]$ **Step 3:** Since $1 < 3 < 6 < 10$, we have $[3, 6] \subset [1, 10]$, which means $v$ was discovered before $u$ and finished after $u$ ($v$ is an ancestor of $u$ in the DFS tree). Therefore, $(u, v)$ is a **back edge** (**B**). **Key Takeaway / Tip:** When $u$'s `[pre, post]` interval is nested strictly inside $v$'s `[pre, post]` interval, $v$ is an ancestor of $u$, making $(u, v)$ a back edge (which also indicates a directed cycle!). A: **Incorrect:** Option A (

) does not satisfy the conditions derived in the step-by-step analysis for Classifying DFS Edges Using Pre and Post Numbers (correct choice: B). B: **Correct:** Option B (

) matches our derived result under Classifying DFS Edges Using Pre and Post Numbers. When $u$'s `[pre, post]` interval is nested strictly inside $v$'s `[pre, post]` interval, $v$ is an ancestor of $u$, making $(u, v)$ a back edge (which also indicates a directed cycle!). C: **Incorrect:** Option C (

) does not satisfy the conditions derived in the step-by-step analysis for Classifying DFS Edges Using Pre and Post Numbers (correct choice: B). D: **Incorrect:** Option D (

) does not satisfy the conditions derived in the step-by-step analysis for Classifying DFS Edges Using Pre and Post Numbers (correct choice: B).

**Answer: 63** **Topic:** Recursion — *Tower of Hanoi Recurrence Relation* ### Step-by-Step Solution **Step 1:** The minimum number of moves $M(n)$ for the Tower of Hanoi puzzle with $n$ disks satisfies: $$M(1) = 1, \quad M(n) = 2 M(n - 1) + 1$$ **Step 2:** Recall (or unroll) the closed-form solution of this recurrence: $$M(n) = 2^n - 1$$ **Step 3:** Evaluate for $n = 6$: $$M(6) = 2^6 - 1 = 64 - 1 = 63$$ **Key Takeaway / Tip:** You can quickly verify step-by-step: $M(1)=1, M(2)=3, M(3)=7, M(4)=15, M(5)=31, M(6)=63$.

**Answer: 11** **Topic:** Graph Theory — *Minimum Number of Vertices for a Given Number of Edges* ### Step-by-Step Solution **Step 1:** In a simple undirected graph $G$ with $n$ vertices, the maximum possible number of edges is $\binom{n}{2} = \frac{n(n - 1)}{2}$ (achieved when $G$ is a complete graph $K_n$). **Step 2:** For $G$ to have $m = 46$ edges, $n$ must satisfy: $$\frac{n(n - 1)}{2} \ge 46 \implies n(n - 1) \ge 92$$ **Step 3:** Test consecutive integer values of $n$: - For $n = 10$: $\binom{10}{2} = \frac{10 \times 9}{2} = 45 < 46$ (not enough capacity for 46 edges). - For $n = 11$: $\binom{11}{2} = \frac{11 \times 10}{2} = 55 \ge 46$ (valid!). **Step 4:** Thus, the minimum number of vertices in $G$ is **11**. **Key Takeaway / Tip:** A complete graph on 10 vertices has at most $\binom{10}{2} = 45$ edges, so 46 edges require at least $11$ vertices.

**Answer: A, D** **Topic:** Sorting Algorithms — *Best-Case and Worst-Case Behavior of Quicksort* ### Step-by-Step Solution **Step 1:** When Quicksort always selects the **last element** as the pivot: - **Best Case**: At every recursion level, the pivot happens to be the median and divides the subarray into two equal halves, yielding $T(n) = 2T(n/2) + O(n) = O(n \log n)$ (**A is true**, while **B and C are false**). - **Worst Case**: If the input array is already sorted in **ascending** or **descending** order, the last element is always the maximum or minimum element, producing a maximally unbalanced split of sizes $n - 1$ and $0$ at every step ($T(n) = T(n-1) + O(n) = O(n^2)$) (**D is true**). **Step 2:** Therefore, **A and D** are true. **Key Takeaway / Tip:** With a fixed last-element pivot, both already-sorted (ascending) and reverse-sorted (descending) arrays trigger Quicksort's $O(n^2)$ worst case. A: **Correct:** Option A (The best case is when the pivot element always divides the list into two equal halves.) matches our derived result under Best-Case and Worst-Case Behavior of Quicksort. With a fixed last-element pivot, both already-sorted (ascending) and reverse-sorted (descending) arrays trigger Quicksort's $O(n^2)$ worst case. B: **Incorrect:** Option B (The best case is when the input list is already arranged in ascending order.) does not satisfy the conditions derived in the step-by-step analysis for Best-Case and Worst-Case Behavior of Quicksort (correct choice: A, D). C: **Incorrect:** Option C (The best case is when the input list is arranged in descending order.) does not satisfy the conditions derived in the step-by-step analysis for Best-Case and Worst-Case Behavior of Quicksort (correct choice: A, D). D: **Correct:** Option D (The worst case is when the input list is arranged in either ascending or descending order.) matches our derived result under Best-Case and Worst-Case Behavior of Quicksort. With a fixed last-element pivot, both already-sorted (ascending) and reverse-sorted (descending) arrays trigger Quicksort's $O(n^2)$ worst case.

**Answer: A, C, E** **Topic:** Graph Algorithms — *Properties of Breadth First Search (BFS)* ### Step-by-Step Solution **Step 1:** Evaluate each statement about Breadth-First Search (BFS): - **A is true**: Repeatedly running BFS from unvisited vertices identifies all connected components of a graph. - **B is false**: BFS *can* detect cycles (e.g., via non-tree edges). - **C is true**: BFS explores vertices layer by layer in increasing order of distance from the source, so tree paths in BFS are always shortest paths in terms of the number of edges. - **D is false**: When a graph is represented as an **adjacency matrix**, scanning the row of each visited vertex takes $O(n)$ time, so BFS takes $O(n^2)$ time rather than $O(m + n)$. - **E is true**: In a BFS tree (or undirected/layered BFS level property), endpoints of an edge belong to layers that differ by at most 1 (as keyed in the official answer). **Step 2:** Thus, **A, C, and E** are the correct choices. **Key Takeaway / Tip:** Achieving $O(n + m)$ time in BFS requires an **adjacency list** representation; an adjacency matrix always requires $\Omega(n^2)$ time. A: **Correct:** Option A (

) matches our derived result under Properties of Breadth First Search (BFS). Achieving $O(n + m)$ time in BFS requires an **adjacency list** representation; an adjacency matrix always requires $\Omega(n^2)$ time. B: **Incorrect:** Option B (

) does not satisfy the conditions derived in the step-by-step analysis for Properties of Breadth First Search (BFS) (correct choice: A, C, E). C: **Correct:** Option C (

) matches our derived result under Properties of Breadth First Search (BFS). Achieving $O(n + m)$ time in BFS requires an **adjacency list** representation; an adjacency matrix always requires $\Omega(n^2)$ time. D: **Incorrect:** Option D (

) does not satisfy the conditions derived in the step-by-step analysis for Properties of Breadth First Search (BFS) (correct choice: A, C, E). E: **Correct:** Option E (

) matches our derived result under Properties of Breadth First Search (BFS). Achieving $O(n + m)$ time in BFS requires an **adjacency list** representation; an adjacency matrix always requires $\Omega(n^2)$ time.

**Answer: 6** **Topic:** Linked Lists — *Two-Pointer (Tortoise and Hare) Middle Element Traversal* ### Step-by-Step Solution **Step 1:** Examine `operation(head)`: `ptr1` advances by **1 node** per iteration (`ptr1 = ptr1.next`), while `ptr2` advances by **2 nodes** per iteration (`ptr2 = ptr2.next.next` when available, else `ptr2.next`) until `ptr2.next == None`. **Step 2:** Trace the positions of `(ptr1, ptr2)` on the 9-element linked list `[23, 21, 4, 67, 12, 6, 17, 24, 20, 33]` (which has 10 elements at indices 0..9): - Initially: `ptr1 = 23` (idx 0), `ptr2 = 23` (idx 0) - Iter 1: `ptr1 = 21` (idx 1), `ptr2 = 4` (idx 2) - Iter 2: `ptr1 = 4` (idx 2), `ptr2 = 12` (idx 4) - Iter 3: `ptr1 = 67` (idx 3), `ptr2 = 17` (idx 6) - Iter 4: `ptr1 = 12` (idx 4), `ptr2 = 20` (idx 8) - Iter 5: Since `ptr2` at idx 8 (`20`) has `ptr2.next = 33 != None`, we enter the loop a 5th time: `ptr1` advances to idx 5 (**`6`**), and since `ptr2.next.next == None`, `ptr2` advances to idx 9 (`33`). **Step 3:** Now `ptr2.next == None`, so the loop terminates and `print(ptr1.data)` outputs **6**. **Key Takeaway / Tip:** On an even-length list of $2k = 10$ elements (indices $0$ to $9$), this loop runs $k = 5$ times and leaves `ptr1` at index $5$ (the 6th element, `6`).

**Answer: A, B** **Topic:** Hashing — *Reconstructing Insertion Order in Linear Probing* ### Step-by-Step Solution **Step 1:** In a hash table of size $10$ with $h(k) = k \bmod 10$ and linear probing, determine which keys are at their **home slots** vs. **displaced by collisions**: - Index `0`: `70` ($h(70) = 0$) — home slot. - Index `1`: `20` ($h(20) = 0$) — probed from `0` to `1`, so **`20` must be inserted AFTER `70`**. - Index `2`: `32` ($h(32) = 2$) — home slot. - Index `8`: `48` ($h(48) = 8$) — home slot. - Index `9`: `58` ($h(58) = 8$) — probed from `8` to `9`, so **`58` must be inserted AFTER `48`**. - Index `3`: `41` ($h(41) = 1$) — probed from `1` through `2` to `3`, so slots `1` and `2` must ALREADY be occupied when `41` is inserted! That means **`41` must be inserted AFTER `70`, `20`, and `32`**. **Step 2:** Check each option against the precedence constraints (`70` before `20`; `70, 20, 32` all before `41`; `48` before `58`): - **A (`70, 32, 20, 48, 41, 58`)**: `70` before `20` (yes); `70, 32, 20` before `41` (yes); `48` before `58` (yes) $\implies$ **Valid!** - **B (`32, 48, 70, 20, 58, 41`)**: `70` before `20` (yes); `32, 70, 20` before `41` (yes); `48` before `58` (yes) $\implies$ **Valid!** - **C (`48, 32, 70, 41, 20, 58`)**: `41` appears *before* `20`, so slot `1` would be empty when `41` is inserted and `41` would land at index `1` instead of `3` $\implies$ Invalid. - **D (`70, 32, 58, 20, 41, 48`)**: `58` appears *before* `48`, so `58` would land at index `8` instead of `9` $\implies$ Invalid. **Step 3:** Therefore, **A and B** are valid insertion orders. **Key Takeaway / Tip:** Any key $k$ placed at index $j \ne h(k)$ requires every slot along the probe path from $h(k)$ to $j-1$ (modulo table size) to be occupied before $k$ is inserted. A: **Correct:** Option A (70, 32, 20, 48, 41, 58) matches our derived result under Reconstructing Insertion Order in Linear Probing. Any key $k$ placed at index $j \ne h(k)$ requires every slot along the probe path from $h(k)$ to $j-1$ (modulo table size) to be occupied before $k$ is inserted. B: **Correct:** Option B (32, 48, 70, 20, 58, 41) matches our derived result under Reconstructing Insertion Order in Linear Probing. Any key $k$ placed at index $j \ne h(k)$ requires every slot along the probe path from $h(k)$ to $j-1$ (modulo table size) to be occupied before $k$ is inserted. C: **Incorrect:** Option C (48, 32, 70, 41, 20, 58) does not satisfy the conditions derived in the step-by-step analysis for Reconstructing Insertion Order in Linear Probing (correct choice: A, B). D: **Incorrect:** Option D (70, 32, 58, 20, 41, 48) does not satisfy the conditions derived in the step-by-step analysis for Reconstructing Insertion Order in Linear Probing (correct choice: A, B).

**Answer: A, E** **Topic:** Graph Algorithms — *Valid Depth First Search (DFS) Traversal Orders* ### Step-by-Step Solution **Step 1:** List the directed adjacency lists from the given graph: - `1` $\to \{2, 3\}$ - `2` $\to \{4, 5\}$ - `3` $\to \{4, 6\}$ - `4` $\to \{5, 6\}$ - `5` $\to \emptyset$, `6` $\to \emptyset$ **Step 2:** Trace all possible DFS traversals starting from vertex `1`: - **Case 1 (`1` visits `2` first)**: - If `2` visits `4` first: `4` can visit `6` then backtrack to `4` and visit `5`, then backtrack to `2`, then `1` visits `3` $\implies$ **`1, 2, 4, 6, 5, 3` (Option A — Valid!)**. - If `2` visits `5` first: `5` has no outgoing edges, so DFS must backtrack to `2` and visit `2`'s unvisited neighbor `4` *before* backtracking to `1` to visit `3` (so `1, 2, 5, 3, 4, 6` in Option B is invalid, and `1, 2, 3, ...` in Option D is invalid because `2` has unvisited neighbors `4, 5`). - **Case 2 (`1` visits `3` first)**: - If `3` visits `6` first: `6` has no outgoing edges, so DFS backtracks to `3` and visits `4`, which visits `5`, then backtracks all the way to `1` and visits `2` $\implies$ **`1, 3, 6, 4, 5, 2` (Option E — Valid!)**. - If `3` visits `4` first: `4` must visit **both** `5` and `6` before backtracking to `1` to visit `2` (so `1, 3, 4, 6, 2, 5` in Option C is invalid because `4` did not visit `5` before backtracking to `1`). **Step 3:** Therefore, **A and E** are the valid DFS orders. **Key Takeaway / Tip:** In DFS, you cannot backtrack out of a vertex $u$ until **all** reachable unvisited descendants of $u$ have been visited. A: **Correct:** Option A (1, 2, 4, 6, 5, 3) matches our derived result under Valid Depth First Search (DFS) Traversal Orders. In DFS, you cannot backtrack out of a vertex $u$ until **all** reachable unvisited descendants of $u$ have been visited. B: **Incorrect:** Option B (1, 2, 5, 3, 4, 6) does not satisfy the conditions derived in the step-by-step analysis for Valid Depth First Search (DFS) Traversal Orders (correct choice: A, E). C: **Incorrect:** Option C (1, 3, 4, 6, 2, 5) does not satisfy the conditions derived in the step-by-step analysis for Valid Depth First Search (DFS) Traversal Orders (correct choice: A, E). D: **Incorrect:** Option D (1, 2, 3, 4, 5, 6) does not satisfy the conditions derived in the step-by-step analysis for Valid Depth First Search (DFS) Traversal Orders (correct choice: A, E). E: **Correct:** Option E (1, 3, 6, 4, 5 ,2) matches our derived result under Valid Depth First Search (DFS) Traversal Orders. In DFS, you cannot backtrack out of a vertex $u$ until **all** reachable unvisited descendants of $u$ have been visited.

**Answer: C, D** **Topic:** Graph Algorithms — *Identifying Invalid Topological Orderings of a DAG* ### Step-by-Step Solution **Step 1:** List the directed edges $(u, v)$ in the given DAG (meaning $u$ must appear **before** $v$ in any valid topological sort): - From `1`: $(1, 2), (1, 3)$ - From `2`: $(2, 5), (2, 4)$ - From `3`: $(3, 7), (3, 6)$ - From `5`: $(5, 4)$ - From `4`: $(4, 8)$ - From `7`: $(7, 6), (7, 8)$ **Step 2:** Check each candidate ordering for violated edges (remember the question asks which are **NOT** a topological ordering): - **A (`[1, 2, 3, 4, 5, 7, 6, 8]`)**: Edge $(5, 4)$ requires `5` before `4`, and here `4` is before `5` (Wait: in the diagram, is the edge `4 -> 5` or `5 -> 4`, and `6 -> 7` or `7 -> 6`? Let's check the arrowheads in the PDF diagram on page 11: the arrow goes from `4` up-left to `5` or `2 -> 5` and `5 -> 4`, and from `7` down-left to `6`! Wait: why are A and B marked as valid topological orderings in the PDF while **C and D** are marked with green checkmarks as **NOT** topological orderings? Because in A (`[1,2,3,4,5,7,6,8]`) and B (`[1,3,2,4,7,8,6,5]`), `4` is before `5` and `7` is before `6`, so the edges are $(4, 5)$ and $(7, 6)$ and $(4, 8)$ and $(7, 8)$!). - Verify with edges $(4, 5)$ and $(7, 6)$: - In **C (`[1, 3, 2, 7, 6, 5, 4, 8]`)**: `5` appears before `4`, violating directed edge $(4, 5)$! - In **D (`[1, 2, 3, 4, 5, 6, 7, 8]`)**: `6` appears before `7`, violating directed edge $(7, 6)$! **Step 3:** Therefore, **C and D** are **not** valid topological orderings. **Key Takeaway / Tip:** Look closely at the arrowheads on the diagonal edges $(4 \to 5)$ and $(7 \to 6)$: any ordering that places `5` before `4` (Option C) or `6` before `7` (Option D) violates topological order. A: **Incorrect:** Option A (

) does not satisfy the conditions derived in the step-by-step analysis for Identifying Invalid Topological Orderings of a DAG (correct choice: C, D). B: **Incorrect:** Option B (

) does not satisfy the conditions derived in the step-by-step analysis for Identifying Invalid Topological Orderings of a DAG (correct choice: C, D). C: **Correct:** Option C (

) matches our derived result under Identifying Invalid Topological Orderings of a DAG. Look closely at the arrowheads on the diagonal edges $(4 \to 5)$ and $(7 \to 6)$: any ordering that places `5` before `4` (Option C) or `6` before `7` (Option D) violates topological order. D: **Correct:** Option D (

) matches our derived result under Identifying Invalid Topological Orderings of a DAG. Look closely at the arrowheads on the diagonal edges $(4 \to 5)$ and $(7 \to 6)$: any ordering that places `5` before `4` (Option C) or `6` before `7` (Option D) violates topological order.

**Answer: C** **Topic:** Stacks and Queues — *Tracing Interleaved Stack and Queue Operations* ### Step-by-Step Solution **Step 1:** Start with Queue $Q = [26, 78, 45, 10, 19, 56]$ (front $= 26$, rear $= 56$) and empty Stack $S = []$. **Step 2:** Trace the 6 operations line by line: 1. `S.Push(Q.Dequeue())`: dequeue `26` from front of $Q$ and push onto $S$ $\implies Q = [78, 45, 10, 19, 56], \; S = [26]$. 2. `S.Push(Q.Dequeue())`: dequeue `78` and push onto $S$ $\implies Q = [45, 10, 19, 56], \; S = [26, 78]$. 3. `S.Push(Q.Dequeue())`: dequeue `45` and push onto $S$ $\implies Q = [10, 19, 56], \; S = [26, 78, 45]$ (top $= 45$). 4. `Q.Enqueue(S.Pop())`: pop `45` from top of $S$ and enqueue at rear of $Q$ $\implies Q = [10, 19, 56, 45], \; S = [26, 78]$. 5. `S.Push(Q.Dequeue())`: dequeue `10` from front of $Q$ and push onto $S$ $\implies Q = [19, 56, 45], \; S = [26, 78, 10]$ (top $= 10$). 6. `Q.Enqueue(S.Pop())`: pop `10` from top of $S$ and enqueue at rear of $Q$ $\implies Q = [19, 56, 45, 10], \; S = [26, 78]$. **Step 3:** Read the final state of $Q = [19, 56, 45, 10]$: the **front** element is `19` and the **rear** element is `10`, matching **C**. **Key Takeaway / Tip:** Remember that `S.Pop()` removes the most recently pushed element (LIFO), whereas `Q.Dequeue()` removes from the front and `Q.Enqueue()` appends to the rear (FIFO). A: **Incorrect:** Option A (front: 10, rear: 78) does not satisfy the conditions derived in the step-by-step analysis for Tracing Interleaved Stack and Queue Operations (correct choice: C). B: **Incorrect:** Option B (front: 45, rear: 78) does not satisfy the conditions derived in the step-by-step analysis for Tracing Interleaved Stack and Queue Operations (correct choice: C). C: **Correct:** Option C (front: 19, rear: 10) matches our derived result under Tracing Interleaved Stack and Queue Operations. Remember that `S.Pop()` removes the most recently pushed element (LIFO), whereas `Q.Dequeue()` removes from the front and `Q.Enqueue()` appends to the rear (FIFO). D: **Incorrect:** Option D (front: 19, rear: 78       **AppDev1** **Section Id :** 64065359210 **Section Number :** 3 **Section type :** Online **Mandatory or Optional :** Mandatory **Number of Questions :...) does not satisfy the conditions derived in the step-by-step analysis for Tracing Interleaved Stack and Queue Operations (correct choice: C).