Question Paper
Exam Date & Time: 21-Jun-2024 (02:30 PM - 05:30 PM)
MANIPAL ACADEMY OF HIGHER EDUCATION
FOURTH SEMESTER B.TECH. DEGREE EXAMINATIONS - JUNE 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) (4)
1B) (3)
1C) (3)
2A) Consider a directed acyclic graph (DAG) with 5 nodes labeled as A, B, C, D, and E. Here's the graph with its edges: (4)
A -> B, A -> C, B -> D, C -> D, D -> E
perform a topological sort on this graph using the source removal approach and DFS-based approach.
2B) Sort an array of integers: [5, 2, 4, 6, 1, 3] in ascending order using the insertion sort algorithm. Determine the total (3)
number of key comparisons and swaps required to sort the given array.
2C) Consider a scenario where a traveling salesman needs to visit 4 cities labeled A, B, C, and D. The distances (3)
between the cities are as follows:
A to B: 10 units, A to C: 15 units, A to D: 20 units, B to C: 35 units, B to D: 30 units, C to D: 25 units
Find the shortest possible route that visits each city exactly once and returns to the starting city using the exhaustive
search approach. Calculate the total number of permutations (possible routes) that need to be checked during this
exhaustive search.
3A) Construct a heap using bottom-up approach for the list (5)
51, 26, 11, 6, 8, 4, 31, 21, 9, 16. Provide a detailed analysis of heap construction technique using the bottom-up
construction method, focusing on worst-case complexity.
3B) Design 2-3 tree for the list 18, 32, 12, 23, 30, 10, 15, 20, 21, 24, 31, 40, 45, 47, 50, 52 using successive insertion, (3)
showing all stages. Page 1 of 3
showing all stages.
3C) Provide a comprehensive complexity analysis of the merge sort algorithm considering best and worst case. (2)
4A) Write the algorithm for the comparison counting sort for an array to arrange in ascending order and calculate the (3)
time complexity of it.
4B) Apply Horspool's algorithm to search for the pattern RAJKUMAR in the given text: (3)
KANNADA_FILM_INDUSTRY_ICON_IS_DR_RAJKUMAR
4C) Solve the graph shown in Figure 4C using Floyd's Algorithm and find the shortest path in the graph. (4)
5A) When can you call a graph as a minimum spanning tree? Apply Prim's algorithm to the graph shown in Figure 5A. (5)
Include in the priority queue all the vertices not already in the tree. List the edges included in the minimum spanning
tree thus obtained. Write the total cost of the minimum spanning tree.
5B) Apply backtracking technique to the problem of finding a Hamiltonian circuit in the graph shown in Figure 5B. Draw (3)
the state space tree. Use alphabetical order to resolve ties if any encountered.
5C) Describe the stages involved in a nondeterministic algorithm. (2)
Page 2 of 3
-----End-----
Page 3 of 3
