CSCI 3650
Summer 2000
Practice questions for exam 1
You will have 90 minutes for the exam, and can bring one sheet
of prepared notes, writing on both sides of the paper.
To within a constant factor, what is the solution to
the following recurrence? Assume that T(n) is bounded by a constant
for small values of n.
T(n) = 9T(n/4) + O(n)
Let f(n) = n3log2(n) and
g(n) = n2(log2(n))3. Is f(n) O(g(n))?
Is g(n) O(f(n))?
Justify your answer.
A particular divide-and-conquer algorithm, when run on an
input of size n, works by spending O(n) time splitting the
problem into three roughly equal size parts,
then does a recursive call on each of the three parts, then
spends O(n) time combining the solutions to the recursive
calls. On small inputs, the algorithm takes a constant amount
of time. To within a constant factor, how long does this algorithm
take, in terms of n?
You have a list of n different numbers
x1, x2, ..., xn,
in an arbitrary order,
and also a value k < n. You would
like an algorithm that prints the smallest k values in the list,
in any order. For example, if k = 3, you are asked to print the
smallest 3 of x1, x2, ..., xn.
Describe an algorithm that solves this problem in time O(n),
independent of the value of k.
You have an unsorted array of size n. You need to search for
k different values in the array. You consider two strategies.
Do k linear searches, searching the entire array for each value.
Sort the array using mergesort, and then do k binary searches.
(A binary search in a sorted array of size n takes time O(log n).)
To within a constant factor, how large should k be before method
(b) is faster than method (a)?