The first midterm will be held in class, Feb. 14, 2018. The test will be closed book. It will cover material on Assignments 0 through 4.

Sample questions

Here are some sample questions from previous midterms and finals. There are solutions available. You are strongly recommended to work through the problems on your own before looking at the solutions.

1. Prove the following asymptotic bounds:

• ∀ a>1 an ∈ O(nᵃ)
• ∀ a>0, b > 0, nᵃ+nᵇ ∈ O(nᶜ) where c=a+b

2. Solve the recurrence T(n) ≤ 3T(n/4) + O(sqrt(n))

3. Suppose T(n) = T(n/2) + log₂(n). Use substitution (induction) to show

    T(n) ∈ O((log₂ n)²)

4. Consider the following recursive algorithm to append two arrays.

    function Append(A[̣1…k], B[1…l])
        if k = 0 return B
        if l = 0 return A
        C = Append(A[1 . . . k], B[1 . . . l − 1])
        return C ◦ B[l]
    end function

The symbol ◦ represents the operation of appending one element to an array. Analyze this algorithm under the assumption that for an array S of size p and element e, the cost of computing S ◦ e is

• Θ(1)
• Θ(p)

5. Suppose that Unlucky Pete has probability p of passing STAT1001, no matter how many times he has taken it before. Let N be the random variable that counts the total number of times Pete takes STAT1001.

• Express N as a sum of indicator random variables.
• Use this sum to compute the expected value of N .

6. Compute the expected running time of the following algorithm

    function MAX (A[1 … n])
    repeat
        p ← random integer from 1 to n
        j ← 0
        for i = 1 . . . n do
        if A[i] ≥ A[p] then
            j ← j +1
        end if
    end for
    until j = 1
    return A[p]
    end function

7. Solve the following recurrences

• T(n) = T(n-1) + nᶜ
• T(n) = T(n-1) + cⁿ

Extra recurrence exercises

7. Solve the following recurrences. Solutions are here.

• T(n) = sqrt(n) T(sqrt(n)) + n
• T(n) = T(3n/4) +n
• T(n) = 2T(n/2) + n/(log n)
• T(n) = 4T(n/2) + n log n