CSCI 3110 Practice Midterm 1 4.10.2019
Topics: Asymptotic notation, recurrence relations, divide-and-conquer, greedy algo-
rithms, dynamic programming
1. (2 marks) Circle the true statements:
(a) lg 3n = o(log 32n)
(b) n4 = O(23 lgn)
(c)
(n
2
)
= Θ(n2)
(d) (n mod 3)n = Ω(2n)
(e) (lg n)! = ω(log n!)
(Note that lg(lg n)! = Ω(log n log logn) but lg lg n! = O(log n).)
2. (2 marks) Recall that the recurrence for Strassen’s Algorithm is T (n) = 7T (n/2) + 8n2.
According to the version of the Master Theorem in Introduction to Algorithms (on the reverse
of this sheet), what is the complexity of this algorithm? Write your answer in Theta-notation
(so use formulas in exponents rather than rounding).
Solution: T (n) = Θ(nlog2 7)
3. (2 marks) Suppose you are given an unsorted array A[1..n] of positive numbers and an integer
k and you want to find the number that would appear kth if A were sorted. For example,
if A = [3, 7, 7, 1, 8, 3] and k = 5 then the answer is 7 because sorting A produces the array
[1, 3, 3, 7, 7, 8] in which the 4th number is 7. How can you modify QuickSort to solve this
problem in O(n) expected time? You can assume the expected number of times you pseudo-
randomly choose a pivot from a subarray before finding one that divides it roughly in half is
O(1), and you need neither prove your algorithm correct nor give an analysis.
(Hint: In the example, if you choose A[6] = 3 as the pivot and see that 3 numbers are less
than or equal to A[6] and 3 are greater, then how do you recurse? What if you choose A[5] = 8
as the pivot?)
Solution: Pseudo-randomly choose a pivot A[i] and create arrays AL and AR containing
all the numbers in A less than or equal to A[i] and all the numbers in A greater than A[i],
respectively. If |AL| ≥ k then recurse on AL with the same value of k; if |AL| < k then recurse
on recurse on AR with the value k − |AL|.
4. (2 marks) Suppose you are given an unsorted array A[1..n] of positive integers and you want to
find a subsequence whose sum is as large as possible under the restriction that the numbers
in it alternate between even and odd (starting with either an even or an odd). Give an
O(n)-time algorithm to solve this problem. You need not prove your algorithm correct.
Solution: Consider A as consisting of non-empty blocks of numbers such that each block
contains either only even numbers or only odd numbers and the kinds of number alternate
between blocks and, from each block, choose the largest number in the block.
(To see why this is correct — although you don’t have to give a proof! — assume there’s an
optimal solution S that extends our subsolution containing the largest numbers from the first
i blocks. Either S also contains the largest number from the (i + 1)st block or it contains
another number from that block — in which case we can swap it with the largest and increase
the sum — or it skips some even number of blocks starting with the (i+ 1)st — in which case
we can add the largest numbers from the skipped blocks and increase the sum.)
5. (2 marks) Suppose you are given an unsorted array A[1..n] of positive integers and you want to
find a subsequence whose sum is as large as possible under the restriction that, for 1 ≤ i ≤ n,
you can include A[i] in the subsequence if and only if you exclude A[max(i−A[i], 1)], . . . , A[i−
1]. Give an O(n)-time algorithm to solve this problem. You need not prove your algorithm
correct.
Solution: We fill a one-dimensional dynamic-programming matrix M [0..n] in O(n) time
using the recurrence
M [0] = 0
M [i] = max(M [i−A[i]− 1] + A[i],M [i− 1])
— so M [i] is the maximum sum we can obtain with a subsequence of A[1..i] — and then walk
back through the matrix to recover the actual subsequence, again in O(n) time.
(To see why this is correct, notice that if the max-sum subsequence for A[1..i] includes A[i]
then M [i] = M [i−A[i]− 1] +A[i]; otherwise, M [i] = M [i− 1]. Again, you don’t have to give
a proof!)