MCA I (First) Semester Examination 2023-24
Course Code: MCA117 Paper ID: 08723122
Data Structures & Algorithms
Time: 3 Hours Max. Marks: 60
Note: Attempt all questions.
Q1. Answer the following (limit your answer to 50 words): Marks
a) What is the definition of asymptotic notation? 2
Or
Explain the difference between Big O, Big Omega, and Theta notation. 2
b) What is the traveling salesman problem (TSP)? 2
Or
Compare between BFS & DFS. 2
c) Explain the difference between the Held-Karp algorithm and the Christofides algorithm 2
for solving the TSP.
Or
What are the characteristics of Kruskal algorithms? 2
d) Explain why the greedy algorithm for the Activity Selection Problem is not always 2
optimal.
Or
Define Knapsack problem. 2
e) What are the characteristics of Randomized Algorithms? 2
Or
What is string matching? 2
2. Compare and contrast the time complexity of the bubble sort and insertion sort 10
algorithms.
Or
Compare and contrast the space complexity of the following two algorithms for finding 10
the maximum value in an array: 1. max = arr[0]; for (i = 1; i< n; i++) { if (arr[i] > max) { max =
arr[i]; }} and 2. Sort the array and return the last element.
3. State the 2-opt algorithm to slow an approximate solution to the TSP. 10
Or
Given a weighted graph and a source vertex in the graph, find the shortest paths from 10
the source to all the other vertices in the given graph.
12
4. Write an algorithm to solve the Assembly Line Scheduling problem using dynamic 10
programming.
Or
Write an algorithm to solve the subset sum problem using backtracking. 10
5. A B-tree of order 4 is built from scratch by 10 successive insertions. What is the 10
maximum number of nodes splitting operations that may take place?
Or
Compare and contrast the advantages and disadvantages of Red-Black Trees. In what 10
scenarios would one be preferred over the other (B tree or Red Black tree).
6. Explain the applicability of string-matching algorithms in various computational tasks. 10
Or
Explain the advantages and disadvantages of using randomized algorithms. 10
