CSCI 570 – Spring 2021 – HW 3 Rubric
1
Solve the following recurrences by giving tight Θ-notation bounds in terms of n for sufficiently large n. Assume that T(·) represents the running time of an algorithm, i.e. T(n) is positive and non-decreasing function of n and for small constants c independent of n, T(c) is also a constant independent of n. Note that some of these recurrences might be a little challenging to think about at first. Each question has 4 points. For each question, you need to explain how the Master Theorem is applied (2 points) and state your answer (2 points).
• (a)T(n)=4T(n/2)+n2logn. • (b)T(n)=8T(n/6)+nlogn.
√
• (c) T(n) =
• (d) T(n) = 10T(n/2) + 2n. • (e)T(n)=2T(√n)+log2n. • (f)T(n)=T(n/2)−n+10 • (g)T(n)=2nT(n/2)+n
• (h) T(n) = 2T(n/4) + n0.51 • (i) T(n) = 0.5T(n/2) + 1/n • (j) T(n) = 16T(n/4) + n!
√6006
.
6006T(n/2) + n
Solution: In some cases, we shall need to invoke the Master Theorem with one generalization as described next. If the recurrence T(n) = aT(n/b) + f(n) is satisfied with f(n) = Θ(nlogb a logk n) for some k ≥ 0, then T(n) = Θ(nlogb a logk+1 n).
[Rubic (40 points, 4 points for each)
– 2 points for correctly explaining how to apply the Master theorem in this question
– 2 point for the correct answer
1
• (a) Observe that f(n) = n2 logn and nlogb a = n2, so applying the gener- alized Master theorem, T (n) = Θ(n2 log2 n)
• (b) Observe that nlogb a = nlog68 and f(n) = nlog(n) = O(nlog68−ε) for any o < ε < log86 −1. Thus, invoking Master theorem gives T (n) = Θ(nlogb a) = Θ(nlog6 8).
√ √√
6006 = n0.5 log2 6006 = O(n0.5 log2 8192) = O(n13/2) and f(n) = n 6006 = Ω(n 4900) = Ω(n70) = Ω(n13/2+ε) for any
√
• (c) We have nlogba = nlog2
0 < ε < 63.5. Thus from Master’s Theorem T(n) = Θ(f(n)) = Θ(n
6006). • (d)Wehavenlogb a =nlog2 10 andf(n)=2n =Ω(nlog2 10+ε)foranyε>0.
Therefore Master theorem implies T(n) = Θ(f(n)) = Θ(2n)
• (e) Use the change of variables n = 2m to get T(2m) = 2T(2m/2) + m. Next, denoting S (m) = T (2m ) implies that we have the recurrence S(m) = 2S(m/2) + m. Note that S(·) is a positive function due to the monotonicity of the increasing map x →− 2x and the positivity of T (·). All conditions for applicability of Master Theorem are satisfied and using the generalized version gives S(m) = Θ(mlogm) on observing that f(m) = m and mlogba = m. We express the solution in terms of T(n) by
T(n) = T(2m) = S(m) = mlog(m) = log2nloglog2 n
, for large enough n so that the growth expression above is positive.
• (f) We cannot apply master Theorem on this, because the f(n) could not be negative (we cannot perform negative number of operations in the recursion).
• (g) We cannot apply master Theorem on this, since a is not a constant. The number of sub-problems at each recursion step should be fixed.
• (h) We have nlogab = nlog24 = n0.5 and f(n) = n0.51 = Ω(n0.5+ε) for any 0 < ε < 0.01. Based on case 3 of master theorem we have T(n) = Θ(f(n)) = Θ(n0.51)
• (i) We cannot apply master Theorem on this, since a < 1. We cannot have less than one sub problem
b4
• (j)Wehavenloga =nlog16 =n2,andf(n)=n!=Ω(n2+ε)foranyε>0.
Based on case 3 of master theorem we have T (n) = Θ(f (n)) = Θ(n!) ]
2
Consider an array A of n numbers with the assurance that n > 2, A1 ≥ A2 andAn ≥An−1. AnindexiissaidtobealocalminimumofthearrayAifit satisfies1
(b) Similar to binary search call function recur(1, n) to find local minimum of the array A1,A2,…,An. In recur(s,e) function, define mid as s+e. Then:
2
1. if e−s is 2: return s+1 (base case)
2. if Amid−1 ≥ Amid and Amid+1 ≥ Amid: return mid as local minimum 3. else if Amid−1 < Amid: return recur(s, mid)
4. else if Amid > Amid+1: return recur(mid, e)
Complexity: If the running time of the algorithm on an input of size n is
T(n), then it involves a constant number of comparisons and assignments and
a recursive function call on either A1,…,A⌊n+1 ⌋ or A⌊n+1 ⌋,…,An. Therefore, 22
T(n) ≤ T(n+1) + θ(1). Assuming n to be a power of 2 (minus 1), this re- 2
currence simplifies to T (n) ≤ T ( n ) + θ(1) and invoking Master’s Theorem gives 2
T (n) = O(logn).
Correctness: Similar to part (a), we can prove the correctness of the algorithm by induction. The base case (1) is clear. The induction hypothesis is that the algorithm return the correct local minimum for any array of size less than n. In case of event 2, we know Amid−1 ≥ Amid and Amid+1 ≥ Amid, so the mid is local minimum. Otherwise, by moving to the appropriate sub-problem in cases 3 and 4 and based on induction hypothesis, the algorithm returns the correct answer.
[Rubic (15 points):
– [5 points]: part a (1 for base case, 4 for induction step: 2 point for each case)
– [4 points]: algorithm of part b (1 for each case).
– [1 points]: Proof of correctness.
– [5 points]: Computing time complexity.
]
3
3
There are n cities where for each i < j, there is a road from city i to city j which takes Ti,j time to travel. Two travelers Marco and Polo want to pass through all the cities, in the shortest time possible. In the other words, we want to divide the cities into two sets and assign one set to Marco and assign the other one to Polo such that the sum of the travel time by them is minimized. You can assume they start their travel from the city with smallest index from their set, and they travel cities in the ascending order of index (from smallest index to largest). The time complexity of your algorithm should be O(n2).
Solution: We want to use dynamic programming. First, we are going to
use array s (as a pre-processing step) to speedup our computations. Define
si = Σn−1Tj,j+1. Array s could be easily computed in O(n) time. j=i
1. Defining sub-problem: Let’s define ci,j for each i < j as the minimum possible time to travel through all the cities from i to n, while Marco starts from city i and Polo starts from city j.
2. Recurrence Relation: The base case of the dynamic Programming is for cn−1,n = 0. Now, we want to find the best answer for ci,j. First we know if i ̸= j − 1 Marco should travel cities i to j − 1 (because Polo cannot travel backwards). So, in that case ci,j = si − sj + cj −1,j . So now we should compute cj−1,j . There are 4 different possibilities to assign cities j − 1 and j to Marco and Polo. The value of cj−1,j is minimum of these 4 cases. Here k is all the possible cities after city j + 1:
1. Travel city j − 1 with Marco and give the rest to Polo: sj
2. Travel city j with Polo and give the rest to Marco: Tj−1,j+1 + sj+1 3. Add city j + 1 to Marco: min{Tj−1,j+1 + Tj,k + cj+1,k|∀k > j + 1} 4. Add city j + 1 to Polo: min{Tj−1,k + Tj,j+1 + cj+1,k|∀k > j + 1}
The final answer to the problem is min{c1,j |2 ≤ j ≤ n}. 3. Pseudo Code:
s[n] = 0
for i=n-1 to 1:
s[i]= T[i][i+1]+s[i+1] c[n-1][n] = 0 # Base case
for i=1 to n-2:
c[i][n] = s[i] – s[n – 1]
for j=n-1 to 2:
minval = min(s[j], T[j – 1, j + 1] + s[j + 1]) #Case 1 & 2
for k=j+2 to n-1:
minval = min(minval, T[j – 1, j + 1] + T[j, k] + c[j + 1][k]) #Case 3
minval = min(minval, T[j – 1, k] + T[j, j + 1] + c[j + 1][k]) #Case 4
c[j – 1][j] = minval
for i=1 to j-2:
4
c[i][j] = c[j – 1][j] + s[i] – s[j]
# Marco starts from 1, and Polo starts from j
final_answer = c[1][2]
for j=3 to n:
final_answer = min(final_answer, c[1][j])
return final_answer
4. Time Complexity: Start from i = n − 2 → 1 and loop through j = n → i+1. For i < j−1 (O(n2) such pairs) each update takes O(1) and for i = j − 1 (O(n) such pairs) each update takes O(n). The pre-processing of array s takes O(n) time. So, in total time complexity of the algorithm is O(n+n2 ×1+n×n)=O(n2).
[Rubic (20 points):
- [3 points]: Correct base case, and pointing out marco should travel cities
i to j − 1 if i ̸= j − 1.
- [12 points]: for covering all 4 mentioned cases, 3 points each. 2 cases: single city to travel by each traveler. 2 cases: adding cities to an already existing set of cities.
- [5 points]: Computing time complexity correctly.
- No reduction of point if they consider ending cities instead of starting city. In that case, they should solve opt[i, j] using previous sub-problems not the next ones!
- If they did not use array s to speed up the optimization (and they loop over to compute the total sum), and they end-up having O(n3), and they compute the correct time complexity, then deduct −2 points.
]
4
Erica is an undergraduate student at USC, and she is preparing for a very important exam.
There are n days left for her to review all the lectures. To make sure she can finish all the materials, in every two consecutive days she must go through at least k lectures. For example, if k = 5 and she learned 2 lectures yesterday, then she must learn at least 3 today.
Also, Erica’s attention and stamina for each day is limited, so for i’th day if Erica learns more than ai lectures, she will be exhausted that day.
You are asked to help her to make a plan. Design an Dynamic Program- ming algorithm that output the lectures she should learn each day (lets say
5
bi), so that she can finish the lectures and being as less exhausted as possi- ble(Specifically, minimize the sum of max(0, bi − ai)). Explain your algorithm and analyze it’s complexity.
hint: k is O(n).
Solution: First of all, we can use greedy to prove that Erica will learn at most k lectures everyday. This is because Erica is only required to learn at least k lectures every two days, so if she’s already learned k lectures in some day, the requirements on yesterday-today and today-tomorrow will both be satisfied, and there’s no need to study more. We use dynamic programming to solve this problem.
1. Defining sub-problem: let opti,j be the minimum exhaustion Erica could get after she studies lectures at days 1 . . . i and learned exactly j lectures at day i. Apparentlyi≤nandj≤k.
2. Recurrence Relation: For Erica to study j lectures at day i, she should study at least k − j lectures at day i − 1. So, the recursive formula would be:
opt1,j =max(0,(j−a1)),∀0≤j≤k
opti,j = min (opti−1,t+max(0,(j−ai))),∀2≤i≤n,0≤j≤k
k−j≤t≤k 3. Pseudo Code
for j=0 to k:
opt[1][j] = max(0, j - a[1])
for i=2 to n:
for j=0 to k:
opt[i][j] = infinity
for t=k-j to k:
opt[i][j] = min(opt[i][j], opt[i - 1][t] + max(0, j - a[i]))
final_answer = opt[n][0]
for j=1 to k:
final_answer = min(final_answer, opt[n][j])
return final_answer
4. Time Complexity The complexity for this algorithm is O(n3), since the total number of states is O(n2) (we have n days and k = O(n)) and each recursive formula costs O(n) time to compute.
Additionally, there’s a faster solution which only cost O(n) of time. It is not required for this answer, but for the sake of learning, we mention it here. The high-level idea is using the lazy strategy, which is, leave as much as possible lectures that will cause exhaustion to tomorrow. See if you can design this algorithm too.
[Rubic (15 points):
- [2 points]: Pointing out that Erica will not learn more than k lectures everyday.
6
- [4 points]: Designing the subproblems and recursive formula that can minimize the exhaustion.
- [7 points]: Taking care of the constraint of learning not less than k lectures.
- [2 points]: Computing time complexity correctly.
- Designing an non dynamic programming algorithm will get at most 14 points.
- It’s okay to design a dp algorithm faster than the solution using ’lazy strategy’.
]
5
Due to the pandemic, You decide to stay at home and play a new board game alone.
The game consists an array a of n positive integers and a chessman. To begin with, you should put your character in an arbitrary position. In each steps, you gain ai points, then move your chessman at least ai positions to the right (that is, i′ >= i + ai). The game ends when your chessman moves out of the array.
Design an algorithm that cost at most O(n) time to find the maximum points you can get. Explain your algorithm and analyze its complexity.
Solution:
1. Defining sub-problem: Let opti be maximum points you can get starting from position i. Define array S as Si = max{optj|i ≤ j}. We are going to use S as a helper for updating opt in the recurrence relation.
2. Recurrence Relation: Array S could capture the best move (maximum points) after being in cell i. As a base case, optn = Sn = an. The recursive formula can be:
The final output is S1. 3. Pseudo Code
opt[n] = a[n]
s[n] = opt[n]
for i=n-1 to 1:
opt[i] = a[i]
if i + a[i] <= n:
opt[i] += s[i + a[i]]
s[i] = max(opt[i], s[i + 1])
return s[1]
opti = ai + Si+ai
Si = max(opti, Si+1)
7
4. Time Complexity: The complexity of this algorithm is O(n), since there are O(n) subproblems and each recursive formula costs O(1) time to compute.
[Rubic (10 points):
- [2 points]: correct subproblem.
- [3 points]: correct recursive formula that can maximize the prize. - [3 points]: The algorithm only cost O(n) time.
- [2 points]: Computing time complexity correctly.
]
6
Joseph recently received some strings as his birthday gift from Chris. He is interested in the similarity between those strings. He thinks that two strings a and b are considered J-similar to each other in one of these two cases:
1. a is equal to b.
2. he can cut a into two substrings a1,a2 of the same length, and cut b in
the same way, then one of following is correct:
(a) a1 is J-similar to b1, and a2 is J-similar to b2.
(b) a2 is J-similar to b1, and a1 is J-similar to b2.
Caution: the second case is not applied to strings of odd length.
He ask you to help him sort this out. Please prove that only strings having the same length can be J-similar to each other, then design an algorithm to determine if two strings are J-similar within O(n2) time (where n is the length of strings).
Solution:
To make our proof straightforward, we first change the statement to another equivalent: For every string a of length n and string b, b will be J-similar to a only if length of b is equal to n.
We use induction on n to prove the statement.
The base case (n = 1) is trivial.
Assume we now have proved the statement for all n < k. Now we focus on
n = k. Regarding to the definition, there are two cases that b can be J-similar to a. Firstly, if a is equal to b, then apparently they have the same length. On the other hand, if the second case happens, by the induction either one of the following will be correct:
len(a1) = len(b1), len(a2) = len(b2) or len(a1) = len(b2), len(a2) = len(b1)
8
In both case we have len(a1) + len(a2) = len(b1) + len(b2), which means the length of b is also n.
The O(n2) algorithm is very easy to design: we just need to follow the two cases. Specifically, we design a function J similar(a) as follows:
def J_similar(a, b)
{
if a == b:
return True # they are identical
if len(a) % 2 == 1:
return False # Unable to cut strings of odd length
a1, a2 = a[:len(a)/2], a[len(a)/2:] # Cut string to half
b1, b2 = b[:len(b)/2], b[len(b)/2:] # Cut string to half
if J_similar(a1, b1) and J_similar(a2, b2):
return True
elif J_similar(a1, b2) and J_similar(a2, b1):
return True
else:
return False
}
this algorithm will results in T(n) = 4 · T(n/2) + O(n), which gives us T(n) = O(n2). Luckily, this is already enough to get full credit. 😉
However, we can go further trying to accelerate it. First of all, we can easily prove that if J (a, b), J (b, c), then J (a, c). This is called the Transitive Property. Using this property we can reduce one recursive call in every call of J similar:
def J_similar(a, b)
{
if a == b:
return True # they are identical
if len(a) % 2 == 1:
return False # Unable to cut strings of odd length
a1, a2 = a[:len(a)/2], a[len(a)/2:] # Cut string to half
b1, b2 = b[:len(b)/2], b[len(b)/2:] # Cut string to half
a1_b1 = J_similar(a1, b1)
a1_b2 = J_similar(a1, b2)
if a1_b1==False and not a1_b2==False:
return False
elif a1_b1==True and a1_b2==False:
return J_similar(a2,b2)
elif a1_b1==False and a1_b2==True:
return J_similar(a2,b1)
else:
return J_similar(a2,b1) # if J_similar(a2,b1)=False, then
9
}
J_similar(a2,b2)=False too.
The key point here is that if J similar(a1,b1) = J similar(a1,b2) = True, then J similar(b1, b2) = T rue. So, we will have J similar(a2, b1) = J similar(a2, b2), which can be checked in only one time of recursion.
In this version, we have T(n) = 3 · T(n/2) + O(n), which gives us T(n) = O(nlog2 3) ≈ O(n1.58). It’s still not O(n log n)!(which is required in the original version)
Further more, let’s explain how to reach O(n log n):
What we do here is: we rearrange both of the two strings by some certain movements, then we prove they will project to the same string if and only if they are J-similar to each other.
How to design this movement? To begin with, it’s obvious that for any string a of even length, once we split it into two halves (a1,a2), a′ = a2a1 should be also J-similar to a. Based on this, we can design a divide and conquer approach to rearrange a, b into their lexicographically minimum equivalents. Specifically, we design a function J-sort(a) as follows:
def J-sort(a)
{
if len(a) % 2 == 1:
return a # Unable to cut strings of odd length
a1, a2 = a[:len(a)/2], a[len(a)/2:] # Cut string to half
a1_m = J-sort(a1)
a2_m = J-sort(a2)
if a1_m < a2_m: # lexicographical order
return a1_m + a2_m # concatenate
else:
return a2_m + a1_m
}
It’s not hard to conclude that J-sort(a) has the lowest lexicographical order among all the strings that is J-similar to a (Just use induction like above). Because of this (and the same thing to b), we can further prove that a is J- similar to b if and only if J-sort(a) is equal to J-sort(b).
Let T (n) be the complexity of calculating J-sort(a) with respect to length n. Based on the previous analysis, we have T (n) = 2 · T (n/2) + O(n). The Master Theorem tells us T(n) = O(nlogn). Aside from that, checking the equivalence between two strings costs only O(n) time, which is negligible.
[Rubic (15 points):
- [5 points]: Proving the statement correctly
- [7 points]: Designing the divide-and-conquer algorithm. - [3 points]: Computing time complexity correctly.
]
10
7
Chris recently received an array p as his birthday gift from Joseph, whose ele- ments are either 0 or 1. He wants to use it to generate an infinite long super- array. Here is his strategy: each time, he inverts his array by bits, changing all 0 to 1 and all 1 to 0 to get another array, then concatenate the original array and the inverted array together. For example, if the original array is [0, 1, 1, 0], then the inverted array will be [1, 0, 0, 1] and the new array will be [0, 1, 1, 0, 1, 0, 0, 1]. He wonders what the array will look like after he repeat this many many times.
He ask you to help him sort this out. Given the original array p of length n and two indices a, b (n ≪ a ≪ b, ≪ means much less than) Design an algorithm to calculate the sum of elements between a and b of the generated infinite array pˆ, specifically, a≤i≤b pˆi. He also wants you to do it real fast, so make sure your algorithm runs less than O(b) time. Explain your algorithm and analyze its complexity.
Solution:
Rather than directly calculate the sum between element a and element b, it’s easier for us to calculate the prefix sum for a and b separately, then subtract them to get the answer.
Let Si denotes the prefix sum of pˆ from index 1 to i, which means Si = 1≤j≤i pˆj. Then:
b b a−1
pˆi =pˆi −pˆi =Sb −Sa−1 i=a i=1 i=1
Calculating Sb for arbitrary b can be finished in two steps: First, if b = 2k · n where k > 1, then pˆ1…b will be one of the arrays Chris gets during his movements. Thus, we can directly calculate Sb from Sb/2:
Sb =Sb/2 +(b/2−Sb/2)=b/2
Second, for arbitrary b, let c be the biggest number among set {2k · n|1 ≤ k} that satisfies c ≤ b. We can divide the array pˆ1…b into two parts: pˆ1…c and pˆc+1…b. For pˆ1…c, we can use the first step to calculate Sc. The tricky thing is the second part. Since pˆc+1…2c is the bit-inverted version of pˆ1…c, we have pˆi =1−pˆi−c,∀c