Midterm Challenge

Comprehensive Assessment covering Modules 1-6.
Part 1: 70 Multiple Choice Questions (Analysis, Brute Force, Divide & Conquer).
Part 2: 10 Concept Essay Questions.

Part 1: The Gauntlet (70 MCQs)

Question 1/70 Score: 0

Topic: General

Part 2: The Concept Vault (Essays)

1. Algorithm Characteristics

Mod 1

List and briefly explain the 5 essential characteristics of an algorithm. Distinguish between an Algorithm and a Program.

Characteristics: Input (0+), Output (1+), Definiteness (Clear steps), Finiteness (Must terminate), Effectiveness (Feasible).
Difference: An algorithm MUST terminate (Finiteness). A program (like an OS) may run indefinitely (infinite loop).

2. Asymptotic Notations

Mod 2

Explain the difference between $O$, $\Omega$, and $\Theta$. Why is $\Theta(n)$ preferred over $O(n)$ when describing an algorithm's exact behavior?

$O$ is Upper Bound (Worst case limit). $\Omega$ is Lower Bound (Best case limit). $\Theta$ is Tight Bound (Sandwiched between constants). $\Theta$ is preferred because it gives a precise growth rate, whereas $O(n^2)$ is technically true for a linear algorithm but misleading.

3. Brute Force Sorting

Mod 3

Compare Selection Sort and Bubble Sort. Both are $O(n^2)$, but why might Selection Sort be preferred in a system where writing to memory is expensive?

Selection Sort performs exactly $O(n)$ swaps (writes) in the worst case. Bubble Sort performs $O(n^2)$ swaps. If write operations are costly (e.g., Flash memory), Selection Sort is superior despite having the same time complexity.

4. DFS vs BFS

Mod 3

Describe the data structures used for DFS and BFS. How does the choice of Adjacency Matrix vs. Adjacency List affect their complexity?

DFS uses a Stack (LIFO). BFS uses a Queue (FIFO).
Matrix: $O(|V|^2)$ because finding neighbors requires scanning a whole row.
List: $O(|V| + |E|)$ because we only traverse existing edges.

5. Decrease-and-Conquer Types

Mod 4

Differentiate between "Decrease by Constant" and "Decrease by Factor". Give one algorithm example for each.

Constant: Reduces size by 1 (or k). Recurrence $T(n) = T(n-1) + 1 \to O(n)$. Ex: Insertion Sort, DFS.
Factor: Reduces size by half (or n/k). Recurrence $T(n) = T(n/2) + 1 \to O(\log n)$. Ex: Binary Search.

6. Topological Sort

Mod 4

What condition must a graph satisfy to be topologically sorted? Explain the "Source Removal" method.

The graph must be a DAG (Directed Acyclic Graph). If it has a cycle, no order exists. Source Removal method: Identify a node with in-degree 0, print it, remove it and its edges, repeat.

7. Master Theorem

Mod 5

Given $T(n) = 2T(n/2) + n$, apply the Master Theorem to find the complexity. What algorithm does this recurrence represent?

$a=2, b=2, d=1$. Compare $a$ vs $b^d \to 2$ vs $2^1$. Since equal, Case 2 applies: $O(n^d \log n) = O(n \log n)$. This represents Mergesort (and best-case QuickSort).

8. QuickSort Worst Case

Mod 5

Under what specific conditions does QuickSort perform in $O(n^2)$? How can we mitigate this?

Occurs when the pivot is the smallest or largest element every time (e.g., sorted array with first element as pivot). Splits into 0 and n-1. Mitigation: Pick random pivot, or median-of-three.

9. Presorting Benefits

Mod 6

"Presorting makes everything faster." Critically evaluate this statement. When is it true, and when is it false?

False. It has overhead. Total cost = Sort ($n \log n$) + Search.
True if you search many times (amortized cost) or if brute force is $O(n^2)$ (e.g., uniqueness).
False if searching once (Linear search $O(n)$ < Sorting $n \log n$).

10. AVL Rotations