Design and Analysis of Algorithms — DU B. Voc – Software Development Previous Year Question Papers

b) What are Omega, Theta, Big-oh notations? Give an example for each 5 Explain the working ofBubble Sort for the given list [9, 8, 3, 6, 5, 2,10 5 by using a suitable example. Differentiate between NP-hard and NP-complete problems with 5 What is the difference between Greedy and Dynamic Programming 5 What is Linear Time Sorting? Sort the given list [402, 308, 334, 555, 77 7, 5 I12, 8881 using Radix Sort. Explain any one method to test Check whether the following graph is 8 Vertices: {A, B, C, D, E}, Edges: {(A,B), (A,C), (B,D), (C,D), (D,E)}. Define a Directed Acyclic Graph (DAG) and explain how to find its 7 Topological Ordering with an example. Explain the working of Quick Sort with the anay [8, 3, 1,7,0, 10,2] 8 using pivot : 8. Show all recursive steps. Derive and explain the average.case and worst-case time complexities of 7 Quick Sort. Apply Kruskal's algorithm to find the MST of this weighted graph: 8 Edge Weight b) Show detailed steps and {inal MST. Using the greedy algorithm approach, Solve a Fractional Knapsack 7 problem with 3 items (values = {40, 120, 80}, weights: {15, 25, 30}, Explain the Dynamic Programming approach for solving the 0/1 8 Knapsack problem with a numerical example: Items = {(weight, value)} : {(3, 13), (4,20), (5,30)}, Capacity: 8. Explain the Divide and Conquer strategy with a step-by-step illustration 7 of the Maximum Subarray Problem. Perform Bubble Sort on [8,4, 7,3,9], showing each pass. Analyse its 8 best, avetage, and worst-case time complexity. Write a python script to implement DFS algorithm for graphs and discuss 7 it's time complexity. Define NP-hard problems and explain why Subset Sum Problem is NP- 8 Explain the difference between Decision and Optimization problems 7 with suitable examples.