Description

Name: NetID:
Instructions
1. Do not forget to write your name and NetID above, and to sign Rutgers honor pledge below.
2. The exam contains 5 problems worth 100 points in total plus one extra credit problem worth 10 points.
1 20
2 20
3 20
4 20
5 20
6 +10
Total 100 + 10
Problem. # Points Score
The only exception to this rule is the extra credit problem: you do not get any credit for leaving the extra credit problem blank, and it is harder to get partial credit on that problem.

Rutgers honor pledge: Please sign the Rutgers honor pledge below.
On my honor, I have neither received nor given any unauthorized assistance on this examination.
Signature:
Problem 1.
(a) Determine the strongest asymptotic relation between the functions
f(n) = plogn and ,
i.e., whether f(n) = o(g(n)), f(n) = O(g(n)), f(n) = Ω(g(n)), f(n) = ω(g(n)), or f(n) = Θ(g(n)).
Remember to prove the correctness of your choice. (10 points)
(b) Use the recursion tree method to solve the following recurrence T(n) by finding the tightest function f(n) such that T(n) = O(f(n)): (10 points)
T(n) ≤ 8 · T(n/2) + O(n3).
(You do not have to prove that your function is the tightest one.)
Problem 2. Consider the algorithm below for finding the total sum of the numbers in any array A[1 : n].
TOTAL-SUM(A[1 : n]):
1. If n = 0: return 0.
2. If n = 1: return A[1].
3. Otherwise, let m1 ← TOTAL-SUM ]) and m2 ← TOTAL-SUM
4. Return m1 + m2.
We analyze TOTAL-SUM in this question.
(a) Use induction to prove the correctness of this algorithm. (10 points)
(b) Write a recurrence for this algorithm and solve it to obtain a tight upper bound on the worst caseruntime of this algorithm. You can use any method you like for solving this recurrence. (10 points)
Problem 3. You are given a collection of n integers a1,…,an with positive weights w1,…,wn. For any number ai, we define the bias of ai as:
bias(ai) = | X wj − X wk|;
j:aj<ai k:ak≥ai
i.e., the absolute value of the difference between the weights of elements smaller than ai and the remaining ones. Design and analyze an algorithm that in O(nlogn) time finds the element that has the smallest bias.
You can assume that the input is given in two arrays A[1 : n] and W[1 : n] where ai = A[i] and wi = W[i].
Examples:
• When n = 5, and A = [1,5,3,2,7] and W = [3,6,2,8,9], the smallest biased element is a2 = A[2] = 5 with bias(a2) = |(3 + 2 + 8) − (6 + 9)| = 2.
• When n = 5, and A = [1,2,3,4,5] and W = [8,6,5,2,6], the smallest biased element is a3 = A[3] = 3 with bias(a3) = |(8 + 6) − (5 + 2 + 6)| = 1.
(a) Algorithm: (7 points)
(b) Proof of Correctness: (10 points) (c) Runtime Analysis: (3 points) Problem 4. You are given three arrays A[1 : n], B[1 : n], and C[1 : n] of positive integers. The goal is to decide whether or not there are indices i,j,k ∈ [1 : n] such that A[i] · B[j] = C[k]; in other words, is it the case that there are numbers in A and B whose multiplication belongs to C.
Examples:
• When n = 3, and A = [1,3,4], B = [2,3,5], and C = [1,3,5], the answer is Yes, because for instance we have A[1] · B[3] = C[3] or A[1] · B[2] = C[2].
• When n = 3 and A = [1,3,4], B = [2,4,6], and C = [7,9,11], the answer is No.
(a) Suppose all the numbers in C belong to the set . Design and analyze an algorithm with worst-case runtime of O(n2) for the problem in this case. (10 points)
(b) Now suppose C can be any arbitrary array of n integers. Design and analyze a randomized algorithm with expected worst-case runtime of O(n2) for the problem in this case. (10 points)
Note: Actually, this problem also has a deterministic algorithm that runs in worst-case O(n2) time. But you do not need to design such an algorithm for this problem (although if you do, you will receive the full credit for both parts (a) and (b)).
Problem 5. Please solve the problems in exactly one of the two parts below.
Part 1 (dynamic programming): We want to purchase an item of price M and for that we have a collection of n different coins in an array C[1 : n] where coin i has value C[i] (we only have one copy of each coin). Our goal is to purchase this item using the smallest possible number of coins or outputting that the item cannot be purchased with these coins. Design a dynamic programming algorithm for this problem with worst-case runtime of O(n · M). (20 points)
Examples:
• Given M = 15, n = 7, and C = [4,9,3,2,7,5,6], the correct answer is 2 by picking C[2] = 9 and C[7] = 6 which add up to 15.
• Given M = 11, n = 4, and C = [4,3,5,9], the correct answer is that ‘the item cannot be purchased’ as no combination of these coins adds up to a value of 11 (recall that we can only use each coin once).
(a) Specification of recursive formula for the problem (in plain English): (5 points)
(b) Recursive solution for the formula and its proof of correctness: (7 points) (c) Algorithm (either memoization or bottom-up dynamic programming): (3 points)
(d) Runtime Analysis: (5 points) Part 2 (greedy): We want to purchase an item of price M and for that we have an unlimited (!) supply of dlogMe types of coins with value 1, . Our goal is to purchase this item using the smallest possible number of coins (it is always possible to buy this item by picking M coins of value 1). Design and analyze a greedy algorithm for this problem with O(logM) runtime. (20 points)
Examples:
• Given M = 15 (and so dlogMe = 4), the correct answer is 4 coins by picking one copy of each of the coins 8,4,2,1. Note that here we cannot pick the coin of value 2dlogMe = 24 = 16.
• Given M = 32 (and so dlogMe = 5), the correct answer is 1 coin by picking one copy of the coin 32 = 25 = 2dlogMe.
(a) Algorithm: (5 points)
(b) Proof of Correctness: (10 points) (c) Runtime Analysis: (5 points) Problem 6. [Extra credit] You are given two unsorted arrays A[1 : n] and B[1 : n] consisting of 2n distinct numbers such that A[1] < B[1] but A[n] > B[n]. Design and analyze an algorithm that in O(logn) time finds an index j ∈ [1 : n] such that A[j] < B[j] but A[j + 1] > B[j + 1].
Hint: Start by convincing yourself that such an index j always exist in the first place. (+10 points)
Extra Workspace