0DAA 2023 Key Answers PDF

PART-A Answer any five questions. Each question carries 2 marks. 1. What is an algorithm? An algorithm is defined as finite sequence unambiguous instructions followed to accomplish a given task. OR It is also defined as step by step procedure (instructions) to solve a given problem in finite numbe...

PART-A Answer any five questions. Each question carries 2 marks. 1. What is an algorithm? An algorithm is defined as finite sequence unambiguous instructions followed to accomplish a given task. OR It is also defined as step by step procedure (instructions) to solve a given problem in finite number of steps by accepting a set of inputs and producing the desired output. OR An algorithm is a finite set of instructions that, if followed, accomplishes a particular task. 2. What is time complexity of an algorithm?\ The amount of time taken by algorithm to run to completion is called time complexity of an algorithm. 3. Define graph. A graph G consists of two sets V and E. The set V is a finit, nonempty set of vertices. The set E is a set of pairs of vertices; these pairs are called edges. We write G=(V,E) to represent a graph. 4. What is a minimum spanning tree ? A minimum spanning tree(MST) of a given graph G is a spanning tree whose cost is minimum. 5. Define greedy method. A greedy method is a problem solving technique that always tries to find the best solution that works in stages, considering one input at a time with the hope that we get an optimal solution. A greedy method works as shown below:  At each stage, a decision is made whether selection of a particular input leads to an optimal solution.  If the inclusion of next input into the partially constructed optimal solution will result in an infeasible solution, then this input is not added to the partial optimized solution. Otherwise, it is added to the partial optimized solution.  A decision made in one stage is not changed in a later stage. So , each decision should assure feasibility. 6. What do you mean by divide and conquer technique? If the sub problems are relatively large then divide and conquer strategy is reapplied. The sub problem resulting from divide and conquer design are of the same type as the original problem. Generally divide and conquer problem is expressed using recursive formulas and functions. A general divide and conquer design strategy(control abstraction) is illustrated as given below- Algorithm DAndC (P) { if small(P) then return S(P) //termination condition else { Divide P into smaller instances P1, P2, P3… Pk k≥1; or 1≤k≤n Apply DAndC to each of these sub problems. Return Combine (DAndC(P1), DAndC (P2), DAndC (P3)… DAndC (Pk) } } PART-B 7. Write an algorithm for bubble sort and find its time complexity. 1 Algorithm Bubblesort(a[],n) 2 { 3 // Purpose: To sort the elements of the array 4 // Input : A is a un sorted array with n elements 1 5 // Output : A is an sorted array 6 For i:=1 to n do 7 { 8 Read a[i]; 9 } 10 For j :=1 to j=a[i+1] “ in the innermost for loop. Step 3: The number of comparisons depends on the value of n and the number of times the two for loops are executed. The total number of times the basic operation is executed can be obtained as shown below: 2 8. Solve the given Knapsack problem using Brute Force technique. (W,, W2. W3) (20, 25, 10) (P1, P2, P3) (30, 40, 35). M = 40 Solution: Capacity of the knapsack M=40 No, of elements n=3 Profits (p1,p2,p3) =(30,40,35) Weights(w1,w2,w3) =(20,25,10) To get the optimal solution arrange the objects in decreasing order of profit/weight as shown below: 𝑃1 30 𝑃2 40 = = 1.5 = = 1.6 𝑤1 20 𝑤2 25 = 1.5 𝑃3 35 = = 3.5 𝑤3 10 Arranging decreasing order of pi/wi we get. 3.5>1.6>1.5 With profits 35 40 30=(p1,p2,p3) With weights 10 25 20=(w1,w2,w3) Now the fractions of the objects selected and the profit we can get can be computed as shown below: Note: rc represents the remaining capacity of the knapsack. Objects Wi Pi X=1 or rc/wi Profit=x*Pi rc=rc-Wi*x (i) =40 Initial - - - - - =40 – 10 ∗ 1 Step 1 1 10 35 =1 1∗35=35 =30 =30 – 25 ∗ 1 Step 2 2 25 40 =1 1∗ 40 = 40 =5 =5/20=0.25 0.25∗ 30 = 7.5 =5 – 20 × 0.25 Step 3 3 20 30 =0 Profits=35+40+7.5=82.5 Fration(x1,x2,x3)=(1,1,0.25) Weights(w1,w2,w3)=(10,25,20) 3 9. Find the minimum spanning tree using Prim's algorithm for the below graph. Algorithm Prims() { visited:={0},min,mincost:=0,cost; Write "enter the number of nodes “; Read n; Write "enter the adjacency of matrix “; For i:=1 to i