Design And Analysis Of Algorithm 2024 – BSc Computer Science Part 3

Total No. of Questions : 8] [Total No. of Printed Pages : 4

Paper code: 13524
1524
B.Sc. (Computer Science) (Part 3)
Examination, 2024
Paper No. 2.3
DESIGN AND ANALYSIS OF ALGORITHM

Time: 3 Hours] [Maximum Marks: 50

Note: Attempt any five questions. All questions carry equal marks.

1. (a) Discuss the process of designing an algorithm. Explain different types of asymptotic notation with example.5

    (b) Apply Quick sort algorithm for the following example 25, 36, 12, 4, 5, 16, 58, 54, 24, 16, 9, 65, 78.5

2. Define minimum cost spanning tree. Apply Kruskal’s and prims algorithm to find minimum cost spanning tree and compare it for better performance.

3. (a) State Matrix chain Multiplication problem. How to solve this problem by Dynamic programming? Explain.5

    (b) Write and explain Traveling Salesperson problem with the help of suitable example.5

4. (a) What is the solution generated by function job Sequencing algorithm when n = 6 (p1…..p6) = (3, 5, 20, 18, 1, 6) 2 and (d1….d6) = (1, 3, 4, 3, 2, 1).5

    (b) Illustrate the operation of Radix – Sort on the following list of English words -COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX.5

5. (a) What is Divide and conquer Strategy? Explain counting -Sort algorithm with example.

    (b) Explain Huffman codes to generate the optimal prefix codes.

6. (a) How 8-Queen’s problem can be solved using back tracking, explain with an example.5

    (b) Generate the Optimal Tour Using LC-Branch and Bound for the given adjacency matrix, [∞ 10 11 6 18, 15 ∞ 16 4 2, 3 5 ∞ 24, 19 6 18 ∞ 3, 16 4 7 16 ∞].5

7. (a) Use an algorithm for greedy strategies for the knapsack to find an optimal solution to the knapsack instance n=7, m=15, (p1, p2…….p7)=(10, 5, 15, 7, 6, 18, 3) and (w1, w2,….w7)=(2,3,5,7,1,4,1).5

    (b) Using Master’s Method, solve the following recurrence: T(n) = 7T(n/2) + 18n².5

8. Write short notes on any two of the following :10

    (i) Dijkastra’s Method

    (ii) Breadth First Search

    (iii) Depth First Search

………………END………………

Thank you Neeraj 🙂