UNB/ CS/ David Bremner/ teaching/ cs3383/ tests/ Class Test 1

The first midterm will be held in class, October 19, 2016. The test will be closed book.

Here are some sample questions from previous midterms. There are solutions available. Note that these are currently practice questions from last year, and the topics are subject to change.

1. Prove the following asymptotic bounds:

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

3. 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

4. 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.

5. 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

6. Suppose the President of UNB (uniformly) randomly shuffles the offices of all of the professors. Use indicator variables and linearity of expectation to compute the expected number of professors that stay in their current office.

7. Solve the following recurrences

8. Solve the following recurrences. Solutions are here.