Midterm Exam Solutions (Q1–Q7)

A prime number is an integer strictly greater than 1 that has exactly two positive divisors: 1 and itself.

An integer greater than 1 with three or more positive divisors is a composite number. The number 1 is neither prime nor composite.

Test each integer $p$ from $2$ to $n$ against all potential divisors $i \in [2, p - 1]$:

BruteForcePrimes(n):
    // Input: Integer n >= 2
    // Output: List L of prime numbers <= n
    L = empty list
    for p = 2 to n do:
        isPrime = 1
        for i = 2 to p - 1 do:
            if p mod i == 0 then:
                isPrime = 0
                break
        if isPrime == 1 then:
            L.append(p)
    return L

• Time Complexity: $\Theta(n^2)$ because in the worst case (when $p$ is prime), the inner loop runs $p - 2$ times: $$\sum_{p=2}^n (p - 2) = \frac{(n-2)(n-1)}{2} = \Theta(n^2)$$
• Square-Root Optimization: Only testing divisors up to $\lfloor \sqrt{p} \rfloor$ improves running time to $\Theta(n \sqrt{n})$:

  for i = 2 to floor(sqrt(p)) do:
      if p mod i == 0 then:
          isPrime = 0
          break

SieveOfEratosthenes(n):
    // Input: Integer n >= 2
    // Output: List L of prime numbers <= n
    create array A[2..n]
    for p = 2 to n do A[p] = p

    for p = 2 to floor(sqrt(n)) do:
        if A[p] != 0 then:
            j = p * p
            while j <= n do:
                A[j] = 0
                j = j + p

    L = empty list
    for p = 2 to n do:
        if A[p] != 0 then:
            L.append(A[p])
    return L

• Why start crossing out at $p^2$? Any composite multiple $k \cdot p$ where $k < p$ has already been crossed out when processing the smaller prime factor of $k$.
• Time Complexity: $\Theta(n \log \log n)$.
• Space Complexity: $\Theta(n)$ for array $A[2..n]$.

The outer loop runs for $i = 1, 2, \dots, n$. For each $i$, the inner loop executes $i$ times:

Answer: $\mathbf{\Theta(n^2)}$

The three indices satisfy $0 \le i < j < k < n$, so count++ executes exactly once per unordered triple drawn from $n$ values:

Answer: $\mathbf{\Theta(n^3)}$

• The outer loop executes $n$ times ($i = 0$ to $n - 1$).
• The inner loop has an upper bound of $n^2$, running $n^2 - (i + 1) \approx n^2$ times for each $i$:

Answer: $\mathbf{\Theta(n^3)}$

Examine each inner block inside the outer loop $i$:

1. for (j = 0; j < n; j++): executes $n$ times $\implies \Theta(n)$.
2. for (j = 2; j <= n; j = j * j): $j$ squares at each step: $2, 4, 16, 256, \dots, 2^{2^t} \le n \implies t \le \log_2(\log_2 n)$. This inner loop executes $\Theta(\log \log n)$ times. Enclosed in loop $k$ running $n$ times: $n \times \Theta(\log \log n) = \Theta(n \log \log n)$.
3. for (m = 0; m < n; m++): executes $n$ times $\implies \Theta(n)$.

Total work inside outer loop $i$:

Multiplied by outer loop $i$ running $n$ times:

(Note: If the inner step is multiplicative $j \leftarrow j \times 5$, it executes in $\Theta(\log n)$ steps, yielding $\mathbf{\Theta(n^2 \log n)}$).

Answer: $\mathbf{\Theta(n^2 \log \log n)}$ (or $\mathbf{\Theta(n^2 \log n)}$)

The inner loop bound is constant: $j$ iterates from $2$ to $7$, which is exactly $6$ operations regardless of $n$:

Answer: $\mathbf{\Theta(n)}$

For every single iteration of the outer loop $i$, either the if branch or the else branch is taken. Both branches contain a loop running from $0$ to $n-1$, which executes exactly $n$ operations:

Total operations across all $n$ outer iterations:

Answer: $\mathbf{\Theta(n^2)}$

The inner loop repeatedly halves $j$: $n, n/2, n/4, \dots, 1$. The number of divisions until $j < 1$ is $\lfloor \log_2 n \rfloor + 1 = \Theta(\log n)$. Outer loop runs $n$ times:

Answer: $\mathbf{\Theta(n \log n)}$

The Tower of Hanoi consists of three pegs (Source, Auxiliary, Destination) and $n$ disks of distinct sizes initially stacked on the source peg in decreasing order of size.

• Goal: Transfer all $n$ disks from the source peg to the destination peg.
• Constraints:
  1. Only one disk may be moved at a time.
  2. Only the top disk on any peg can be moved.
  3. No larger disk may be placed on top of a smaller disk.

For $n = 4$, the minimum number of moves is $2^4 - 1 = 15$ moves. Let Peg 1 be Source, Peg 2 be Auxiliary, and Peg 3 be Destination:

Final state: all 4 disks are stacked correctly on Destination Peg 3.

Hanoi(n, source, destination, auxiliary):
    if n == 1 then:
        move disk 1 from source to destination
        return

    Hanoi(n - 1, source, auxiliary, destination)
    move disk n from source to destination
    Hanoi(n - 1, auxiliary, destination, source)

• Recurrence Relation: $$T(n) = 2T(n - 1) + 1 \quad \text{for } n > 1, \quad T(1) = 1$$
• Closed Form: $T(n) = 2^n - 1$ moves.
• Time Complexity: $\Theta(2^n)$.
• Space Complexity: $\Theta(n)$ (maximum recursion call stack depth).

Let text $T$ have length $n$ and pattern $P$ have length $m \le n$:

BruteForceSearch(T, P):
    n = length(T)
    m = length(P)
    for i = 0 to n - m do:
        j = 0
        while j < m and T[i + j] == P[j] do:
            j = j + 1
        if j == m return i
    return -1

• Worst-Case Time Complexity: $\Theta(n \cdot m)$ (e.g., $T = \text{"AAAAAAAAAB"}$, $P = \text{"AAB"}$).
• Best-Case Time Complexity: $\Theta(n)$ (when the first character of $P$ immediately mismatches).
• Space Complexity: $\Theta(1)$ auxiliary space.

Let board $D$ have $R$ rows and $C$ columns, and pattern $P$ have length $m$:

function search2D(board, P) {
    const R = board.length;
    const C = board[0].length;
    const m = P.length;

    for (let r = 0; r < R; r++) {
        for (let c = 0; c < C; c++) {
            // 1. Horizontal Search (Left to Right)
            if (c + m <= C) {
                let j = 0;
                while (j < m && board[r][c + j] === P[j]) {
                    j++;
                }
                if (j === m) console.log(`Found horizontally at (${r}, ${c})`);
            }

            // 2. Vertical Search (Top to Bottom)
            if (r + m <= R) {
                let j = 0;
                while (j < m && board[r + j][c] === P[j]) {
                    j++;
                }
                if (j === m) console.log(`Found vertically at (${r}, ${c})`);
            }
        }
    }
}

• Time Complexity: For an $R \times C$ board, each of the $R \cdot C$ cells performs at most $2m$ comparisons, giving $\mathbf{\Theta(R \cdot C \cdot m)}$.
• For an $n \times n$ square board, the complexity is $\mathbf{\Theta(n^2 \cdot m)}$.

Each person must be assigned to exactly one job, and each job assigned to exactly one person. Exhaustive search enumerates all $4! = 24$ permutations and keeps the cheapest.

Minimum-cost assignment:

This is the unique optimum. Two runner-up permutations cost $25$ and are the ones most often stopped at when the enumeration tree is pruned by eye rather than completed:

1. $A \to J_4 (3) + B \to J_3 (3) + C \to J_2 (9) + D \to J_1 (10) = 25$
2. $A \to J_4 (3) + B \to J_3 (3) + C \to J_1 (7) + D \to J_2 (12) = 25$

Both fix $A \to J_4$ and $B \to J_3$ because those are each row’s cheapest cell, but the greedy row-wise choice is not optimal here: paying $6$ instead of $3$ for $B$ frees $J_3$ for $D$, whose alternatives are all far more expensive.

Time Complexity: Generating and evaluating all permutations takes $\mathbf{\Theta(n!)}$.

ClosestPairBruteForce(P):
    // Input: Array P of n points (x_i, y_i)
    // Output: Indices of closest pair and distance
    dmin = infinity
    index1 = null; index2 = null

    for i = 0 to n - 2 do:
        for j = i + 1 to n - 1 do:
            d = sqrt((P[i].x - P[j].x)^2 + (P[i].y - P[j].y)^2)
            if d < dmin then:
                dmin = d
                index1 = i
                index2 = j

    return index1, index2, dmin

• Time Complexity: Computes Euclidean distance for all $\frac{n(n - 1)}{2}$ pairs $\implies \mathbf{\Theta(n^2)}$.
• Space Complexity: $\Theta(1)$ auxiliary space.

1. Step 1 (Divide): Sort all points by $x$-coordinate. Divide the set into two equal subsets $P_L$ and $P_R$ using a vertical line $x = m$.
2. Step 2 (Conquer): Recursively compute the minimum pairwise distance in the left half ($d_L$) and right half ($d_R$). Set $d = \min(d_L, d_R)$.
3. Step 3 (Combine): Check for points spanning across the dividing line:
   • Construct a vertical strip of width $2d$ ($m - d \le x \le m + d$).
   • Sort the strip points by $y$-coordinate.
   • For each point in the strip, inspect only subsequent points whose $y$-difference is strictly less than $d$. Geometrically, at most 6 points can fit in this region without violating the minimum distance condition.
4. Recurrence & Complexity: $$T(n) = 2T(n / 2) + \Theta(n)$$ By the Master Theorem, the time complexity is $\mathbf{\Theta(n \log n)}$, improving upon the $\Theta(n^2)$ brute-force approach.

Let $m = 2$:

• $A = 2134 \implies a_1 = 21, \ a_0 = 34$
• $B = 5687 \implies b_1 = 56, \ b_0 = 87$

Step 1: Compute $c_2$

Step 2: Compute $c_0$

Step 3: Compute $c_1$

Step 4: Combine the Results

1. Division into Subproblems: The integers of $n$ digits are divided into high and low halves of $n/2$ digits ($a_1, a_0$ and $b_1, b_0$).
2. Number of Subproblems: Traditional multiplication requires 4 subproblems ($a_1 b_1, a_1 b_0, a_0 b_1, a_0 b_0$). Karatsuba’s formula computes $c_1$ using only one additional product $(a_1 + a_0)(b_1 + b_0)$ and linear additions/subtractions, reducing the count to 3 recursive subproblems.
3. Recurrence Relation: $$T(n) = 3T(n / 2) + \Theta(n)$$
4. Time Complexity: By the Master Theorem ($a = 3, b = 2, d = 1$, since $a > b^d = 2^1$): $$T(n) \in \Theta(n^{\log_2 3}) \approx \mathbf{\Theta(n^{1.585})}$$ This is asymptotically superior to the $\Theta(n^2)$ pencil-and-paper algorithm.