CS412 Algorithms: Design & Analysis

Spring 2024

Dhanani School of Science and Engineering

Habib University

Copyright © 2024 Habib University

Week 1 Practice Problems
Asymptotic Analysis

1. Let
p(n) = Σdi=0 ai ni
where ad > 0, be a degree-d polynomial in n, and let k be a constant. Use the definitions
of the asymptotic notations to prove the following properties:
(a) If k ≥ d, then p(n) = O(nk ).
(b) If k ≤ d, then p(n) = Ω(nk ).
(c) If k = d, then p(n) = Θ(nk ).
(d) If k > d, then p(n) = o(nk ).
(e) If k < d, then p(n) = ω(nk ).

(a) If we pick any c > 0, then, the end behavior of cnk − p(n) is going to infinity, in
particular, there is an n0 so that for every n ≥ n0 , it is positive, so, we can add
p(n) to both sides to get p(n) < cnk .
(b) If we pick any c > 0, then, the end behavior of p(n) − cnk is going to infinity, in
particular, there is an n0 so that for every n ≥ n0 , it is positive, so, we can add
cnk to both sides to get p(n) > cnk .
(c) We have by the previous parts that p(n) = O(nk ) and p(n) = Ω(nk). So, by
Theorem 3.1, we have that p(n) = Θ(nk )
(d)
p(n) nd (ad + o(1)) 2ad nd
lim = lim < lim = 2ad lim nd−k = 0
n→∞ nk n→∞ nk n→∞ nk n→∞

(e)
nk nk nk
lim = lim d < lim d = lim nk−d = 0
n→∞ p(n) n→∞ n O(1) n→∞ n n→∞

2. Indicate, for each pair of expressions (A, B) in the table below whether A is O, o, Ω, ω,
or Θ of B. Assume that k ≥ 1, ϵ > 0, and c > 1 are constants. Write your answer in the
form of the table with “yes” or “no” written in each box.

1
Figure 1

3. Let f (n) and g(n) be asymptotically positive functions. Prove or disprove each of the
following conjectures.
(a) f (n) = O(g(n)) implies g(n) = O(f (n)).
(b) f (n) + g(n) = Θ(min{f (n), g(n)}).
(c) f (n) = O(g(n)) implies lg f (n) = O(lg g(n)), where lg g(n) ≥ 1 and f (n) ≥ 1 for all
sufficiently large n.
(d) f (n) = O(g(n)) implies 2f (n) = O(2g(n) ).
(e) f (n) = O((f (n))2 ).
(f) f (n) = O(g(n)) implies g(n) = Ω(f (n)).
(g) f (n) = Θ(f ( n2 )).
(h) f (n) + o(f (n)) = Θ(f (n)).

(a) False. Counterexample: n = O(n2 ) but n2 ̸= O(n).

(b) False. Counterexample: n + n2 ̸= Θ(n).
(c) True. Since f (n) = O(g(n)) there exist c and n0 such that n ≥ n0 implies f (n) ≤
cg(n) and f (n) ≥ 1. This means that log(f (n)) ≤ log(cg(n)) = log(c)+log(g(n)).
Note that the inequality is preserved after taking logs because f (n) ≥ 1. Now
we need to find d such that log(f (n)) ≤ dlog(g(n)). It will suffice to make

2
log(c) + log(g(n)) ≤ dlog(g(n)), which is achieved by taking d = log(c) + 1, since
log(g(n)) ≥ 1.
(d) False. Counterexample: 2n = O(n) but 22n ̸= 2n as shown below: 2n+1 ≥2 ·
2n for all n ≥ 0, so 2n+1 = O(2n ). However, 22n is not O(2n ). If it were, there
would exist n0 and c such that n ≥ n0 implies 2nů2 n = 22n c2 n, so 2n c for
n n0 which is clearly impossible since c is a constant..

4. Let f (n) and g(n) be asymptotically positive functions. Prove the following identities:
(a) Θ(Θ(f (n))) = Θ(f (n)).
(b) Θ(f (n)) + O(f (n)) = Θ(f (n)).
(c) Θ(f (n)) + Θ(g(n)) = Θ(f (n) + g(n)).
(d) Θ(f (n)).Θ(g(n)) = Θ(f (n).g(n)).

3
CS412 Algorithms: Design & Analysis

Spring 2024

Dhanani School of Science and Engineering

Habib University

Copyright © 2024 Habib University

Week 2 Practice Problems
Asymptotic Analysis

1. Let f (n) and g(n) be asymptotically non-negative functions. Using the basic definition of
Θ-notation, prove that max{f (n), g(n)} = Θ(f (n) + g(n)).

Solution:
Let n1 < n2 be arbitrary. From f and g be monotonic increasing, we know f (n1 ) <
f (n2 ) and g(n1 ) < g(n2 ). So

f (n1 ) + g(n1 ) < f (n2 ) + g(n1 ) < f (n2 ) + g(n2 )

Since g(n1 ) < g(n2 ) we have f (g(n1 )) < f (g(n2 )). Lastly, if both are non-negative,
then,
f (n1 )g(n1 ) = f (n2 )g(n1 ) + (f (n2 ) − f (n1 ))g(n1 )
= f (n2 )g(n2 ) + f (n2 )(g(n2 ) − g(n1 )) + (f (n2 ) − f (n1 ))g(n1 )
Since f (n1 ) ≥ 0, f (n2 ) > 0, the second term in this expression is greater than zero.
The third term is non-negative, so, the whole thing is < f (n2 )g(n2 ).

2. Prove or disprove the statements below.

(a) (n + 1)2 = n2 + O(n)
√ √
(b) (n + O ( n)) (n + O (log (n)))2 = n3 + O n5

(c) exp (O(1)) = O(en )

(d) nlog (n) = O ((log n)n )
(e) 22n = O (2n )

Solution: For (a),

1<n (1)
2n + 1 < 3n (2)
2n + 1 < O(n) (3)
2 2
n + 2n + 1 < n + O(n) (4)

1
For (b),
√
n+O n (n + O (log (n)))2 (5)
√
= n + c0 n (n + c1 log (n))2 (6)
√
= n3 + O n5 (7)

After small algebraic simplification, we went from 6 to 7.

For (c),

exp (O(1)) (8)

= exp(c0 ) (9)
≤ exp (n) ∀n ≥ c0 (10)
=O(exp(n)) (11)

Hence (c) is false and can not be proven.

For (e), we can not bound 4n with 2n , as there will always be some point where it is
not true. In general ∀a, b, n, 1 < a < b, 0 < n, an < bn .

3. Prove that for any two functions f (n) and g(n), we have f (n) = Θ(g(n)) if and only if
f (n) = O(g(n)) and f (n) = Ω(g(n)).

Solution: We can formulate the statement as,

f (n) = Θ(g(n)) ⇐⇒ (f (n) = Ω(g(n))) ∧ (f (n) = O(g(n)))

The proof starts here,

f (n) = Θ(g(n)) ⇐⇒ f (n) ∈ {g(k) | ∃c0 , c1 , n0 ∋ ∀n ≥ n0 , 0 ≤ c0 f (n) ≤ g(n) ≤ c1 f (n)}

(12)
⇐⇒ f (n) ∈ {g(k) | ∃c0 , c1 , n0 ∋ ∀n ≥ n0 , (c0 f (n) ≤ g(n)) ∧ (0 ≤ g(n) ≤ c1 f (n))}
(13)
⇐⇒ f (n) ∈ {g(k) | ∃c0 , c1 , n0 ∋ ∀n ≥ n0 , 0 ≤ c0 f (n) ≤ g(n)} ∩
{g(k) | ∃c0 , c1 , n0 ∋ ∀n ≥ n0 , 0 ≤ g(n) ≤ c1 f (n)} (14)
⇐⇒ f (n) ∈ {g(k) | ∃c0 , c1 , n0 ∋ ∀n ≥ n0 , 0 ≤ c0 f (n) ≤ g(n)} ∧
f (n) ∈ {g(k) | ∃c0 , c1 , n0 ∋ ∀n ≥ n0 , 0 ≤ g(n) ≤ c1 f (n)} (15)
⇐⇒ f (n) = Ω(g(n)) ∧ f (n) = O(g(n)) (16)

4. Prove that for S ⊆ Z,  

X X
Θ(f (k)) = Θ  f (k)
k∈S k∈S

assuming both sums converge.

Page 2
Solution: Θ(·) is a set by definition. The book does not define any operation + that
can be utilized in this proof. This question is book “Introduction to Algorithms” chapter
3, question 3.5(f).

5. Is 2n+1 = O(2n )? Is 22n = O(2n )

Solution: 2n+1 = O(2n ), but 22n ̸= O(2n ).

To show that 2n+1 = O(2n ), we must find constants c, n0 > 0 such that
0 ≤ 2n+1 ≤ c.2n for all n ≥ n0 .
Since 2n+1 = 2.2n for all n, we can satisfy the definition with c = 2 and n0 = 1.
To show that 22n ̸= O(2n ) assume there exist constants c, n0 > 0 such that
0 ≤ 2n ≤ c.2n for all n ≥ n0 .
Then 22n = 2n .2n ≤ c.2n =⇒ 2n ≤ c. But no constant is greater than all 2n , and so
the assumption leads to a contradiction.

Page 3
CS412 Algorithms: Design & Analysis

Spring 2024

Dhanani School of Science and Engineering

Habib University

Copyright © 2024 Habib University

Week 3 Practice Problems
Asymptotic Analysis 3

1. Explain why the statement, “The running time of algorithm A is at least O(n2 ),” is mean-
ingless.

Solution: There are a ton of different funtions that have growth rate less than or equal
to n2 . In particular, functions that are constant or shrink to zero arbitrarily fast. Saying
that you grow more quickly than a function that shrinks to zero quickly means nothing.

2. Prove that the running time of an algorithm is Θ(g(n)) if and only if its worst-case running
time is O(g(n)) and its best-case running time is Ω(g(n)).

Solution: Suppose the running time is Θ(g(n)). By Theorem 3.1, the running time is
O(g(n)), which implies that for any input of size n ≥ n0 the running time is bounded
above by c1 g(n) for some c1 . This includes the running time on the worst-case input.
Theorem 3.1 also imlpies the running time is Ω(g(n)), which implies that for any input
of size n ≥ n0 the running time is bounded below by c2 g(n) for some c2 . This includes
the running time of the best-case input. On the other hand, the running time of any
input is bounded above by the worst-case running time and bounded below by the
best-case running time. If the worst-case and best-case running times are O(g(n)) and
Ω(g(n)) respectively, then the running time of any input of size n must be O(g(n)) and
Ω(g(n)). Theorem 3.1 implies that the running time is Θ(g(n)).

3. Prove that o(g(n)) ⋒ ω(g(n)) is the empty set.

Solution: Suppose we had some f (n) ∈ o(g(n)) ⋒ ω(g(n)). Then, we have

f (n)
0 = lim =∞
n→∞ g(n)

which is a contradiction, hence the set is empty.

4. Show that klnk = Θ(n) implies k = Θ(n/ln).

Solution: Let c1 and c2 be such that c1 n ≤ klnk ≤ c2 n. Then we have lnc1 + lnn =
ln(c1 n) ≤ ln(klnk) = lnk + ln(lnk) so lnn = O(lnk). Let c3 be such that lnn ≤ c3 lnk.
Then
n n k
≥ ≥
lnn c3 lnk c2 c3
n
so that ln n = Ω(k). Similarly, we have lnk + ln(lnk) = ln(klnk) ≤ ln(c2 n) = ln(c2 ) +

1
ln(n) so ln(n) = Ω(lnk). Let c4 be such that lnn ≥ c4 lnk. Then

n n k
≤ ≤
lnn c4 lnk c1 c4
n n
so that lnn = O(k). By Theorem 3.1 this implies lnn = Θk. Then by Symmetry,
n
k = Θ lnn .

5. Show that for any real constants a and b, where b > 0, (n + a)b = Θ(nb ).

Solution: Let c = 2b and n0 ≥ 2a. Then for all n ≥ n0 we have (n + a)b leq(2n)b = cnb
−a 1 −a
so (n + a)b = O(nb ). Now let n0 ≥ 1−1/2 1/b and c = 2 . Then n ≥ n0 ≥ 1−1/21/b if and
n
only if n − 21/b ≥ −a if and only if n + a ≥ (1/2)a/b n if and only if (n + a)b ≥ cnb .
Therefore (n + a)b = Ω(nb ). By Theorem 3.1, (n + a)b = Θ(nb ).

Page 2
CS412 Algorithms: Design & Analysis

Spring 2024

Dhanani School of Science and Engineering

Habib University

Copyright © 2024 Habib University

Practice Problems
Week 4

1. Although merge sort runs in Θ(nlgn) worst-case time and insertion sort runs in Θ(n2 )
worst-case time, the constant factors in insertion sort can make it faster in practice for
small problem sizes on many machines. Thus, it makes sense to coarsen the leaves of the
recursion by using insertion sort within merge sort when subproblems become sufficiently
small. Consider a modification to merge sort in which n = k sublists of length k are sorted
using insertion sort and then merged using the standard merging mechanism, where k is a
value to be determined.
(a) Show that insertion sort can sort the n = k sublists, each of length k, in Θ(nk) worst-
case time.
(b) Show how to merge the sublists in Θ(nlg(n/k)) worst-case time.
(c) Given that the modified algorithm runs in Θ(nk + nlg(n/k)) worst-case time, what is
the largest value of k as a function of n for which the modified algorithm has the same
running time as standard merge sort, in terms of, Θ−notation?
(d) How should we choose k in practice?

Solution: a) The time for insertion sort to sort a single list of length k is Θ(k 2 ), so,
n/k of them will take time Θ( nk k 2 ) = Θ(nk).
b) Suppose we have coarseness k. This meas we can just start using the usual merging
procedure, except starting it at the level in which each array has size at most k. This
means that the depth of the merge tree is lg(n) − lg(k) = lg(n/k). Each level of merging
is still time cn, so putting it together, the merging takes time Θ(nlg(n/k)).
c) Viewing k as a function of n, as long as k(n) ∈ O(lg(n)), it has the same asymptotics.
In particular, for any constant choice of k, the asymptotics are the same.
d) If we optimize the previous expression using our calculus 1 skills to get k, we have
that c1 n − nck2 = 0 where c1 and c2 are the coeffients of nk and nlg(n/k) hidden by
the asymptotics notation. In particular, a constant choice of k is optimal. In practice
we could find the best choice of this k by just trying and timing for various values for
sufficiently large n.

2. What does FIND-MAXIMUM-SUBARRAY return when all elements of A are negative?

Solution: It will return the least negative position. As each of the cross sums are
computed, the most positive one must have the shortest possible lengths. The algorithm
doesn’t consider length zero sub arrays, so it must have length 1.

1
3. Write pseudocode for the brute-force method of solving the maximum-subarray problem.
Your procedure should run in Θ(n2 ).

Solution:
1 left = 1
2 right = 1
3 max = A [1]
4 curSum = 0
5 for i = 1 to n do // Increment left end of subarray
6 curSum = 0
7 for j = i to n do // Increment right end of subarray
8 curSum = curSum + A [ j ]
9 if curSum > max then
10 max = curSum
11 left = i
12 right = j
13 end if
14 end for
15 end for

−ϕˆi
ϕi√
4. Prove by induction that the ith Fibonacci number satisfies the equality Fi = 5
where
ϕ is the golden ratio and ϕ̂ is its conjugate.

√
6+2 5
Solution: First, we show that 1 + ϕ = 4 = ϕ2 . So for ever√ i, ϕi−1 √
+ ϕi−2 =
1+ 5 1− 5 √
0 0 −
ϕi−2 (ϕ+1) = ϕi . Similarly for ϕ̂. For i = 0, ϕ −5 ϕ̂ = 0. For i = 1, 2 √5 2 = √55 = 1.
i−1 i−2 i−1 +ϕ̂i−2 ) i ˆi
Then, by induction, Fi = Fi−1 + Fi−2 = ϕ +ϕ −( √ ϕ̂
5
= ϕ √−5ϕ .

5. Use the master method to give tight asymptotic bounds for the following recurrences.
1. T (n) = 2T (n/4) + 1
√
2. T (n) = 2T (n/4) + n
3. T (n) = 2T (n/4) + n
4. T (n) = 2T (n/4) + n2

Solution: The master theorem is a tool used to analyze recurrence relations of the
form:
T (n) = aT (n/b) + f (n)

Here, a and b are positive constants, and f (n) is an asymptotically positive function.
The master theorem provides a framework for determining the asymptotic behavior of
the recurrence relation in terms of Big O notation. The theorem has three cases, and
a
the solution depends on comparing f (n) with a certain function related to nlogb
The master theorem is stated as follows:
(a) If f (n) = O(nlogb a−ϵ ) for some ϵ > 0 then T (n) = Θ(nlogb a ).

Page 2
(b) If f (n) = Θ(nlogb a ), then T (n) = Θ(nlogb a lg n).
(c) If f (n) = Ω(nlogb a+ϵ ) for some ϵ > 0 and if af (n/b) ≤ cf (n) for some constant c <
1 and all sufficiently large n, then T (n) = Θf (n).
Now, let’s analyze each of the given recurrences using the master theorem:
1. T (n) = 2T (n/4) + 1
Here, a = 2, b = 4, and f (n) = 1. The recurrence follows the form of the master
theorem with logb a = log4 2 = 1/2.
Comparing f (n) = 1 with nlogb a−ϵ = n1/2−ϵ for any ϵ > 0, we see that f (n) = O(n1/2−ϵ ).
Therefore, the first case of the master theorem applies.
The solution is T (n) = Θ(nlogb a ) = Θ(n1/2 ).
√
2. T (n) = 2T (n/4) + n
√
Here, a = 2, b = 4, and f (n) = n. The recurrence also follows the form of the master
theorem with logb a = log4 2 = 1/2.
√
Comparing f (n) = n with nlogb a = n1/2 , we see that f (n) = Θ(nlogb a ). Therefore,
the second case of the master theorem applies.
√
The solution is T (n) = Θ(f (n) log n) = Θ( n log n).
3. T (n) = 2T (n/4) + n
Here, a = 2, b = 4, and f (n) = n. The recurrence follows the form of the master
theorem with logb a = log4 2 = 1/2.
Comparing f (n) = n with nlogb a+ϵ = n1/2+ϵ for any ϵ > 0, we see that f (n) = Ω(n1/2+ϵ ).
Therefore, the third case of the master theorem applies.
The solution is T (n) = Θ(f (n)) = Θ(n).
4. T (n) = 2T (n/4) + n2
Here, a = 2, b = 4, and f (n) = n2 . The recurrence follows the form of the master
theorem with logb a = log4 2 = 1/2.
Comparing f (n) = n2 with nlogb a = n1/2 , we see that f (n) = Ω(n1/2+ϵ ) for any ϵ > 0.
Therefore, the third case of the master theorem applies.
The solution is T (n) = Θ(f (n)) = Θ(n2 ).

Page 3
CS412 Algorithms: Design & Analysis

Spring 2024

Dhanani School of Science and Engineering

Habib University

Copyright © 2024 Habib University

Practice Problems
Week 5 & 6

1. What does FIND-MAXIMUM-SUBARRAY return when all elements of A are negative?

Solution: It will return the least negative position. As each of the cross sums are
computed, the most positive one must have the shortest possible lengths. The algorithm
doesn’t consider length zero sub arrays, so it must have length 1.

2. Implement both the brute-force and recursive algorithms for the maximumsubarray problem
on your own computer. What problem size n0 gives the crossover point at which the
recursive algorithm beats the brute-force algorithm? Then, change the base case of the
recursive algorithm to use the brute-force algorithm whenever the problem size is less than
n0 . Does that change the crossover point?

Solution: The crossover point is at around a length 20 array, however, the times were
incredibly noisy and I think that there was a garbage collection during the run, so it is
not reliable. It would probably be more effective to use an actual profiler for measuring
runtimes. By switching over the way the recursive algorithm handles the base case,
the recursive algorithm is now better for smaller values of n. The chart included has
really strange runtimes for the brute force algorithm. These times were obtained on a
i7 10750H.
In the chart of runtimes, the x axis is the length of the array input. The y axis is the
measured runtime in nanoseconds.

3. Show that the solution to T (n) = 2T (⌊n/2⌋ + 17) is O(nlg(n)).

1
Solution: Choose n1 such that n ≥ n1 implies n/2 + 17 ≤ 3n/4. We’ll find c and d
such that T (n) ≤ cnlogn − d.

T (n) = 2T (⌊n/2⌋ + 17) + n

≤ 2(c(n/2 + 17)log(n/2 + 17) − d) + n

≤ cnlog(n/2 + 17) + 17clog(n/2 + 17) − 2d + n
≤ cnlog(3n/4) + 17clog(3n/4) − d + n
= cnlogn + cnlog(3/4) + 17clog(3n/4) − 2d + n
Take c = −2/log(3/4) and d = 34. Then we have T (n) ≤ cnlogn − d + 17clog(n) − n.
Since log(n) = o(n), there exists n2 such that ngeqn2 implies n ≥ 17clog(n). Letting
n0 = max{n1 , n2 } we have that n ≥ n0 implies T (n) ≤ cnlogn − d. Therefore T (n) =
O(nlogn).

4. Using the master method, you can show that the solution to the recurrence T (n) =
4T (n/2) + n2 is T (n) = Θ(n2 ). Show that a substitution proof with the assumption
T (n) ≤ cn2 fails. Then show how to subtract off a lower-order term to make a substi-
tution proof work.

Solution:
Suppose we want to use substitution to show T (n) ≤ cn2 for some c. Then we have

T (n) = 4T (n/2) + n

≤ 4(c(n/2)2) + n
= cn2 + n,
which fails to be less than cn2 for any c > 0. Next we’ll attempt to show T (n) ≤ cn2 −n.

T (n) = 4T (n/2) + n

≤ 4(c(n/2)2 − n) + n
= cn2 − 4cn + n
≤ cn2

Page 2
CS412 Algorithms: Design & Analysis

Spring 2024

Dhanani School of Science and Engineering

Habib University

Copyright © 2024 Habib University

Practice Problems
Week 7

1. Given an adjacency-list representation of a directed graph, how long does it take to compute
the out-degree of every vertex? How long does it take to compute the in-degrees?

Solution: Since it seems as though the list for the neighbors of each vertex v is just an
undecorated list, to find the length of each would take time O(out-degree(v)). So, the
total cost will be P v ∈ V O(outdegree(v)) = O(|E| + |V |). Note that the |V | showing
up in the asymptotics is necessary, because it still takes a constant amount of time to
know that a list is empty. This time could be reduced to O(|V |) if for each list in the
adjacency list representation, we just also stored its length.
To compute the in degree of each vertex, we will have to scan through all of the adjacency
lists and keep counters for how many times each vertex has appeared. As in the previous
case, the time to scan through all of the adjacency lists takes time O(|E| + |V |).

2. The transpose of a directed graph G = (V, E) is the graph GT = (V, E T ), where E T =

{(v, u) ∈ V × V : (u, v) ∈ E}. Thus, GT is G with all its edges reversed. Describe efficient
algorithms for computing GT from G, for both the adjacencylist and adjacency-matrix
representations of G. Analyze the running times of your algorithms.

Solution: For the adjacency matrix representation, to compute the graph transpose,
we just take the matrix transpose. This means looking along every entry above the
diagonal, and swapping it with the entry that occurs below the diagonal. This takes
time O(|V |2 ).
For the adjacency list representation, we will maintain an initially empty adjacency list
representation of the transpose. Then, we scan through every list in the original graph.
If we are in the list corresponding to vertex v and see u as an entry in the list, then we
add an entry of v to the list in the transpose graph corresponding to vertex u. Since
this only requires a scan through all of the lists, it only takes time O(|E| + |V |).

3. Most graph algorithms that take an adjacency-matrix representation as input require time
Ω(V 2 ), but there are some exceptions. Show how to determine whether a directed graph G
contains a universal sink-a vertex with in-degree |V | − 1 and out-degree 0 - in time O(V ),
given an adjacency matrix for G.

Solution: Start by examining position (1, 1) in the adjacency matrix. When examining
position (i, j), if a 1 is encountered, examine position (i + 1, j). If a 0 is encountered,
examine position (i, j + 1). Once either i or j is equal to |V |, terminate. I claim that
if the graph contains a universal sink, then it must be at vertex i. To see this, suppose

1
that vertex k is a universal sink. Since k is a universal sink, row k in the adjacency
matrix is all 0’s, and column k is all 1’s except for position (k, k) which is a 0. Thus,
once row k is hit, the algorithm will continue to increment j until j = |V |. To be sure
that row k is eventually hit, note that once column k is reached, the algorithm will
continue to increment i until it reaches k. This algorithm runs in O(V ) and checking
whether or not i in fact corresponds to a sink is done in O(V ). Therefore the entire
process takes O(V ).

4. Give an example of a directed graph G = (V, E), a source vertex s ∈ V , and a set of tree
edges Eπ ⊆ E such that for each vertex v ∈ V , the unique simple path in the graph (V, Eπ
from s to v is a shortest path in G, yet the set of edges Eπ cannot be produced by running
BFS on G, no matter how the vertices are ordered in each adjacency list.

Solution: Let G be the graph shown in the first picture, G′ = (V, Eπ ) be the graph
shown in the second picture, and 1 be the source vertex. Let’s see why Eπ can never
be produced by running BFS on G. Suppose that 2 precedes 5 in the adjacency list of
1. We’ll dequeue 2 before 5, so 3.π and 4.π must both equal 2. However, this is not the
case. Thus, 5 must have preceded 2 in the adjacency list. However, this implies that
3.π and 4.π both equal 5, which again isn’t true. Nonetheless, it is easily seen that the
unique simple path in G′ from 1 to any vertex is a shortest path in G.

Page 2
CS412 Algorithms: Design & Analysis

Spring 2024

Dhanani School of Science and Engineering

Habib University

Copyright © 2024 Habib University

Practice Problems
Week 8

1. Make a 3-by-3 chart with row and column labels W HIT E, GRAY , and BLACK. In each
cell (i, j), indicate whether, at any point during a depth-first search of a directed graph,
there can be an edge from a vertex of color i to a vertex of color j. For each possible edge,
indicate what edge types it can be. Make a second such chart for depth-first search of an
undirected graph.

Solution:

2. Show that edge (u, v) is

(a) a tree edge or forward edge if and only if u.d < v.d < v.f < u.f ,
(b) a back edge if and only if v.d ≤ u.d < u.f ≤ v.f , and
(c) a cross edge if and only if v.d < v.f < u.d < u : f .

Solution: a) Since we have that u.d < v.d, we know that we have first explored u
before v. This rules out back edges and rules out the possibility that v is on a tree
that has been explored before exploring u’s tree. Also, since we return from v before
returning from u, we know that it can’t be on a tree that was explored after exploring
u. So, This rules out it being a cross edge. Leaving us with the only possibilities of
being a tree edge or forward edge. To show the other direction, suppose that (u, v) is
a tree or forward edge. In that case, since v occurs further down the tree from u, we
know that we have to explored u before v, this means that u.d < v.d. Also, since we
have to of finished v before coming back up the tree, we have that v.f < u.f . The last
inequality to show is that v.d < v.f which is trivial.

b) By similar reasoning to part a, we have that we must have v being an ancestor

1
of u on the DFS tree. This means that the only type of edge that could go from u
to v is a back edge. To show the other direction, suppose that (u, v) is a back edge.
This means that we have that v is above u on the DFS tree. This is the same as the
second direction of part a where the roles of u and v are reversed. This means that the
inequalities follow for the same reasons.

c) Since we have that v.f < u.d, we know that either v is a descendant of u or it
comes on some branch that is explored before u. Similarly, since v.d < u.d, we either
have that u is a descendant of v or it comes on some branch that gets explored before
u. Putting these together, we see that it isn’t possible for both to be descendants of
each other. So, we must have that v comes on a branch before u, So, we have that u
is a cross edge. To See the other direction, suppose that (u, v) is a cross edge. This
means that we have explored v at some point before exploring u, otherwise, we would
have taken the edge from u to v when exploring u, which would make the edge either a
forward edge or a tree edge. Since we explored v first, and the edge is not a back edge,
we must of finished exploring v before starting u, so we have the desired inequalities.

3. Give an algorithm that determines whether or not a given undirected graph G = (V, E)
contains a cycle. Your algorithm should run in O(V ) time, independent of |E|.

Solution: We can’t just use a depth first search, since that takes time that could
be worst case linear in |E|. However we will take great inspiration from DFS, and just
terminate early if we end up seeing an edge that goes back to a visited vertex. Then, we
should only have to spend a constant amount of time processing each vertex. Suppose
we have an acyclic graph, then this algorithm is the usual DFS, however, since it is
a forest, we have |E| ≤ |V | − 1 with equality in the case that it is connected. So, in
this case, the runtime of O(|E| + |V |)O(|V |). Now, suppose that the procedure stopped
early, this is because it found some edge coming from the currently considered vertex
that goes to a vertex that has already been considered. Since all of the edges considered
up to this point didn’t do that, we know that they formed a forest. So, the number of
edges considered is at most the number of vertices considered, which is O(|V |). So, the
total runtime is O(|V |).

4. How can the number of strongly connected components of a graph change if a new edge is
added?

Solution: It can either stay the same or decrease. To see that it is possible to stay the
same, just suppose you add some edge to a cycle. To see that it is possible to decrease,
suppose that your original graph is on three vertices, and is just a path passing through
all of them, and the edge added completes this path to a cycle. To see that it cannot
increase, notice that adding an edge cannot remove any path that existed before. So,
if u and v are in the same connected component in the original graph, then there are a
path from one to the other, in both directions. Adding an edge wont disturb these two
paths, so we know that u and v will still be in the same SCC in the graph after adding
the edge. Since no components can be split apart, this means that the number of them
cannot increase since they form a partition of the set of vertices.

Page 2
5. Give an O(V + E)-time algorithm to compute the component graph of a directed graph
G = (V, E). Make sure that there is at most one edge between two vertices in the component
graph your algorithm produces.

Solution: Given the procedure given in the section, we can compute the set of vertices
in each of the strongly connected components. For each vertex, we will give it an
entry SCC, so that v.SCC denotes the strongly connected component (vertex in the
component graph) that v belongs to. Then, for each edge (u, v) in the original graph,
we add an edge from u.SCC to v.SCC if one does not already exist. This whole process
only takes a time of O(|V | + |E|). This is because the procedure from this section only
takes that much time. Then, from that point, we just need a constant amount of work
checking the existence of an edge in the component graph, and adding one if need be.

Page 3
CS412 Algorithms: Design & Analysis

Spring 2024

Dhanani School of Science and Engineering

Habib University

Copyright © 2024 Habib University

Practice Problems
Week 9

1. Show that splitting an edge in a flow network yields an equivalent network. More formally,
suppose that flow network G contains edge (u, v), and we create a new flow network G′ by
creating a new vertex x and replacing (u, v) by new edges (u, x) and (x, v) with c(u, x) =
c(x, v) = c(u, v). Show that a maximum flow in G′ has the same value as a maximum flow
in G.

Solution: To see that the networks have the same maximum flow, we will show that
every flow through one of the networks corresponds to a flow through the other. First,
suppose that we have some flow through the network before applying the splitting
procedure to the anti-symmetric edges. Since we are only changing one of any pair of
anti-symmetric edges, for any edge that is unchanged by the splitting, we just have an
identical flow going through those edges. Suppose that there was some edge (u, v) that
was split because it had an anti-symmetric edge, and we had some flow, f (u, v) in the
original graph. Since the capacity of both of the two edges that are introduced by the
splitting of that edge have the same capacity, we can set f ′ (u, v) = f ′ (u, x) = f ′ (x, v).
By constructing the new flow in this manor, we have an identical total flow, and we
also still have a valid flow.
Similarly, suppose that we had some flow f ′ on the graph with split edges, then, for any
triple of vertices u, x, v that correspond to a split edge, we must have that f ′ (u, x) =
f ′ (x, v) because the only edge into x is (u, x) and the only edge out of x is (x, v), and
the net flow into and out of each vertex must be zero. We can then just set the flow
on the unsplit edge equal to the common value that the flows on (u, x) and (x, v) have.
Again, since we handle this on an edge by edge basis, and each substitution of edges
maintains the fact that it is a flow of the same total, we have that the end result is also
a valid flow of the same total value as the original.
Since we have shown that any flow in one digraph can be translated into a flow of the
same value in the other, we can translate the maximum value flow for one of them to
get that it’s max value flow is ≤ to that of the other, and do it in the reverse direction
as well to achieve equality.

2. The Ford-Fulkerson algorithm is a widely used algorithm to solve the maximum flow problem
in a flow network. The maximum flow problem involves determining the maximum amount
of flow that can be sent from a source vertex to a sink vertex in a directed weighted graph,
subject to capacity constraints on the edges.
The algorithm works by iteratively finding an augmenting path, which is a path from the
source to the sink in the residual graph, i.e., the graph obtained by subtracting the current
flow from the capacity of each edge. The algorithm then increases the flow along this path
by the maximum possible amount, which is the minimum capacity of the edges along the

1
path.
Given a graph which represents a flow network where every edge has a capacity. Also, given
two vertices source s and sink t in the graph, find the maximum possible flow from s to t
with the following constraints:
1. Flow on an edge doesn’t exceed the given capacity of the edge.
2. Incoming flow is equal to outgoing flow for every vertex except s and t.

Solution:
1 # Python program for implementation
2 # of Ford Fulkerson algorithm
3 from collections import defaultdict
4
5 # This class represents a directed graph
6 # using adjacency matrix representation
7 class Graph :
8
9 def __init__ ( self , graph ) :
10 self . graph = graph # residual graph
11 self . ROW = len ( graph )
12 # self . COL = len ( gr [0])
13
14 ’’’ Returns true if there is a path from source ’s ’ to sink ’t ’ in
15 residual graph . Also fills parent [] to store the path ’’’
16
17 def BFS ( self , s , t , parent ) :
18
19 # Mark all the vertices as not visited
20 visited = [ False ]*( self . ROW )
21
22 # Create a queue for BFS
23 queue = []
24
25 # Mark the source node as visited and enqueue it
26 queue . append ( s )
27 visited [ s ] = True
28
29 # Standard BFS Loop
30 while queue :
31
32 # Dequeue a vertex from queue and print it
33 u = queue . pop (0)
34
35 # Get all adjacent vertices of the dequeued vertex u
36 # If a adjacent has not been visited , then mark it
37 # visited and enqueue it
38 for ind , val in enumerate ( self . graph [ u ]) :
39 if visited [ ind ] == False and val > 0:
40 # If we find a connection to the sink node ,
41 # then there is no point in BFS anymore
42 # We just have to set its parent and can return true
43 queue . append ( ind )
44 visited [ ind ] = True
45 parent [ ind ] = u
46 if ind == t :
47 return True

Page 2
48
49 # We didn ’t reach sink in BFS starting
50 # from source , so return false
51 return False
52
53
54 # Returns the maximum flow from s to t in the given graph
55 def FordFulkerson ( self , source , sink ) :
56
57 # This array is filled by BFS and to store path
58 parent = [ -1]*( self . ROW )
59
60 max_flow = 0 # There is no flow initially
61
62 # Augment the flow while there is path from source to sink
63 while self . BFS ( source , sink , parent ) :
64
65 # Find minimum residual capacity of the edges along the
66 # path filled by BFS . Or we can say find the maximum flow
67 # through the path found .
68 path_flow = float ( " Inf " )
69 s = sink
70 while ( s != source ) :
71 path_flow = min ( path_flow , self . graph [ parent [ s ]][ s ])
72 s = parent [ s ]
73
74 # Add path flow to overall flow
75 max_flow += path_flow
76
77 # update residual capacities of the edges and reverse edges
78 # along the path
79 v = sink
80 while ( v != source ) :
81 u = parent [ v ]
82 self . graph [ u ][ v ] -= path_flow
83 self . graph [ v ][ u ] += path_flow
84 v = parent [ v ]
85
86 return max_flow
87
88
89 # Create a graph given in the above diagram
90
91 graph = [[0 , 16 , 13 , 0 , 0 , 0] ,
92 [0 , 0 , 10 , 12 , 0 , 0] ,
93 [0 , 4 , 0 , 0 , 14 , 0] ,
94 [0 , 0 , 9 , 0 , 0 , 20] ,
95 [0 , 0 , 0 , 7 , 0 , 4] ,
96 [0 , 0 , 0 , 0 , 0 , 0]]
97
98 g = Graph ( graph )
99
100 source = 0; sink = 5
101
102 print ( " The maximum possible flow is % d " % g . FordFulkerson ( source , sink )
)
103
104 # This code is contributed by Neelam Yadav

Page 3
3. Given a weighted, directed graph G = (V, E) with no negative-weight cycles, let m be the
maximum over all vertices v ∈ V of the minimum number of edges in a shortest path from
the source s to v. (Here, the shortest path is by weight, not the number of edges.) Suggest
a simple change to the Bellman-Ford algorithm that allows it to terminate in m + 1 passes,
even if m is not known in advance.

Solution: Before each iteration of the for loop on line 2, we make a backup copy of
the current d values for all the vertices. Then, after each iteration, we check to see if
any of the d values changed. If none did, then we immediately terminate the for loop.
This clearly works because if one iteration didn’t change the values of d, nothing will
of changed on later iterations, and so they would all proceed to not change any of the
d values.

4. Suppose that a weighted, directed graph G = (V, E) has a negative-weight cycle. Give an
efficient algorithm to list the vertices of one such cycle. Prove that your algorithm is correct.

Solution: Begin by calling a slightly modified version of DFS, where we maintain the
attribute v.d at each vertex which gives the weight of the unique simple path from s to
v in the DFS tree. However, once v.d is set for the first time we will never modify it.
It is easy to update DFS to keep track of this without changing its runtime. At first
sight of a back edge (u, v), if v.d > u.d + w(u, v) then we must have a negative-weight
cycle because u.d + w(u, v) − v.d represents the weight of the cycle which the back edge
completes in the DFS tree. To print out the vertices print v, u, u.π, u.π.π, and so on
until v is reached. This has runtime O(V + E).

Page 4
CS412 Algorithms: Design & Analysis

Spring 2024

Dhanani School of Science and Engineering

Habib University

Copyright © 2024 Habib University

Practice Problems
Week 10

1. Show, by means of a counterexample, that the following “greedy” strategy does not always
determine an optimal way to cut rods. Define the density of a rod of length i to be pi = i,
that is, its value per inch. The greedy strategy for a rod of length n cuts off a first piece
of length i, where 1 ≤ i ≤ n, having maximum density. It then continues by applying the
greedy strategy to the remaining piece of length n − i.

Solution: Let p1 = 0, p2 = 4, p3 = 7 and n = 4. The greedy strategy would first cut

off a piece of length 3 since it has highest density. The remaining rod has length 1, so
the total price would be 7. On the other hand, two rods of length 2 yield a price of 8.

2. The Fibonacci numbers are defined by recurrence:

Fi = Fi−1 + Fi−2 for i ≥ 2

Give an O(n)-time dynamic-programming algorithm to compute the nth Fibonacci number.

Draw the subproblem graph. How many vertices and edges are in the graph?

Solution: The subproblem graph for n = 4 looks like:

The number of vertices in the tree to compute the nth Fibonacci will follow the recur-
rence
V (n) = 1 + V (n − 2) + V (n − 1)

And has initial condition V (1) = V (0) = 1. This has solution V (n) = 2 ∗ F ib(n) − 1
which we will check by direct substitution. For the base cases, this is simple to check.
Now, by induction, we have

V (n) = 1 + 2 ∗ F ib(n − 2) − 1 + 2 ∗ F ib(n − 1) − 1 = 2 ∗ F ib(n) − 1

1
The number of edegs will satisfy the recurrence

E(n) = 2 + E(n − 1) + E(n − 2)

and having base cases E(1) = E(0) = 0. So, we show by induction that we have
E(n) = 2 ∗ F ib(n) − 2. For the base cases it clearly holds, and by induction, we have

E(n) = 2 + 2 ∗ F ib(n − 1) − 2 + 2 ∗ F ib(n − 2) − 2 = 2 ∗ F ib(n) − 2

We will present a O(n) bottom up solution that only keeps track of the the two largest
subproblems so far, since a subproblem can only depend on the solution to subproblems
at most two less for Fibonacci.

3. Which is a more efficient way to determine the optimal number of multiplications in

a matrix-chain multiplication problem: enumerating all the ways of parenthesizing the
product and computing the number of multiplications for each, or running RECURSIVE-
MATRIX-CHAIN? Justify your answer.

Solution: The runtime of of enumerating is just n ∗ P (n), while is we were running

RECURSIVE-MATRIX-CHAIN, it would also have to run on all of the internal nodes of
the subproblem tree. Also, the enumeration approach wouldn’t have as much overhead.

4. Draw the recursion tree for the MERGE-SORT procedure from Section 2.3.1 on an array
of 16 elements. Explain why memoization fails to speed up a good divideand-conquer
algorithm such as MERGE-SORT.

Solution: Let [i..j] denote the call to Merge Sort to sort the elements in positions i
through j of the original array. The recursion tree will have [1..n] as its root, and at
any node [i..j] will have [i..(j − i)/2] and [(j − i)/2 + 1..j] as its left 4 and right children,
respectively. If j − i = 1, there will be no children. The memoization approach fails to
speed up Merge Sort because the subproblems aren’t overlapping. Sorting one list of
size n isn’t the same as sorting another list of size n, so there is no savings in storing
solutions to subproblems since each solution is used at most once.

5. Consider a variant of the matrix-chain multiplication problem in which the goal is to paren-
thesize the sequence of matrices so as to maximize, rather than minimize, the number of
scalar multiplications. Does this problem exhibit optimal substructure?

Solution: This modification of the matrix-chain-multiplication problem does still ex-

hibit the optimal substructure property. Suppose we split a maximal multiplication of
A1 , ..., An between Ak andAk+1 then, we must have a maximal cost multiplication on ei-
ther side, otherwise we could substitute in for that side a more expensive multiplication
of A1 , ..., An .

6. As stated, in dynamic programming we first solve the subproblems and then choose which
of them to use in an optimal solution to the problem. Professor Capulet claims that we
do not always need to solve all the subproblems in order to find an optimal solution. She

Page 2
suggests that we can find an optimal solution to the matrix-chain multiplication problem by
always choosing the matrix Ak at which to split the subproduct Ai Ai+1 ...Aj (by selecting
k to minimize the quantity pi−1 pk pj ) before solving the subproblems. Find an instance of
the matrix-chain multiplication problem for which this greedy approach yields a suboptimal
solution.

Solution: Suppose that we are given matrices A1 , A2 , A3 , and A4 with dimensions

such that p0 , p1 , p2 , p3 , p4 = 1000, 100, 20, 10, 1000. Then p0 pk p4 is minimized when
k = 3, so we need to solve the subproblem of multiplying A1 A2 A3 , and also A4 which
is solved automatically. By her algorithm, this is solved by splitting at k = 2. Thus,
the full parenthesization is (((A1 A2 )A3 )A4 ). This requires 1000 × 100 × 20 + 1000 ×
20ů × 10 + 1000ů × 10 × 1000 = 12, 200, 000 scalar multiplications. On the other hand,
suppose we had fully parenthesized the matrices to multiply as ((A1 (A2 A3 ))A4 ). Then
we would only require 100 × 20 × 10 + 1000 × 100 × 10 + 1000ů × 10ů × 1000 = 11, 020,
000 scalar multiplications, which is fewer than Professor Capulet’s method. Therefore
her greedy approach yields a suboptimal solution.

Page 3
CS412 Algorithms: Design & Analysis

Spring 2024

Dhanani School of Science and Engineering

Habib University

Copyright © 2024 Habib University

Practice Problems
Week 11

1. Why do we analyze the expected running time of a randomized algorithm and not its
worst-case running time?

Solution: We analyze the expected run time because it represents the more typical
time cost. Also, we are doing the expected run time over the possible randomness
used during computation because it can’t be produced adversarially, unlike when doing
expected run time over all possible inputs to the algorithm.

2. When RANDOMIZED-QUICKSORT runs, how many calls are made to the random number
generator RANDOM in the worst case? How about in the best case? Give your answer in
terms of Θ-notation.

Solution: In either case, Θ(n) calls are made to RANDOM. PARTITION will run
faster in the best case because the inputs will generally be smaller, but RANDOM is
called every single time RANDOMIZED-PARTITION is called, which happens Θ(n)
times.

3. Show that RANDOMIZED-SELECT never makes a recursive call to a 0-length array.

Solution: Calling a zero length array would mean that the second and third arguments
are equal. So, if the call is made on line 8, we would need that p = q − 1, which means
that q − p + 1 = 0. However, i is assumed to be a nonnegative number, and to be
executing line 8, we would need that i < k = q − p + 1 = 0, a contradiction. The
other possibility is that the bad recursive call occurs on line 9. This would mean that
q + 1 = r. To be executing line 9, we need that i > k = q − p + 1 = r − p. This would be
a nonsensical original call to the array though because we are asking for the ith element
from an array of strictly less size.

4. Argue that the indicator random variable Xk and the value max(k − 1, n − k) are indepen-
dent.

Solution: The probability that Xk is equal to 1 is unchanged when we know the max
of k − 1 and n − k. In other words, P (Xk = a|max(k − 1, n − k) = m) = P (Xk = a) for
a = 0, 1 and m = k − 1, n − k so Xk and max(k − 1, n − k) are independent. By C.3-5,
so are Xk and T (max(k − 1, n − k)).

5. Write an iterative version of RANDOMIZED-SELECT.

1
Solution:

6. Suppose we use RANDOMIZED-SELECT to select the minimum element of the array

A = {3, 2, 9, 0, 7, 5, 4, 8, 6, 1}. Describe a sequence of partitions that results in a worst-case
performance of RANDOMIZED-SELECT.

Solution: When the partition selected is always the maximum element of the array we
get worst-case performance. In the example, the sequence would be 9, 8, 7, 6, 5, 4, 3,
2, 1, 0.

Page 2