Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CIT 596
Midterm 1 Practice Problems
These problems are meant to help you prepare for the first midterm. They may not all be reflective
of the difficulty of the problems on the exam.
1. Solve each of the recurrences below and express T (n) in asymptotic notation. State the
method used to derive answer. In each case assume that T (1) = 1.
(a) T (n) = T (3n/4) + T (n/4) + n.
(b) T (n) = 6T (n/2) + n3.
(c) T (n) = T (n/2) + log n.
2. Let A and B be two arrays (not necessarily sorted) containing n elements each. Suppose we
are given a target T . Describe an O(n log n) algorithm to determine if there are elements A[i]
and B[j] that add up to T .
3. Suppose we have an array of numbers a1, . . . , an with the property that successive entries of
the array differ by at most 2. In other words |ai − ai+1| ≤ 2. In addition we are told that a1
is negative and an is positive.
(a) Prove that at least one of 0 and 1 must be present in the array.
(b) Design an efficient algorithm to determine the index at which 0 or 1 occurs. (If there
are multiple occurrences of 0 or 1 you just have to find one.)
4. Use the comparison-tree model to find an exact (not asymptotic) lower bound on the number
of comparisons required to merge a sorted list of n elements with a sorted list of 2 elements.
5. Recall that a modal element in an array of n elements is an element that appears more than
n/2 times. Suppose you are given an array containing a modal element. Design a simple
randomized algorithm to determine the modal element that runs in expected O(n) time.
6. Let A[1..n] be an array of n positive integers. For any 1 ≤ i ≤ j ≤ n, define
f(i, j) =
j∑
k=i
A[k].
(a) Describe an O(n)-time algorithm that creates a data structure such that, for any 1 ≤
i ≤ j ≤ n, f(i, j) can be evaluated in constant time using this data structure. Justify
your answer.
Midterm CIT 596 2
(b) Describe an algorithm that on input A[1..n] and a number K, determines whether there
exists a pair (i, j) such that f(i, j) = K. Your algorithm should run in time o(n2). (Note
that this is little “o”.)
7. For an odd number of n distinct elements x1, x2, . . . , xn with positive weights w1, w2, . . . , wn
such that
∑n
i=1wi = 1, the weighted median is the element xk satisfying:
k−1∑
i=1
wi < 1/2 and
n∑
i=k+1
wi ≤ 1/2
(a) Show how to compute the weighted median of n elements in O(n log n) worst-case time
using sorting. No proof of correctness is needed.
(b) Show how to compute the weighted median in O(n) worst-case time using the linear-
time median-finding algorithm covered in class. You can use results from class without
proof, and no proof of correctness is needed for this part.
8. Suppose we want to maintain a balanced binary search tree that handles the usual dictionary
operations of insert, delete, and find. In addition, we want to answer interval queries of
the following form: Given an integer a, output the number of elements in the tree, that are
greater than or equal to a. (Note that a itself may or may not occur in the tree.) How would
you modify the tree to answer these questions efficiently? Design and analyze the algorithm
for handling an interval query. Show that you can maintain this modified binary search tree
as you insert and delete elements into it and rotate it to rebalance the tree.
9. In a min heap we want to answer the following query: Given k and x, is the kth-smallest
element in the heap less than x? Design a O(k) algorithm for solving this problem. Prove
that your algorithm is correct and analyze its running time.
10. Give short answers to the following questions:
(a) To use hashing when we want to be able to insert and delete elements, what is the best
collision resolution scheme?
(b) Define an indicator random variable.
(c) The best divide-and-conquer algorithm for the maximum-sum-subinterval selection prob-
lem takes time Θ(n log n). Does it follow that a lower bound for this problem is
Ω(n log n). Justify your answer.
(d) Suppose we are doing QuickSelect where we are searching for the 100th-smallest element
in an array. What is the probability that the smallest element is compared to the second
smallest element?