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:

- ∀ 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.** 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)

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

- Express
`N`

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

.

**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

`T(n) = T(n-1) + nᶜ`

`T(n) = T(n-1) + cⁿ`

**8.** 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`