Only for the personal use of students registered in CS 344, Spring 2023 at Rutgers University.

Redistribution out of this class is strictly prohibited.

CS 344: Design and Analysis of Computer Algorithms Rutgers: Spring 2023

Homework #1
February 8, 2023
Name(s): Muhammad Chaudhary, Rishi Patel Extension: Yes

Homework Policy
• If you leave a question completely blank, you will receive 25% of the grade for that question. This
however does not apply to the extra credit questions.
• You may also consult all the materials used in this course (lecture notes, textbook, slides, etc.) while
writing your solution, but no other resources are allowed.
• Unless specified otherwise, you may use any algorithm covered in class as a “black box” – for example
you can simply write “sort the array in Θ(n log n) time using merge sort”.

• Remember to always prove the correctness of your algorithms and analyze their running time
(or any other efficiency measure asked in the question). See “Practice Homework” for an example.
• The “Challenge yourself” and “Fun with algorithms” are both extra credit. These problems are
significantly more challenging than the standard problems you see in this course (including lectures,
homeworks, and exams). As a general rule, only attempt to solve these problems if you enjoy them.
• Groups: You are allowed to form groups of size two or three students for solving each homework (you
can also opt to do it alone if you prefer). The policy regarding groups is as follows:
– You can pick different partners for different assignments (e.g., from HW1 to HW2) but for any
single assignment (e.g., HW1), you have to use the same partners for all questions.
– The members of each group only need to write down and submit a single assignment between
them, and all of them will receive the same grade.
– For submissions, only one member of the group submits the full solutions on Canvas and lists the
name of their partners in the group. The other members of the group also need to submit a PDF
on Canvas that contains only a single line, stating the name of their partner who has submitted
the full solution on Canvas (Example: Say A, B, and C are in one group; A submits the whole
assignment and writes down the names A, B, and C. B and C only submit a one-page PDF with
a single line that says “See the solution of A”).
– You are allowed to discuss the questions with any of your classmates even if they are not in your
group. But each group must write their solutions independently.

• Extensions: All the students in a group can decide to use an extension and submit their homework up
to two days after the original deadline (you do not need to ask permission for using an extension; there
is no penalty for using one, nor any bonus credit for not using them). In this case, all members of the
group lose one of their extensions. Since the group members can change during the semester, to ensure
fairness, as long as there is even one member of the group who has used less than two extensions, the
entire group is allowed to use an extension (this means that some students may end up having used
more than two extensions throughout the semester, but that is okay).

1
Only for the personal use of students registered in CS 344, Spring 2023 at Rutgers University.
Redistribution out of this class is strictly prohibited.

Problem 1. This question reviews asymptotic notation. You may assume the following inequalities for this
question (and throughout the course): For any constant c ≥ 1,

(log n)c = o(n) , nc = o(nc+1 ) , cn = o((c + 1)n ) , (n/2)(n/2) = o(n!) , n! = o(nn ).

(a) Rank the following functions based on their asymptotic value in the increasing order, i.e., list them
as functions f1 , f2 , f3 , . . . , f9 such that f1 = O(f2 ), f2 = O(f3 ), . . . , f8 = O(f9 ). Remember to write
down your proof for each equation fi = O(fi+1 ) in the sequence above. (15 points)
√
n log n nlog n
n
100n 2 n!
33 n
9n 33
log2 n

Hint: For some of the proofs, you can simply show that fi (n) ≤ fi+1 (n) for all sufficiently large n
which immediately implies fi = O(fi+1 ).

Solution. √ The ranking of the functions based on their asymptotic value in increasing order is:
n
327 , log(n), n, log(n)2 , 100n, n
log(n) n n
, 2 , 9 , n!

327 = O(log(n)) is true, as 327 does not depend on n and is a constant; and log(n) depends on n
and grows larger as n approaches ∞.

√
log(n) = O( n) ↔ (log(n))2 = O(n) which is true since log(n)c = O(n) for c ≥ 1.

√ n n 2
n = O( log(n)2 ) ↔ n = O( log(n)4 )

log(n)4
limn→+∞ nn2 = limn→+∞ n = 0 as log(n)4 = O(n) because log(n)c = O(n) for c ≥ 1. So
log(n)4
√ n
n = O( log(n) 2)

n
log(n)2 = O(100n)
n
log(n)2 1 n
limn→+∞ 100n = limn→+∞ 100∗log(n)2 = 0 so log(n)2 = O(100n)

100n = O(nlogn )
m = logn
n = 2m
m
100 ∗ 2m = O(2m )
m
Because m ≤ mm , 100 ∗ 2m = O(2m ) so 100n = O(nlogn )

nlog(n = O(2n )
n = 2log(n)
2
nlog(n) = 2log(n)
2
2log(n) = O(2n )
2
log(n)2 = O(n) as log(n)c = O(n) for c ≥ 1 so 2log(n) = O(2n ) so nlog(n = O(2n )

2n = O(9n ) as 2n = O(3n ) = O(4n ) = ... = O(9n ) as cn = O((c + 1)n ) for all c > 1.

2
Only for the personal use of students registered in CS 344, Spring 2023 at Rutgers University.
Redistribution out of this class is strictly prohibited.

9n = O(n!)
n n
Using n2 2 = O(n!), we can prove 9n = O(n!) by proving 9n = O( n2 2 ).
For n ≥ 2 ∗ 81 → 9 ≤ 2 ↔ 9n ≤ ( n2 )n , so 9n = O(n!)
pn p

(b) Consider the following four different functions f (n):

n
1 log log n n2 22 .

For each of these functions, determine which of the following statements is true and which one is false.
Remember to write down your proof for each choice. (10 points)
• f (n) = Θ(f (n − 1));
• f (n) = Θ(f ( n2 ));
√
• f (n) = Θ(f ( n));
n n−1 n−1 1 n n
Example: For the function f (n) = 22 , we have f (n − 1) = 22 . Since 22 = 2 2 ·2 = (22 )1/2 .
n n
f (n) 22 22 n
lim = lim 2n−1 = lim n = lim (22 )1/2 = +∞.
n→∞ f (n − 1) n→∞ 2 n→∞ (2 )1/2
2 n→∞

n
As such, f (n) ̸= O(f (n − 1)) and thus the first statement is false for 22 .
√
Solution. f (n) = 1, f (n − 1) = 1, f ( n2 ) = 1, f ( n) = 1
1 = Θ(1) so all the statements are true.
√ √
f (n) = loglogn,
√ f (n − 1) = loglog(n − 1), f ( n2 ) = loglog( n2 ), f ( n) = loglog n. If we prove loglogn =
Θ(loglog n) then we know loglogn = Θ(loglog(n − 1)) and loglogn = Θ(loglog n2 )
√ 1
loglog n = loglog(n 2 ) = log( 12 logn) = log( 12 ) + loglogn = −1 + loglogn
√ √
limn→+∞ loglog n loglogn 1
loglogn = limn→+∞ loglogn − loglogn = 1 − 0 = 1 so loglogn = Θ(loglog n) which means all the
statements are true.

n2 √ √
f (n) = n2 , f (n − 1) = (n − 1)2 = n2 − 2n + 1, f ( n2 ) = ( n2 )2 = 4 , f ( n) = ( n)2 = n.
2
limn→+∞ n −2n+1 n2 = 1 so f (n) = Θ(f (n − 1)) is true.
n2
limn→+∞ 4
n2 = 14 so f (n) = Θ(f ( n2 )) is true.
n2 √
limn→+∞ n = ∞ which means f (n) ̸= Θ(f ( n)) so it is false.
n n −1
√ n √ √
n
f (n) = 22 , f (n − 1) = 22 −2 , f ( n2 ) = 2 2 , f ( n) = 22
n n −1
If we prove 22 ̸= Θ(2√2 −2 ) then all the statements are false.
n −1 n 1
22 −2 =√2(2n )∗ 2 = 22n
n n −1
22
limn→+∞ 22n = limn→+∞ √ 12n = 0 so 22 ̸= Θ(22 −2 ) so all the statements are false.
2

Problem 2. Your goal in this problem is to analyze the runtime of the following (imaginary) recursive
algorithms for some (even more imaginary) problem:

3
Only for the personal use of students registered in CS 344, Spring 2023 at Rutgers University.
Redistribution out of this class is strictly prohibited.

(A) Algorithm A divides an instance of size n in to 3 subproblems of size n − 1 each, recursively solves
each one, and then takes O(1) time to combine the solutions and output the answer.
Solution. There are three recursive calls on inputs of length n-1, where O(1) is the time on top of the
3 recursive calls.

So the recurrence will be T (n) ≤ 3 ∗ T (n − 1) + O(1)

Figure 1: Recursion tree for algorithm A.

Pn Pn−1
i=1 3i−1 ∗ C = i=0 3i ∗ C
Pn−1 i n
i=0 3 = 3 −1 ≤ 3n
Pn−1 i 2
So i=0 3 ∗ C ≤ 3n ∗ C = O(3n )

Therefore, T (n) = O(3n ) in this case.

(B) Algorithm B divides an instance of size n into 2 subproblems, one with size n/4 and one with size n/5,
recursively solves each one, and then takes O(n) time to combine the solutions and output the answer.
Solution. Let us write the recurrence for an arbitrary Algorithm B as:
n n
T (n) = T ( ) + T ( ) + O(n)
4 5

Figure 2: Recursion tree for algorithm B.

First, let’s solve for the case T ( n4 ) + O(n). At the level i of the tree, we have 2i nodes, each with the
value of c ∗ ( n4 )i . Hence, the total value of level i is ( 21 )i ∗ c ∗ n. The total number of levels in the tree
is also [log4 n]. As such, the total value of the tree is:

log4 n log4 n ∞
X 1
i
X 1
i
X 1 −1
( ) ·c·n=c·n· ( ) ≤c·n· ( )i = 1 · c · n = 2 · c · n =⇒ O(n)
2 −1
i=0
2 i=0
2 i=0
2

4
Only for the personal use of students registered in CS 344, Spring 2023 at Rutgers University.
Redistribution out of this class is strictly prohibited.

(the second last equality is by using the formula for sum of geometric series)

Hence T (n) = O(n) in this case.

Now, let’s solve for the case T ( n5 ) + O(n). At the level i of the tree, we have 2i nodes, each with the
value of c · ( n5 )i . Hence, the total value of level i is ( 25 )i · c · n. The total number of levels in the tree is
also [log5 n]. As such, the total value of the tree is:

log5 n log5 n ∞
X 2 X 2 X 2 −1 5
( )i · c · n = c · n · ( )i ≤ c · n · ( )i = 2 · c · n = · c · n =⇒ O(n)
5 −1
i=0
5 i=0
5 i=0
5 3

(the second last equality is by using the formula for sum of geometric series)

Now, combining both solutions we have O(n).

So, the tightest asymptotic upper bound for this function will be O(n).

(C) Algorithm C divides an instance of size n into 5 subproblems of size n/5 each, recursively solves each
one, and then takes O(n) time to combine the solutions and output the answer.

Solution. Let us write the recurrence for Algorithm C as:

n
T (n) = 5T + O(n)
5

Figure 3: Recursion tree for algorithm C.

At each level i, there are 5i nodes, each with the value of c · n · ( 15 )i . Hence, the total value of level i
is c · n. The total number of levels in the tree is [log5 n].
Therefore, the total cost of the recursion tree is c · n. Hence, the total value of the tree is:

log5 n ∞
X X
i
1 ·c·n≤ 1i · c · n =⇒ O(nlogn)
i=0 i=0

We got this value by calculating:

The cost of the tree at each level: O(n)

5
Only for the personal use of students registered in CS 344, Spring 2023 at Rutgers University.
Redistribution out of this class is strictly prohibited.

Total value of the tree: T (n) ≤ c · n · [log5 n]

T (n) = O(log n) · O(n) = O(n log n)

(D) Algorithm D divides an instance of size n into 5 subproblems of size n/2 each, recursively solves each
one, and then takes O(n2 ) time to combine the solutions and output the answer.
Solution. Let us write the recurrence for the algorithm as:
n
T (n) = 5T + O(n2 )
2

Figure 4: Recursion tree for algorithm D.

2
At level i, there are 5i nodes each with the value of c · 2ni . Hence, the total value of level i is

i
c · n2 · 52 . The total number of levels in the tree is [log2 n]. Therefore, the total value of the tree is:

log2 n log2 n ∞
X 5
i 2 2
X 5
i 2
X 5 −1 2
( ) ∗c∗n =c∗n ∗ ( ) ≤c∗n ∗ ( )i = 5 ∗ c ∗ n2 = ∗ c ∗ n2 =⇒ O(n2 )
i=0
2 i=0
2 i=0
2 2 − 1 3

(the second last equality is by using the formula for the sum of geometric series)

Hence T (n) = O(n2 ) is the tightest asymptotic upper bound on the runtime of the algorithm D.

For each algorithm, write a recurrence for its runtime and use the recursion tree method of Lecture 5 to solve
this recurrence and find the tightest asymptotic upper bound on runtime of the algorithm. (25 points)

Problem 3. In this problem, we consider a non-standard sorting algorithm called the Slow Sort. Given an
array A[1 : n] of n integers, the algorithm is as follows:
• Slow-Sort(A[1 : n]):

1. If n < 100, run merge sort (or selection sort or insertion sort) on A.

6
Only for the personal use of students registered in CS 344, Spring 2023 at Rutgers University.
Redistribution out of this class is strictly prohibited.

2. Otherwise, run Slow-Sort(A[1 : n − 1]), Slow-Sort(A[2 : n]), and Slow-Sort(A[1 : n − 1]) again.

We now analyze this algorithm.

(a) Prove the correctness of Slow-Sort. (15 points)

Solution. Proof by Induction:
Induction Hypothesis: Slow sort sorts an array of length n ≥ 1
Base case: n = 1 to 99 (solved using merge sort)

Inductive Step: If slow sort sorts an array of size n ≤ k then slow sort will correctly sort an array of
size n = k + 1
Lets have an array A of size n = k + 1
In the first recursive call (A[1 : n − 1]), we can assume that we correctly sorted A[1 : n − 1] because
A[1 : n − 1] is the same as A[1 : k], which we know is sorted correctly due to the inductive hypothesis.
We can also conclude that the max element of A is either A[k] or A[k + 1].
In the second recursive call (A[2 : n]), we can assume that we correctly solved A[2 : n] or A[2 : k + 1]
as the length of (A[2 : k + 1]) is k, so we know it is correctly solved due to the inductive hypothesis.
We can also conclude that the max element is in A[k + 1].

In the third recursive call (A[1 : n−1]), we can assume that we correctly solved (A[1 : n−1]) or A[1 : k],
as it is of length k, which we know is correctly sorted due to the inductive hypothesis. Because we
know that (A[1 : k]) is correctly sorted and A[k + 1] is the max element of A, we can conclude that all
of A is correctly sorted.

(b) Write a recurrence for Slow-Sort and use the recursion tree method of Lecture 5 to solve this recurrence
and find the tightest asymptotic upper bound on the runtime of Slow-Sort. (10 points)
Solution.

There are 3 recursive calls on inputs of length n − 1, where O(1) is the time on top of the 3 recursive
calls.
The base case of merge sort is going to be constant O(1), as it always sorts only when the input less
than 100.

So the recursion will be T (n) ≤ 3 · T (n − 1) + O(1).

Figure 5: Recursion tree for Question 3 (b).

7
Only for the personal use of students registered in CS 344, Spring 2023 at Rutgers University.
Redistribution out of this class is strictly prohibited.

n
X n−1
X
3i−1 · c = 3i · c
i=1 i=0

n−1
X 3n − 1
3i = ≤ 3n
i=0
2

n−1
X
3i · c ≤ 3n · c = O(3n )
i=0

Problem 4. You are hired to help the rebels fight the evil empire in Star Wars (!). The rebels have n space
ships and each space ship i ∈ {1, . . . , n} has a certain power pi . Moreover, the empire has m bases where
each base j ∈ {1, . . . , m} has a defensive power dj and gold gj . You know that each space ship can attack
every base with defensive power strictly smaller than the ship’s own power and collect its golds.
The rebels need to know that, for each of their space ships, what is the maximum amount of gold this space
ship can collect. Design an algorithm with running time O((n + m) · log m) for this task. (25 points)

Example. The correct answer for the following input with n = 4 and m = 5 is [8, 5, 7, 11]:

power of space ships: p1 = 5, p2 = 3, p3 = 4, p4 = 9;

defense power of bases: d1 = 3, d2 = 8, d3 = 4, d4 = 0, d5 = 1;
amount of gold in bases: g1 = 2, g2 = 3, g3 = 1, g4 = 3, g5 = 2.

Solution. Although there are different ways to approach this problem, we will be using binary search
because it provides a faster way to find a desired element in a sorted array. The basic functionality of the
below algorithm is that it first sorts the defensive power of bases in increasing order (by using Merge Sort).
Then, we will create an array that stores the sum of the gold from 1 to j in the jth index of the array. And
after that, we will use binary search for each ship to find the the base with the largest index from the sorted
array that has Pi (Spaceship power) ≥ defensive power. This means that all the bases before this base can
be attacked, and the total gold can be calculated by utilizing the array we created in the prior step.

Algorithm with the running time O((n+m) ·logm)is :

1. Sort bases di using Merge sort in an increasing order of defense power

2. Create an array G[1:m] that has G[1] = the amount of gold in the base with the lowest defensive power.
For j=2 to m of array G, G[j] = G[j-1] + the amount of gold in the jth index of bases sorted in merge
sort.
3. For each ship, use binary search to find base j with the largest index from the merge sorted array that
has Pi (Spaceship power) > defensive power. Then use that j index to get the max gold that can be
collected by looking at G[j].

• Proof of Correctness:
– The first step correctly sorts the bases according to their defensive power because we used merge
sort (proved correctness in class).

8
Only for the personal use of students registered in CS 344, Spring 2023 at Rutgers University.
Redistribution out of this class is strictly prohibited.

– The second step correctly creates an array where the value at each index j is the sum of the gold
at the current index and everything prior to that. Since we are using the bases sorted according
to defensive power, we know that the sum of the gold before index j (G[j-1]) is attainable by the
ship, as the defensive power will the less than the ship’s power, and the base at index j is the last
base where the spaceship power is greater than the defensive power.
– The binary search to find the base j with the largest with the largest index from the merge sorted
array that has Pi (Spaceship power) > defensive power will always give us the correct index j, as
we are using binary search (proved in class). That index will correctly give us the maximum gold
that a ship can collect, because we use that index in the gold array created in the prior step. As
proved above the G[j] gives us the maximum gold of all the bases where the spaceship’s power is
greater than the defensive power.

• Runtime Analysis:
– Runtime analysis for the Merge sort: O(m log m)(Lecture.5 Pg:3) (We derived this by knowing
the number of times the dividing step is repeated O(log m) and the time complexity of merging
step O(m))
– O(logm) · O(m) = O(mlogm)
– Runtime analysis for creating the maximum gold array is O(m), as we have to go through each
index in the gold array, which has a length of m.
– Since we have n spaceships the total Runtime analysis for Binary search: O(n log m)(Lecture. 4
Pg: 3)
– O(m · logm) + O(n · logm) + O(m) = O((n + m) · logm).

Challenge Yourself. Let us revisit the community detection problem but with an interesting twist. Re-
member that we have a collection of n people for some odd integer n and we know that strictly more than
half of them belong to a hidden community. As before, when we introduce two people together, the members
of the hidden community would say they know the other person if they also belong to the community, and
otherwise they say they do not know the other person. The twist is now as follows: the people that do not
belong to the community may lie, meaning that they may decide to say they know the other person even
though in reality only people inside the hidden community know each other.
Concretely, suppose we introduce two people A and B, then what they will say would be one of the following
(first part of tuple is the answer of A and second part is the answer of B):

• if both belong: (know , know);

• if A belongs and B does not: (does not know , know/does not know);
• if B belongs and A does not: (know/does not know , does not know);
• if neither belongs: (know/does not know , know/does not know);

Design an algorithm that finds all members of the hidden community using O(n) greetings. (+10 points)
Solution. Algorithm:

1. Choose Person A randomly, and introduce him to Person B that is also chosen randomly.

9
Only for the personal use of students registered in CS 344, Spring 2023 at Rutgers University.
Redistribution out of this class is strictly prohibited.

2. If both Person A and B, say(know, know) they belong to the hidden community, we add them to the
hidden community list.
3. If both Person A and B say(does not know), introduce them to Person C
4. If person C says he knows both A and B, Add all of them to the hidden community list.
5. If Person C says they only know one of A or B we add that person to the hidden community.
6. If person C doesn’t know either A or B, Start with step 1 and repeat the process until all the members
of the hidden community are found.

Fun with Algorithms. We have an n-story building and a series of magical vases that work as follows:
there is some unknown level L in the building that if we throw these vases down from any of the levels
L, L + 1, . . . , n, they will definitely break; however, no matter how many times we throw the vases down
from any level below L nothing will happen them. Our goal in this question is to determine this level L by
throwing the vases from different levels of the building (!).
For each of the scenarios below, design an algorithm that uses asymptotically the smallest number of times
we throw a vase (so the measure of efficiency for us is the number of vase throws).

(a) When we have only one vase. Once we break the vase, there is nothing else we can do. (+2 points)
Solution. Algorithm:
(a) Start at first Level(L)
(b) If the vase does not break, Go up one level (L+1)
(c) Repeat step (b) if the vase does not break.
(d) If the vase breaks, STOP. desired level L is current level. This algorithm takes O(n) time com-
plexity

(b) When we have four vases. Once we break all four vases, there is nothing else we can do. (+4 points)
Solution. For this problem we will be using binary search algorithm.
(a) Throw the vase from ( n2 ) of the total range of levels (L, L + 1 · · · n) being tested.
(b) If the vase breaks, then the search range is reduced to the lower half of the original range, which
is ( n4 ) then ( n8 ) until we break 3 vases.
(c) Go to Level 1 and start throwing vase from (L · ·· ( n8 ))
(d) If the vase does not break at ( n2 ) then the search range is reduced to the upper half of the original
range.
(e) This process is repeated (n 2 · · · n − 1) until the floor from which a vase will not break is found.
This algorithm takes O(log n) time complexity

(c) When we have an unlimited number of vases. (+4 points)

Solution. This algorithm also uses binary search
(a) Start with the ( n2 ) floor of the building and throw one vase.

10
Only for the personal use of students registered in CS 344, Spring 2023 at Rutgers University.
Redistribution out of this class is strictly prohibited.

(b) If the vase breaks, move to the lower half of the building (from the current floor to the first floor).
(c) If the vase does not break, move to the upper half of the building (from the current floor to the
top floor).
(d) Repeat the process of steps 1 to 3 until the current floor is the only possibility left.
(e) Level L is the floor where the vase broke.

11