Question Paper
Exam Date & Time: 05-May-2024 (02:30 PM - 05:30 PM)
MANIPAL ACADEMY OF HIGHER EDUCATION
FOURTH SEMESTER B.TECH. DEGREE EXAMINATIONS - APRIL / MAY 2024
SUBJECT: CSE 2222/CSE-2222 - DESIGN AND ANALYSIS OF ALGORITHMS
(SPL: COMPUTER SCIENCE AND ENGINEERING - ARTIFICIAL INTELLIGENCE AND MACHINE LEARNING / COMPUTER
SCIENCE / COMPUTER SCIENCE AND ENGINEERING - CYBER SECURITY)
DESIGN AND ANALYSIS OF ALGORITHMS [CSE 2222]
Marks: 50 Duration: 180 mins.
A
Answer all the questions.
1A) Write a recursive algorithm to solve the tower of Hanoi problem. Set up and solve recurrence (4)
relation using backward substitution method.
1B) Write the pseudocode to find the GCD of two numbers using consecutive integer method. Compute (3)
the best case and worst-case time complexity of this algorithm.
1C) For each of the following functions, indicate how much the function's value will change if its (3)
argument is increased fourfold.
2A) Consider a simple text search feature in a word processing application using the brute force string (4)
matching algorithm. The user inputs a pattern to search for within a given text document. The text
document contains 1000 characters, and the pattern to search for is abc. Calculate the total number
of character comparisons needed by the brute force algorithm to search for the pattern within the
text document. Analyze its time complexity also.
2B) Consider a scenario where you have a knapsack with a capacity of 20 units and a list of items with their (3)
weights and values as follows:
Solve the above knapsack problem using the exhaustive search approach to find the optimal solution.
Calculate the total number of combinations that need to be checked during this exhaustive search.
2C) Sort an array of integers: [8, 5, 2, 9, 3] in ascending order using the bubble sort algorithm. (3)
Determine the total number of comparisons and swaps required to sort the given array.
3A) Enumerate the benefits of AVL trees over Binary search trees and demonstrate the construction of (5)
an AVL tree using the given list: 51, 26, 11, 6, 8, 4, 31, 21, 9, 16.
3B) Illustrate the best-case, average-case, and worst-case scenarios (input case) in the quicksort (3)
algorithm, including an example for each.
3C) Utilize a tree representation to depict the step-by-step process of heapsort for sorting the elements (2)
2, 9, 7, 6, 5, 8.
Page 1 of 2
4A) Assuming that the set of possible list values is {m, n, o, p}, sort the following list in alphabetical (3)
order by the distribution-counting sorting algorithm: n, o, p, o, n, m, m, n. Analyse the time
efficiency of this algorithm.
4B) A hash table of length m=11 is to be constructed by closed hashing. Show the hash table after (3)
inserting the keys 30, 20, 56, 75, 31, 19 into the empty hash table using the function h(K) = K mod
11. What is the load factor? Find the average number of key comparisons in a successful search in
this table.
4C) Solve the all-pairs shortest-path problem for the digraph with the following weight matrix. (4)
5A) What is a minimum spanning tree? Apply Kruskal's algorithm to find the minimum spanning tree of (5)
the graph shown in Figure 5A. Illustrate every step of edge inclusion diagrammatically. What is the
total cost of the minimum spanning tree obtained?
5B) Solve the following instance of the Assignment problem by the branch and bound technique. Draw (3)
the state space tree and show the optimal assignment.
5C) When can a decision problem D be said to be NP-complete? explain (2)
-----End-----
Page 2 of 2
