11/8/24, 1:00 PM ESA - DEC 2023 - Minor - UE22CS241BX (set- 1)
PES University, Bengaluru
(Established under Karnataka Act 16 of 2013)
END SEMESTER ASSESSMENT (ESA) - DEC 2023
UE22CS241B. - Design and Analysis of Algorithms
Total Marks : 100.0
1.a. Define Asymptotic notation.Explain Asypmtotic notations in detail
with example. (8.0 Marks)
1.b. Design a non recursive algorithm for matrix multiplication and
calculate its time complexity (6.0 Marks)
1.c. Consider the following version of an algorithm.
Algorithm GE(A[0..n − 1, 0..n])
//Input: An n-by-n + 1 matrix A[0..n − 1, 0..n] of real numbers
for i ← 0 to n − 2 do
for j ← i + 1 to n − 1 do
for k ← i to n do
A[j, k] ← A[j, k] − A[i, k] ∗ A[j, i] / A[i, i]
a. Find the time efficiency class of this algorithm.
b.What glaring inefficiency does this pseudocode contain and how can it
be eliminated to speed the algorithm up (5.0 Marks)
about:blank 1/6
11/8/24, 1:00 PM ESA - DEC 2023 - Minor - UE22CS241BX (set- 1)
1.d. Outline an algorithm to sort n elements using bubble sort and obtain
its time complexity. (6.0 Marks)
2.a. Design a recursive algorithm for Binary search and calcuate its time
complexity (6.0 Marks)
2.b. Apply Quick sort on the following set of elements::
51,95,66,72,42,38,39,41,15 (6.0 Marks)
about:blank 2/6
11/8/24, 1:00 PM ESA - DEC 2023 - Minor - UE22CS241BX (set- 1)
2.c. Traverse the following binary tree
a.. in preorder. b. in inorder. c. in postorder
(4.0 Marks)
2.d. List out the advantages and disadvantages of divide and conquer
approach. (4.0 Marks)
2.e. Apply the DFS-based algorithm to solve the topological sorting
problem for the following digraph:
(5.0 Marks)
about:blank 3/6
11/8/24, 1:00 PM ESA - DEC 2023 - Minor - UE22CS241BX (set- 1)
3.a. Sort the following lists by heapsort by using the array representation
of heaps
i) S, O, R, T, I, N, G (in alphabetical order) (4.0 Marks)
3.b. Draw diagrams of the single L-rotation and of the double RL-rotation
in their general form.construct an AVL tree by inserting the following
elements successively, starting with the empty tree.
6, 5, 4, 3, 2, 1 (5.0 Marks)
3.c. Solve the following instances of the single-source shortest-paths
problem with vertex a as the source
(6.0 Marks)
about:blank 4/6
11/8/24, 1:00 PM ESA - DEC 2023 - Minor - UE22CS241BX (set- 1)
3.d. a.Construct a Huffman code for the following data:
character A B C D -
Probability 0.4 0.1 0.2 0.15 0.15
b.Encode the text ABACABAD using the code of question a.
c. Decode the text whose encoding is 100010111001010 in the code of
question a (6.0 Marks)
3.e. Consider the algorithm for the sorting problem that sorts an array by
counting, for each of its elements, the number of smaller elements and
then uses this information to put the element in its appropriate position
in the sorted array:
Algorithm ComparisonCountingSort(A[0..n − 1], S[0..n − 1])
//Sorts an array by comparison counting
//Input: Array A[0..n − 1] of orderable values
//Output: Array S[0..n − 1] of A’s elements sorted in nondecreasing order
for i ← 0 to n − 1 do
Count[i] ← 0
for i ← 0 to n − 2 do
for j ← i + 1 to n − 1 do
if A[i] < A[j]
Count[j] ← Count[j]+1
else
Count[i] ← Count[i]+1
for i ← 0 to n − 1 do
S[Count[i]] ← A[i]
a.Apply this algorithm to sorting the list 60, 35, 81, 98, 14, 47.
b. Is this algorithm stable?
c. Is it in place? (4.0 Marks)
4.a. Write a pseudocode of the bottom-up dynamic programming
algorithm for the knapsack problem. (5.0 Marks)
about:blank 5/6
11/8/24, 1:00 PM ESA - DEC 2023 - Minor - UE22CS241BX (set- 1)
4.b. Solve the all-pairs shortest path problem for the digraph with the
following weight matrix
(5.0 Marks)
4.c. a.What is Hamiltonian Cycle.
b. Explain the classes of NP-Hard and NP-Complete. (7.0 Marks)
4.d. Solve the following assignment problem using Branch and bound
technique
(8.0 Marks)
about:blank 6/6
