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`