Course/ Batch: BTech/ SCSET Course Type: Core

Course Code: CSET244 Course Name: Design and Analysis of Algorithms

Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 1

Tutorial title: Running time of the loop execution of functions, Growth of functions

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓
Q2 ✓
Q3 ✓

Q1. Arrange the following list of functions in ascending order of growth.

𝑛 2
(a) 2√logn, 2n, n4/3, logn, nlogn, 22 , 2𝑛

(b) log(log2n), 1/n, √logn, 100, 2n, √n, n1/3

Q2. For the following functions, determine how many times will the print() statement be
executed? Give your answer in terms of n.
(a)
fun(n)
{
for (i=n/2; i>=1; i--)
for (j=2; j<=n; j=j*2)
print(“Nested loop execution”);
}

(b)
fun(n)
{
for(i =1; i<=n2; i++)
for (j=n; j>=1; j=j/2)
print(“Nested loop execution”);
}

Q3. Suppose that for inputs of size n on a particular computer, insertion sort runs in 8n2 steps
and merge sort runs in 64nlogn steps. For which values of n does insertion sort beat merge sort?
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 1

Tutorial title: Running time of the loop execution of functions, Growth of functions

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓
Q2 ✓
Q3 ✓

Q1. Arrange the following list of functions in ascending order of growth.

𝑛 2
(a) 2√logn, 2n, n4/3, logn, nlogn, 22 , 2𝑛

(b) log(log2n), 1/n, √logn, 100, 2n, √n, n1/3

Q2. For the following functions, determine how many times will the print() statement be executed? Give
your answer in terms of n.
(a)
fun(n)
{
for (i=n/2; i>=1; i--)
for (j=2; j<=n; j=j*2)
print(“Nested loop execution”);
}

(b)
fun(n)
{
for(i =1; i<=n2; i++)
for (j=n; j>=1; j=j/2)
print(“Nested loop execution”);
}

Q3. Let algorithms A and B have asymptotic running times TA(n) = 20n and TB(n) = 0.1nlog2n. For which
value of n does A outperform B?
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 1

Tutorial title: Running time of the loop execution of functions, Growth of functions

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓
Q2 ✓
Q3 ✓

Q1. Arrange the following list of functions in ascending order of growth.

(a) n0.01, log(n10), 2log2n , n!, nlogn , 2n, log10n

(b) √n, √logn, nn, log3n, nlogn, (1/3)n, n2/3

Q2. For the following functions, determine how many times will the print() statement be executed? Give
your answer in terms of n.
(a)
fun(n)
{
for (i=n/2; i>=1; i--)
for (j=2; j<=n; j=j*2)
print(“Nested loop execution”);
}

(b)
fun(n)
{
for(i =1; i<=n2; i++)
for (j=n; j>=1; j=j/2)
print(“Nested loop execution”);
}

Q3. Let algorithms A and B have asymptotic running times TA(n) = 20n and TB(n) = 0.1nlog2n. For which
value of n does A outperform B?
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 1

Tutorial title: Running time of the loop execution of functions, Growth of functions

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓
Q2 ✓
Q3 ✓

Q1. Arrange the following list of functions in ascending order of growth.

(a) n0.01, log(n10), 2log2n , n!, nlogn , 2n, log10n

(b) √n, √logn, nn, log3n, nlogn, (1/3)n, n2/3

Q2. For the following functions, determine how many times will the print() statement be
executed? Give your answer in terms of n.
(a)
fun(n)
{
for (i=n/2; i>=1; i--)
for (j=2; j<=n; j=j*2)
print(“Nested loop execution”);
}

(b)
fun(n)
{
for(i =1; i<=n2; i++)
for (j=n; j>=1; j=j/2)
print(“Nested loop execution”);
}

Q3. Suppose that for inputs of size n on a particular computer, insertion sort runs in 8n2 steps
and merge sort runs in 64nlogn steps. For which values of n does insertion sort beat merge sort?
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 1

Tutorial title: Running time of the loop execution of functions, Growth of functions

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓
Q2 ✓
Q3 ✓

Q1. Arrange the following list of functions in ascending order of growth.

𝑛 2
(a) (a) 2√logn, 2n, n4/3, logn, nlogn, 22 , 2𝑛

(b) log(log2n), 1/n, √logn, 100, 2n, √n, n1/3

Q2. For the following functions, determine how many times will the print() statement be
executed? Give your answer in terms of n.
(a)
fun(n)
{
for (i=n/2; i>=1; i--)
for (j=2; j<=n; j=j*2)
print(“Nested loop execution”);
}

(b)
fun(n)
{
for(i =1; i<=n2; i++)
for (j=n; j>=1; j=j/2)
print(“Nested loop execution”);
}

Q3. What is the smallest value of n such that an algorithm whose running time is 100n2 runs
faster than an algorithm whose running time is 2n on the same machine?
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 2

Tutorial title: Asymptotic notations: Big Oh, Theta, Omega

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓
Q2 ✓
Q3 ✓
Q4 ✓

Q1. Consider the following two claims:

(i) 2n + 1 = O(2n)?
(ii) 22n = O(2n)?
Which of these claims are correct?

Q2. Let f and g be functions of natural numbers given by f(n)=n2 and g(n)=n. Choose the appropriate
asymptotic notation(s) that makes the relation correct. Choose all answers that apply.
f(n) = ?(g(n))

Q3. Consider the following functions:

f(n) = 2n
g(n) = n!
h(n) = nlogn
Which of the following statements about the asymptotic behavior of f(n), g(n), and h(n) is true?
a) f(n) = O(g(n)); g(n) = O(h(n)) b) f(n) = Ω(g(n)); g(n) = O(h(n))
c) g(n) = O(f(n)); h(n) = O(f(n)) d) h(n) = O(f(n)); g(n) = Ω(f(n))

Q4. For each pair of functions, A and B, given in the table below, determine whether A is O, o, Ω, ω,
or Θ of B. Write your answers as “yes” or “no” in each corresponding box of the table. No justification
is required.
A B O o Ω ω Θ
n n
3 2
2
n logn n2
(log n)3 √n
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 2

Tutorial title: Asymptotic notations: Big Oh, Theta, Omega

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓
Q2 ✓
Q3 ✓
Q4 ✓

Q1. Consider the following two claims:

(i) 2n + 1 = O(2n)?
(ii) 22n = O(2n)?
Which of these claims are correct?

Q2. Let f and g be functions of natural numbers given by f(n)=n and g(n)=n2. Choose the appropriate
asymptotic notation(s) that makes the relation correct. Choose all answers that apply.
f(n) = ?(g(n))

Q3. Consider the following three functions

f(n)=3n√n
g(n)=2√nlog2n
h(n)=n!
Which of these claims is correct?
(i) h(n)=O(f(n))
(ii) h(n)=O(g(n))
(iii) g(n)!=O(f(n))
(iv) f(n)=O(g(n))

Q4. Consider the following two functions: f(n) = log2𝑛log27 and g(n) = log27log2𝑛; what is the asymptotic
relationship between f(n) and g(n)?
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 2

Tutorial title: Asymptotic Notations: Big Oh, Theta, Omega

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓
Q2 ✓
Q3 ✓
Q4 ✓

Q1. Consider the following two claims:

(i) 2n + 1 = O(2n)?
(ii) 22n = O(2n)?
Which of these claims are correct?

Q2. Consider the following two functions: f(n) = log2𝑛log27 and g(n) = log27log2𝑛; what is the asymptotic
relationship between f(n) and g(n)?

Q3. Consider the following three functions

f(n)=3n√n
g(n)=2√nlog2n
h(n)=n!
Which of these claims is correct?
(i) h(n)=O(f(n)) (ii) h(n)=O(g(n)) (iii) g(n)!=O(f(n)) (iv) f(n)=O(g(n))

Q4. Consider the following functions:

f(n) = 2n
g(n) = n!
h(n) = nlogn
Which of the following statements about the asymptotic behavior of f(n), g(n), and h(n) is true?
a) f(n) = O(g(n)); g(n) = O(h(n)) b) f(n) = Ω(g(n)); g(n) = O(h(n))
c) g(n) = O(f(n)); h(n) = O(f(n)) d) h(n) = O(f(n)); g(n) = Ω(f(n))
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 2

Tutorial title: Asymptotic Notations: Big Oh, Theta, Omega

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓
Q2 ✓
Q3 ✓
Q4 ✓

Q1. Consider the following two claims:

(i) 2n + 1 = O(2n)?
(ii) 22n = O(2n)?
Which of these claims are correct?

Q2. Let f and g be functions of natural numbers given by f(n)=n and g(n)=n2. Choose the appropriate
asymptotic notation(s) that makes the relation correct. Choose all answers that apply.
f(n) = ?(g(n))

Q3. Consider the following three functions

f(n)=3n√n
g(n)=2√nlog2n
h(n)=n!
Which of these claims is correct?
(i) h(n)=O(f(n)) (ii) h(n)=O(g(n)) (iii) g(n)!=O(f(n)) (iv) f(n)=O(g(n))

Q4. Consider the following functions:

f(n) = 2n
g(n) = n!
h(n) = nlogn
Which of the following statements about the asymptotic behavior of f(n), g(n), and h(n) is true?
a) f(n) = O(g(n)); g(n) = O(h(n)) b) f(n) = Ω(g(n)); g(n) = O(h(n))
c) g(n) = O(f(n)); h(n) = O(f(n)) d) h(n) = O(f(n)); g(n) = Ω(f(n))
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 2

Tutorial title: Asymptotic notations: Big Oh, Theta, Omega

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓
Q2 ✓
Q3 ✓
Q4 ✓

Q1. Consider the following two claims:

(i) 2n + 1 = O(2n)?
(ii) 22n = O(2n)?
Which of these claims are correct?

Q2. Let f and g be functions of natural numbers given by f(n)=n2 and g(n)=n. Choose the appropriate
asymptotic notation(s) that makes the relation correct. Choose all answers that apply.
f(n) = ?(g(n))

Q3. Consider the following functions:

f(n) = 2n
g(n) = n!
h(n) = nlogn
Which of the following statements about the asymptotic behavior of f(n), g(n), and h(n) is true?
a) f(n) = O(g(n)); g(n) = O(h(n)) b) f(n) = Ω(g(n)); g(n) = O(h(n))
c) g(n) = O(f(n)); h(n) = O(f(n)) d) h(n) = O(f(n)); g(n) = Ω(f(n))

Q4. For each pair of functions, A and B, given in the table below, determine whether A is O, o, Ω, ω,
or Θ of B. Write your answers as “yes” or “no” in each corresponding box of the table. No justification
is required.
A B O o Ω ω Θ
2 0.5
log n n
2
n nlogn
n 1/3
√log n
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 3

Tutorial title: Solving Recurrence Relation

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓ ✓
Q2 ✓ ✓
Q3 ✓ ✓
Q4 ✓ ✓

Q1. Let the recurrence relation T(n) = T(n-1) + T(n-2) - T(n-3) for n>3, and for n≤3 T(n)=n. Give (.)
bounds for T(n).

Q2. Solve the following recurrence relation using change of variable method and give a  bound for it.
T(n) = 2T(√n) + 1

Q3. Give (.) bounds for T(n) in each of the following recurrence relations using master theorem.
𝑛
(i) T(n) = 4T( ) + √n
16
𝑛
(ii) T(n) = 2T( 2) + nlogn

Q4. Find the (.) bounds for T(n) of the following recurrence relations using the recursion tree method.
T(n) = T(n/10) + T(9n/10) + n
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 3

Tutorial title: Solving Recurrence Relation

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓ ✓
Q2 ✓ ✓
Q3 ✓ ✓
Q4 ✓ ✓

Q1. Solve the following recurrence relations using substitution method and give a  bound for each of
them.
(i) T(n) = T(n-1) + n2 for n>0, with T(0)=10
(ii) T(n) = 3T(n – 1) + 1 for n >1, with T(1) = 1 and T(0)=0.

Q2. Solve the following recurrence relation using change of variable method and give a  bound for it.
T(n) = 2T(√n) + 1

Q3. Give (.) bounds for T(n) in each of the following recurrence relations using master theorem.
𝑛
(i) T(n) = 2T( ) + nlogn
2
𝑛
(ii) T(n) = 4T(16) + √n

Q4. Find the (.) bounds for T(n) of the following recurrence relations using the recursion tree method.
T(n) = T(n/3) + T(2n/3) + n
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 3

Tutorial title: Solving Recurrence Relation

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓ ✓
Q2 ✓ ✓
Q3 ✓ ✓
Q4 ✓ ✓

Q1. Solve the following recurrence relations using substitution method and give a  bound for each of
them.
(i) T(n) = T(n-1) + n2 for n>0, with T(0)=10
(ii) T(n) = 3T(n – 1) + 1 for n >1, with T(1) = 1 and T(0)=0.

Q2. Solve the following recurrence relation using change of variable method and give a  bound for it.
T(n) = √nT(√n) + n

Q3. Give (.) bounds for T(n) in each of the following recurrence relations using master theorem.
𝑛
(i) T(n) = 2T( ) + nlogn
2
𝑛
(ii) T(n) = 4T(16) + √n

Q4. Find the (.) bounds for T(n) of the following recurrence relations using the recursion tree method.
T(n) = T(n/3) + T(2n/3) + n
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 3

Tutorial title: Solving Recurrence Relation

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓ ✓
Q2 ✓ ✓
Q3 ✓ ✓
Q4 ✓ ✓

Q1. Let the recurrence relation T(n) = 5T(n-1) - 6T(n-2) for n>=2. Using mathematical induction, give (.)
bounds for T(n).

Q2. Solve the following recurrence relation using change of variable method and give a  bound for it.
T(n) = 2T(√n) + 1

Q3. Give (.) bounds for T(n) in each of the following recurrence relations using master theorem.
𝑛
(i) T(n) = 4T( ) + √n
16
𝑛
(ii) T(n) = 2T( 2) + nlogn

Q4. Find the (.) bounds for T(n) of the following recurrence relations using the recursion tree method.
T(n) = T(4n/5) + T(n/5) + n
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 3

Tutorial title: Solving Recurrence Relation

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓ ✓
Q2 ✓ ✓
Q3 ✓ ✓
Q4 ✓ ✓

Q1. Let the recurrence relation T(n) = 5T(n-1) - 6T(n-2) for n>=2, with T(0)=1 and T(1)=2. Give (.)
bounds for T(n).

Q2. Solve the following recurrence relation using change of variable method and give a  bound for it.
T(n) = √nT(√n) + n

Q3. Give (.) bounds for T(n) in each of the following recurrence relations using master theorem.
𝑛
(i) T(n) = 4T( ) + √n
16
𝑛
(ii) T(n) = 2T( 2) + nlogn

Q4. Find the (.) bounds for T(n) of the following recurrence relations using the recursion tree method.
T(n) = T(3n/4) + T(n/4) + n
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 4

Tutorial title: Recursive Algorithm, Divide and Conquer

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓ ✓
Q2 ✓ ✓
Q3 ✓ ✓
Q4 ✓ ✓

Q1. Give a recursive algorithm for binary search. Derive the recurrence for its worst-case running time.

Q2. Suppose that the partition algorithm of deterministic quick sort consistently splits the array into 1/10
and 9/10 portions. Then what will be the running time of the algorithm over an unsorted array of n
elements?

Q3. Suppose that all the elements of the array are equal. If we run randomized quick sort, find out its
recurrence.

Q4. Give a recurrence for the best-case running time of quick sort and an asymptotic tight bound on the
best-case running time.
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 4

Tutorial title: Recursive Algorithm, Divide and Conquer

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓ ✓
Q2 ✓ ✓
Q3 ✓ ✓
Q4 ✓ ✓

Q1. Give a recursive algorithm for linear search in an array. Derive the recurrence for its worst-case running
time.

Q2. Suppose that the partition algorithm of deterministic quick sort consistently splits the array into 1/10
and 9/10 portions. Write down the recurrence for it.

Q3. Suppose that all the elements of the array are equal. If we run deterministic quick sort, find out its
recurrence.

Q4. Give a recurrence for the worst-case running time of merge sort and an asymptotic tight bound on the
worst-case running time.
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 4

Tutorial title: Recursive Algorithm, Divide and Conquer

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓ ✓
Q2 ✓ ✓
Q3 ✓ ✓
Q4 ✓ ✓

Q1. Give a recursive algorithm for insertion sort in an array. Derive the recurrence for its worst-case
running time.

Q2. Suppose that the partition algorithm of deterministic quick sort consistently splits the array into 1/10
and 9/10 portions. Then what will be the running time of the algorithm over an unsorted array of n
elements?

Q3. Suppose that all the elements of the array are equal. If we run deterministic quick sort, find out its
recurrence.

Q4. Give a recurrence for the worst-case running time of merge sort and an asymptotic tight bound on the
worst-case running time.
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 4

Tutorial title: Recursive Algorithm, Divide and Conquer

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓ ✓
Q2 ✓ ✓
Q3 ✓ ✓
Q4 ✓ ✓

Q1. Give a recursive algorithm for bubble sort in an array. Derive the recurrence for its worst-case running
time.

Q2. Suppose that the partition algorithm of deterministic quick sort consistently splits the array into 1/10
and 9/10 portions. Then what will be the running time of the algorithm over an unsorted array of n
elements?

Q3. Suppose that all the elements of the array are equal. If we run randomized quick sort, find out its
recurrence.

Q4. Give a recurrence for the worst-case running time of quick sort and an asymptotic tight bound on the
worst-case running time.
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 4

Tutorial title: Recursive Algorithm, Divide and Conquer

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓ ✓
Q2 ✓ ✓
Q3 ✓ ✓
Q4 ✓ ✓

Q1. Give a recursive algorithm for selection sort in an array. Derive the recurrence for its worst-case
running time.

Q2. Suppose that the partition algorithm of deterministic quick sort consistently splits the array into 1/10
and 9/10 portions. Then what will be the running time of the algorithm over an unsorted array of n
elements?

Q3. Suppose that all the elements of the array are equal. If we run randomized quick sort, Give a recurrence
for the worst-case running time of quick sort and an asymptotic tight bound on the worst-case running time.

Q4. Give a recurrence for the best-case running time of quick sort and an asymptotic tight bound on the
best-case running time.
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 5

Tutorial title: Divide and Conquer

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓ ✓
Q2 ✓ ✓
Q3 ✓ ✓
Q4 ✓ ✓
Q5 ✓ ✓

Q1. You are given an array of n elements, and you notice that some of the elements are duplicates; that is, they
appear more than once in the array. Design an algorithm to remove all duplicates from the array in time
O(n log n). Justify that your algorithm runs in O(n log n) time in the worst case.

Q2. Given an array of n elements, decide whether the array has an element that appears more than n/2 times
in the array, and if so, find the element. If there are more than such element, report any one. Design and
analyze an algorithm that runs in O(n log n) time in the worst case.

Q3. Suppose there is an integer multiplication algorithm A that takes 8n1.5 single digit multiplications to
multiply two n-digit numbers, whereas another multiplication algorithm B (can be the classical high school
multiplication algorithm) takes n2 single digit multiplications. Find the crossover point for which algorithm A
asymptotically beats algorithm B.

Q4. A list of n names, each of length n, need to be sorted into dictionary order using the merge-sort algorithm.
What will be the worst case running time of this computation?

Q5. Consider sorting the following array A = {15, 25, 35, 55, 85, 90} in ascending order using deterministic
Quicksort algorithm that uses the last element as the pivot. What will be the number of swaps performed
during this Quicksort?
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 6

Tutorial title: Greedy method

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓ ✓
Q2 ✓ ✓
Q3 ✓ ✓
Q4 ✓ ✓

Q1. Consider the weights and values of the items listed below. The task is to pick a subset of these items
such that their total weight is no more than 11 Kgs and their total value is maximized. Moreover, a fraction
of each item may be taken. Find the optimal solution to the given problem.

Item Weights Values

Number (Kg.) (in Rs.)
1 10 60
2 7 28
3 4 20
4 2 24
5 8 48

Q2. i) How many bits are at least required for encoding the message ‘MISSISSIPPI’ using Huffman coding?
Construct the tree for optimal coding.
ii) Decode 100010111001010 using the Huffman code that you generated.
iii) Find the time complexity of constructing an optimal code using Huffman’s algorithm.
Q3. Given a set of 10 classes along with their start time (si) and finish time (fi), where si < fi.
Ai = {C1, C2, C3, C4, C5, C6, C7, C8, C9, C10}
Si = (1, 2, 3, 4, 7, 8, 9, 9, 11, 12)
Fi = (3, 5, 4, 7, 10, 9, 11, 13, 12, 14)
Suppose that you are in charge of scheduling a class into classrooms. At a time, only one class can be run
into a classroom. You are allowed to schedule a maximum number of classes in a classroom. Find the
minimum number of classrooms required to schedule all 10 classes without any conflict (non-overlapping
classes).

Q4. In the Traveling Salesman Problem (TSP), a salesman wants to visit each of n cities and return to his
starting point while traveling the shortest possible distance. The conditions of this tour are as follows:
• The salesman can visit each city exactly once.
• The goal is to find the best route that minimizes travel distance (or cost).

Consider the following distances between four cities:

City A B C D
A 0 20 15 30
B 20 0 25 35
C 15 25 0 20
D 30 35 20 0

The above matrix is symmetric in which every element denotes the distance between two cities, e.g., (i, j)
denotes the distance between city i and j. Every city is connected to other cities. Consider the following
greedy method:
1. Select a starting city.
2. Find the nearest city to your current one and go there if it was not visited earlier.
3. If there are still cities not yet visited, repeat step 2. Else, return to the starting city.
If the salesman wants to start his tour from city A, find the minimum total travel distance of his tour using
the greedy method described above. Write the sequence of the cities that the salesman would visit.

Q5. Given a graph, your goal is to color the vertices with a minimum number of colors so that the end points
of every edge are colored differently (i.e., no adjacent vertex has the same color). Consider the following
greedy heuristic to color the graph.
• Step 1: All vertices are sorted according to the decreasing value of their degree in a list V = { v1,
v2, . . . , vn }.
• Step 2: Colors are ordered in a list C = {c1, c2, c3,… }.
• Step 3: The first non-colored vertex v in V is colored with the first available color in
C. Available means a color that was not previously used.
• Step 4: The remaining part of the ordered list V is traversed, and the same color is allocated to
every vertex for which no adjacent vertex has the same color.
• Step 5: Steps 3 and 4 are applied iteratively until all the vertices have been colored.
Consider the following graphs. Apply the above heuristic to the following graphs and determine the number
of colors required to color the graphs. Does greedy coloring always give optimal coloring?

V2 V1 V2
V1

V4
V3

V4 V3 V6

V6
V5
V5
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 7

Tutorial title: Minimum Spanning Tree

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓ ✓
Q2 ✓ ✓
Q3 ✓ ✓
Q4 ✓ ✓
Q5 ✓ ✓

Q1. Consider the following weighted graph:

(a) Find the cost of the minimum weighted spanning tree.

(b) Find the number of distinct minimum spanning trees.

Q2. Given a connected, undirected graph. Give an algorithm to detect whether there is a cycle. Analyze the
running time of your algorithm.
Q3. Consider the following weighted graph:

(a) What is the cost of the minimum weighted spanning tree?

(b) How many minimum spanning trees does it have?
(c) Suppose Kruskal’s algorithm is run on this graph. In what order are the edges added to the MST?
(d) Suppose Prim’s algorithm is run on this graph. In what order are the edges added to the MST?

Q4. The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree
(MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D, F)}. The edge weights of
only those edges which are in the MST are given in the figure shown below. Find the minimum possible sum
of weights of all 8 edges of this graph.

Q5. Consider the following undirected graph G:

Choose a value for x that will maximize the number of minimum weight spanning trees (MWSTs) of G. The
number of MWSTs of G for this value of x is ____.
 1. Consider the following directed graph with zero-weight edges:
A → B (4)
A → C (0)
C → D (0)
D → E (5)
B → E (2)
If we apply Dijkstra’s algorithm starting from A, what will be the shortest distance to E?
A) 4
B) 2
C) 5
D) 6

2. Suppose we modify Dijkstra’s algorithm to allow negative weights by ignoring already processed
nodes when a shorter path is found. What will be the consequence?
A) The algorithm will run in O(n log n) time instead of O(m + n log n).
B) The algorithm will still find the correct shortest paths for all nodes.
C) The algorithm may fail to find correct shortest paths.
D) The algorithm will work only if there are no negative-weight cycles.
3. Using a Fibonacci Heap, what is the best possible time complexity of Dijkstra’s algorithm for a
graph with n vertices and m edges?

A) O(n log n + m)
B) O(m + n log n)
C) O(n log n + m log m)
D) O(m log n)
4. Dijkstra’s Algorithm maintains a parent array to reconstruct the shortest path from source to
destination. Given the following graph:

A → B (2)
A → C (4)
B → C (1)
B → D (7)
C → D (3)
D → E (1)

If we run Dijkstra’s Algorithm from A to E, what is the shortest path and its total cost?
A) A → B → C → D → E, cost = 7
B) A → C → D → E, cost = 8
C) A → B → D → E, cost = 10
D) A → C → E, cost = 6

5. A graph with n nodes and m edges contains edges with weight 1, 2, or 3 only. What is the best
approach to compute shortest paths from a source node?

A) Standard Dijkstra’s Algorithm using a Priority Queue

B) Bellman-Ford Algorithm
C) Dijkstra’s Algorithm using a 0-1 BFS-like approach
D) Floyd-Warshall Algorithm
6. A graph has 1000 nodes and 499,500 edges (almost a complete graph). Which of the
following is the tightest bound on the time complexity of Dijkstra’s algorithm using a Fibonacci
Heap?

(A) O(V2)
(B) O(E+VlogV)
(C) O(VlogV+ElogV)
(D) O(ElogV)
7. A directed graph contains some edges with zero weight. In order to ensure correctness, a
transformation is applied before running Dijkstra’s Algorithm. What transformation ensures
correct results?

(A) Replace all zero-weight edges with a very small positive value (e.g., 10−610^{-6}10−6).
(B) Treat zero-weight edges as unweighted and apply BFS instead.
(C) Convert all zero-weight edges to positive weight edges by adding a constant to all edges.
(D) Use Bellman-Ford Algorithm instead.
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 9

Tutorial title: BFS and DFS

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓ ✓ ✓
Q2 ✓ ✓ ✓
Q3 ✓ ✓ ✓
Q4 ✓ ✓ ✓
Q5 ✓ ✓

Q1. For the given directed graph, determine the BFS

and DFS traversal sequences starting from node A.

Q 2 Anjali has enrolled for a part-time Masters programme where she has to complete 8 courses, numbered
1, 2, . . . , 8. Each course takes a full semester to complete. She can take as many or as few courses as
she wants in each semester.
Some courses are prerequisites for other courses. If course A is a prerequisite for course B, she can
take course B the semester after she finishes course A, or any time after that, but not before.
Given the following information about prerequisites, compute the minimum number of semesters she
needs to complete these courses
• Prerequisites for course 1: course 2,4,5,7
• Prerequisites for course 2: course 3
• Prerequisites for course 3: course 5,6
• Prerequisites for course 4: course 8
• Prerequisites for course 5: course 8
• Prerequisites for course 6: course 7,8
 a) 3
b) 4
c) 5
d) 6

Q 3. A computer network is represented as a given graph, where each Computer is a node, and a direct
connection between two computers is an edge. The system
administrator wants to check if there is a redundant connection
(i.e., if a cycle exists in the network).

Q4. A city has 7 major intersections labelled A to G, connected by a complex network of roads. The city's traffic
department is conducting a study to identify critical intersections that, if blocked due to construction, accidents,
or natural disasters, could severely impact traffic flow. In addition, the city's emergency response team needs a
plan to ensure uninterrupted access to all areas in case of road closures. Some intersections are also near
hospitals, fire stations, and police headquarters, making their accessibility even more critical.
Your task is to identify all critical intersections whose removal would disconnect parts of the city. The road
network is represented using the following adjacency matrix, where a 1 indicates a direct road connection
between two intersections:

A B C D E F G
A 0 1 1 0 0 0 0
B 1 0 1 0 1 0 0
C 1 1 0 1 0 0 0
D 0 0 1 0 1 1 1
E 0 1 0 1 0 0 0
F 0 0 0 1 0 0 1
G 0 0 0 1 0 1 0

Q5. Let G be a directed graph and T a depth-first search (DFS) spanning tree in G that is rooted at a vertex v.
Suppose T is also a breadth-first search (BFS) tree in G, rooted at v. Which of the following statements
is/are true for every such graph G and tree T?*
A. There are no back-edges in G with respect to the tree T.
B. There are no cross-edges in G with respect to the tree T.
C. There are no forward-edges in G with respect to the tree T.
D. The only edges in G are the edges in T.
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 10

Tutorial title: Dynamic Programming

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓ ✓
Q2 ✓ ✓
Q3 ✓ ✓
Q4 ✓ ✓
Q5 ✓ ✓

Q1. Find the optimal solution for 0/1 knapsack problem

(w1, w2, w3) = (2, 3, 3)
(p1, p2, p3) = (1, 2, 4) and W = 6

Q2. Consider the weights and values of items listed below. Note that there is only one unit of each item.

Item Weight Value ( in

No. Rupees)
1 10 60
2 7 28
3 4 20
4 2 24

The task is to pick up a subset of these items such that their total weight is no more than 11 Kgs and their
value is maximized. Moreover, no item may be split. The total value of the items picked by an optimal
algorithm is denoted by Vopt. A greedy algorithm sorts the item by their value to weight ratios in descending
order and packs them greedily, starting from the first item in the ordered list. The total value of the item picked
by the greedy algorithm is denoted by Vgreedy. Find the value of Vopt – Vgreedy.
Q3. Determine the length of Longest Common Subsequence of <1,0,0,1,0,1,0,1> and <0,1,0,1,1,0,1,1,0>
and state the subsequences.

Q4. Consider two strings A= <q p q r r> and B = <p q p r q r p>. Let X be the length of the LCS between A
and B and Y be the number of longest common subsequences between A and B, then find the value of
X +10Y
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 11

Tutorial title: Dynamic Programming

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓ ✓ ✓
Q2 ✓ ✓
Q3 ✓ ✓
Q4 ✓ ✓
Q5 ✓ ✓ ✓

Q1. A hospital maintains a patient database that undergoes multiple stages of transformation before
generating a final report. The data is processed in four steps, each represented as a matrix:
• Step 1: The raw patient data is stored in a structured format with 10 attributes (such as age, weight,
and BP) and 5 key identifiers (like patient ID, admission date, etc.). (Matrix A1, size 10×5).
• Step 2: The data is mapped to a medical coding system that expands it into 20 different medical codes
used for diagnosis and billing. (Matrix A2, size 5×20).
• Step 3: The coded data is passed through a risk prediction model, which reduces the dimensionality to
10 key risk indicators. (Matrix A3, size 20 x 10).
• Step 4: A final transformation prepares the data for report generation, reducing it to 5 key metrics used
by doctors and insurance providers. (Matrix A4, size 10 ×5).
To ensure efficient processing, we need to determine the optimal order of matrix multiplications that
minimizes the number of scalar computations required to transform the data through all stages. What is the
minimum number of scalar multiplications required to compute the final processed output?

Q2. Compute the binomial coefficient 𝐶(6,3) using dynamic programming based on Pascal's Identity.

Q3. Consider the dynamic programming approach to calculate the binomial coefficient 𝐶(𝑛, 𝑘) using
Pascal's Identity. Which of the following statements is TRUE?
(A) The base case for the recursion is 𝐶(𝑛, 𝑘) = 1 if 𝑛 = 𝑘 or 𝑘 = 0.
(B) The recurrence relation used is 𝐶(𝑛, 𝑘) = 𝐶(𝑛 + 1, 𝑘 − 1) + 𝐶(𝑛 + 1, 𝑘).
(C) The time complexity of the dynamic programming solution to calculate 𝐶(𝑛, 𝑘) is exponential in terms
of n.
(D) The dynamic programming approach avoids redundant calculations by storing the results of
subproblems.

Q4. If you implement the bottom-up dynamic programming approach to find 𝐶(𝑛, 𝑘), approximately how
many addition operations will be performed to fill the DP table?

(A) 𝑂(𝑛)
(B) 𝑂(𝑘)
(C) 𝑂(𝑛 × 𝑘)
(D) 𝑂(𝑛 + 𝑘)

Q5. A logistics company manages four warehouses (labeled 1, 2, 3, and 4) and tracks the shipping costs
between them. The table below shows the direct shipping costs (in dollars) between warehouses, where ∞
means no direct shipping route exists:

1 2 3 4
1 0 8 ∞ 1
2 ∞ 0 1 ∞
3 4 ∞ 0 ∞
4 ∞ 2 9 0

To optimize shipping costs, the company applies the Floyd-Warshall algorithm to determine the minimum
cost to transport goods from warehouse 4 to warehouse 3 after considering all possible routes. What is the
lowest shipping cost?
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 12

Tutorial title: Backtracking

CO Mapping

Question no CO1 CO2 CO3

Q1 ✓ ✓
Q2 ✓ ✓
Q3 ✓ ✓
Q4 ✓ ✓

Q1 What among the alternatives makes the best solution/option, when considering the 4 queens
problem?

A. (2,3,1,4)
B. (4,3,2,1)
C. (3,1,4,2)
D. (4,2,3,1)

Q2. The chromatic number of a graph is the minimum number of colours used in a proper colouring of the
graph. Let G be any graph with n vertices and chromatic number k. Which of the following statements
is/are always TRUE?
A. G contains a complete subgraph with k vertices
B. G contains an independent set of size at least n/k
C. G contains at least k(k−1)/2 edges
D. G contains a vertex of degree at least k

Q3 The minimum number of colours required to colour the following graph, such that no two adjacent vertices are
assigned the same colour, is
A. 2
B. 3
C. 4
D. 5

Q4. Let G be an undirected complete graph on n vertices, where n>2. Then, the number of different
Hamiltonian cycles in G is equal to
A. n!
B. (n−1)!
C. 1
D. (n−1)!2

Q5 the given undirected graph G(V, E) and its adjacency matrix are as follows −

The backtracking algorithm can be used to find a Hamiltonian path in the above graph. If found, the
algorithm returns the path. If not, it returns false. Find the Hamiltonian path in the above graph.
 Course/ Batch: BTech/ SCSET Course Type: Core
Course Code: CSET244 Course Name: Design and Analysis of Algorithms
Semester: Even
Session: 2024-2025

Tutorial Assignment: Week 13

Tutorial title: NP Complete, NP Hard

CO Mapping

Q1. Ram and Shyam have been asked to show that a certain problem Π is NP-complete.
Ram shows a polynomial time reduction from the 3-SAT problem to Π, and Shyam
shows a polynomial time reduction from Π to 3-SAT. Which of the following can be
inferred from these reductions ?

A. Π is NP-hard but not NP complete

B. Π is in NP, but is not NP-complete
C. Π is NP-complete
D. Π is neither NP-hard, nor in NP complete

Q2. The problems are 3-SAT and 3SAT are

A. Both in P
B. Both NP complete
C. NP-complete and in p respective
D. Undecidable and NP complete Respective
Q3. The subset-sum problem is defined as follows:
Given a set S of n positive integers and a positive integer W, determine whether there is a subset of S
Whose elements sum to W. An algorithm Q solves this problem in O(nW) time. Which of the
following statements is false?

A. Q solves the subset-sum problem in polynomial time when the input is encoded in Unary
B. Q solves the subset-sum problem in polynomial time when the input is encode in binary
C. The subset sum problem belongs to the class NP
D. The subset problem is NP hard

Q4. Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G = (V, E) with |V| divisible
by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which
one of the following is true?

A. Both SHAM3and DHAM3are NP hard

B. SHAM3 is NP hard, DHAM3 but is not
C. DHAM3 is NP hard, SHAM3 but is not
D. Neither SHAM3 Nor DHAM3 is NP hard