bank pages. ton, appeal to evaluator and for equations written eg, 42+8 = 50, will be treated as malpractice. 1g your answers, compulsorily draw diagonal cross lines on the remain Important Note : 1, On complet Ce GS Seietls USN | 15CS43 Fourth Semester B.E. Degree Examination, July/August 2021 Design and Analysis of Algorithms Time: 3 hrs. Max. Marks: 80 Note: Answer any FIVE full questions. 1 If (a) €O(g,(n)) and t,(n) €O(g.(n)), prove that t,(n)+t,(n) 0 (max(g,(n),g,(n))) (06 Marks) Consider the following algorithm, Algorithm Enigma (A[0....1-1,0.....—1)) for i 0 to n—2do for j>i+1 to n-Ido if Afi Jz aii) return False. end For. end For return True (i) What does the algorithm compute? (ii) What is the basic operation? (iii) How many times the basic operation is executed? (iv) What is the efficiency class of the algorithm? (05 Marks) By using limits compare the order of growth of the following: @ ~~ tog,n and Yn. (ii) nt and 2" (05 Marks) If M(n) denotes the number of moves in towers of honoi puzzle, when n disks are involved. Give a recurrence relation for M(n) and solve the recurrence relation. (06 Marks) Define basic three asymptotic notations with example. (06 Marks) Define with example, (Stack Gi), Graphs (iii) Trees (iy) Sets and Dictionaries. (04 Marks) Write Merge Sort algorithm and discuss its efficiency. Sort the list E, X, A, M, P. L, E in alphabetical order. (08 Marks) Write recursive algorithm to find minimum and maximum element in a set of n elements by using divide and conquer and find the minimum and maximum element in the set 29, 4, 88, 15, 9, 87, 14, 1 (08 Marks) Write Quick Sort Algorithm. Sort 5, 3, 1, 9, 8, 2, 4, 7 in ascending order and write the tree of recursive calls to quicksort algorithm. (08 Marks) Lof315C843 Solve the recurrence relation by using backward substitution method. (Solve for n=2) a2 |a2 2)"° ifn>2 Tn) =41 ifn=2 (08 Marks) 0 if Write and explain Greedy Knapsack algorithm. (04 Marks) What is minimum cost spanning tree? Explain with an example, Find minimum cost spanning tree for weighted graph given in Fig. QS (b) using Prim’s algorithm, with source vertex | (07 Marks) Fig. Q5 (b) For n= 4, profits (Pi, P2, Ps, Ps) =(100, 10, 15, 27) and deadlines (di, ds, ds, ds) = (2, 1, 2, 1) Find all the feasible solutions and optimal solution for Job sequencing with deadlines problem. (05 Marks) Write Dijikstra’s algorithm, Apply Dijikstra’s algorithm on the graph given in Fig. Q6 (a), to obtain the shortest paths from source vertex 1. (08 Marks) Fig. Q6 (a) Sort the array 3, 2, 4 1, 6, 5 by using heapsort with array representation of heaps in increasing order. (04 Marks) Write Kruskal’s algorithm. (04 Marks) Using Warshalls algorithm, obtain transitive closure of matrix for the graph given in Fig. Q7 (a) (08 Marks) Oe—_@ Fig. Q7 (a) Using dynamic programming solve the following knapsack instance. For n = 4, M = 5, (Wi, W2, Wa, Wa) = (2, 1, 3, 2) and (P), P2, Ps, Pa) = (12, 10, 20, 15) (08 Marks) 20f315CS843 8 4, Write Floyd’s algorithm. Find all pair shortest path for the graph given in Fig. Q8 (a). (08 Marks) Fig, Q8 (a) b. Write short note on: () Reliability design, Gi) Optimal binary seareh tree algorithm and its efficiency. (08 Marks) 9 a. Write the pseudocode for backtracking algorithm. Apply backtracking to solve the instance of the sum of subset problem. $= {3, 5, 6, 7} and d = 15. (08 Marks) b. Write short note on: ()— N.Queen’s problem, (ii) Hamiltonian cycles. (08 Marks) 10 a. With the help of a state space tree, solve the following salesperson problem for graph given in Fig. Q10 (a), using branch and bound algorithm, (08 Marks) Fig. Q10 (a) b. Write short note on: (i) Non deterministic algorithm (i) Graph Colouring (ili) P, NP problems (iv) NP hard class. (08 Marks) tte 30f3ipractice. 50, willbe treated a ines on the remaining blank pages. ‘evaluator and /or equations writen og, 42+8, ing your answers, compulsorily draw diagonal cross 2. Any revealing of idontficaion, appeal Important Note : 1. On comple CSCS SCHEME USN | 17€843 Fourth Semester B.E. Degree Examination, July/August 2021 Design and Analysis of Algorithms Time: 3 hrs. Max. Marks: 100 Note: Answer any FIVE full questions. 1a. Define asymptotic notations with example. (09 Marks) Solve the following recurrence relation. Using backward substitution x(n) =3x(n—1) forn> 1, x(1)=4 (03 Marks) List and explain the basic asymptotic efficiency classes. (08 Marks) 2 a. Define the following terms : (i) Graph (i) Tree (iii) Set and Dictionaries. (04 Marks) Write an algorithm to find n Fibonacci number recursively. Set up a recurrence relation for Fibonacci number and solve it (08 Marks) Consider the following algorithm Algorithm Mystery (n) Minput : A nonnegative integer is Se-0 for i 1 tondo sestiti returns (i) What does this algorithm compute? (ii) What is its basic operation? (iii) How many time is the basic operation executed? (iv) What is the efficiency class of this algorithm? (08 Marks) 3. a Write an algorithm to finding the maximum and minimum of the given set of elements, {a(i), a(H1),.......a@)} (08 Marks) Apply Quicksort algorithm to the following set of input values and draw a tree of recursive calls to quicksort with input values / and r of subarray bounds and split position P of a partition obtained. 5,3, 1,9,8,2,4,7 (12 Marks) 4 a, Explain the Strassen’s matrix multiplication algorithm ( compute the product of 2x2 matrices. (08 Marks) Describe the advantages and disadvantages of divide and conquer technique, (06 Marks) Consider the following graph, apply the DFS-based algorithm to solve the topological sorting problem for the given digraphs : (Refer Fig. Q4 (c)) (06 Marks) oa Fig. Q4 (c) 1of3a 17843 wr malgorithm of greedy method control abstraction for the subset paradigm. (06 Marks) What is spanning tree? Explain the Prim’s algorithm for constructing a minimum spanning, tree for the weighted connected graph. (08 Marks) Apply the dijkstra’s algorithm for single source shortest paths for the given graph and assume vertex “A” as source (Fig. QS (¢)) (06 Marks) 3 3—— Fig, Q5(¢) (i) Construct a Huffiman code for the following data: Character [A |B [C [D_[- Probability | 0.4 [0.1 | 0.2 | 0.15 | 0.15 (ii) Encode the text ABACABAD using the code of Q(). (iii) Decode the text whose encoding is 1010111001010 in the code of Q(). (10 Marks) Construct a heap for the list 2. 9, 7, 6, 5, 8 by bottom up algorithm and how efficient is this algorithm in the worst case’ (10 Marks) Apply the dynamic programming algorithm for constructing an optimal binary search-tree for the folloy data set: [Key A [B [ec [Probability [0.1 | 0.2 | 0.4 (10 Marks) Solve the all pairs shortest path problem for the diagram with the following weight matrix: O2m18 603.2% 04 x (10 Marks) 20 3 one Compute the optimal tour of the given directed graph using dynamic programming techniques of TSP. (Refer Fig. Q8 (a). (10 Marks) Fig. Q8 (a) 2of3170843 b. Apply the bottom-up dynamic programmin knapsack problem. algorithm to the following instance of the Item | Weight | Value 1 a $12 2 T $10 _| Capacity W =5 5 3 $20 4 2__[ sis (10 Marks) 9 a. Explain how the board’s symmetry can be used to find the second solution to the 4-Queen problems. (06 Marks) 'b. Apply backtracking to the problem of finding a Hamiltonian circuit in the following graph (Fig. Q9 (b)) (08 Marks) Fig. Q9 (by © Write a pseudocode of the backtracking algorithm. (06 Marks) 10 a. Construct and draw the state space tree of the backtracking algorithm applied to the instance A=(3, 5, 6, 7} and d = 15 of the subset problem, (10 Marks) b. Solve the following instance of the knapsack problem by FIFOBB algorithm. n=4 (Pj, Pz, P3, Pa) =(10, 10, 12, 18) Wi, Wa, Ws, Wa = (2.4.6.9) M= 15 (10 Marks) 3 0f3be teated as malpractice blank pages. 1 your answers, compulsorily draw diagonal cross lines on the remai jation, appeal to evaluator and for equa 5 a é 2 Important Note: 1. On compl GBES SChlEME USN [TELE 15CS43 Fourth Semester B.E. Degree Examination, Jan./Feb. 2021 Design and Analysis of Algorithms Time: 3 hrs. Max. Marks: 80 Note: Answer any FIVE full questions, choosing ONE full question from euch module. Modute-1 1a. Explain the worst case, best case and average ease efficiencies of an algorithm, with an example each case (08 Marks) b. Explain the method of comparing the order of growth of two functions using limits, compute the order of growth of (i) logznand Vn (ii) 2" andn! (08 Marks) OR 2 a Define Big Oh notation. Prove that if t,(n)eO(y(n)) and Lin)=O(g.(n)) then (1) + t(n) € O(max fg\(n).23(n)}) (08 Marks) b, Explain the general plan for analyzing the efficieney of a recursive alzoritiim by considering Tower of Honoi problem as an example (08 Marks) Modute-2 3a, Explain the concept of divide and conquer. Design and algorithin for merge sort, (08 Marks) b. Apply Stressen’s matrix multiplication algorithm to compute product of following two [: ‘] F | matrices: * (08 Marks) 31 45 OR 4 a. Discuss how Quick data set: 2,-4, 1.0.3 ort works to sort an array. Trace Quick sort algorithny for the following ~T. Also derive the worst case time complexity of Quick sort. (08 Marks) b. Design and analyse an algorithm for findings the maximum and minimum of an clements using Divide and Conquer Approach, (08 Marks) Modute-3, 5 a. Write the algorithm to find optimal solution for job sequencing problem with deadline. Apply the same algorithm for the following dataset and find an optimal solution, n=4, Profit (pi. p2- ps. Pa) = (100, 10, 15. 27), Deadlines: (4), ds. ds, du) = (2.1.2, 1) (08 Marks) b. Write a Kruskal’s algorithm to find minimum cost spanning tree and obtain minimum spanning tree for the graph shown in Fig.Q5(b). (08 Marks)15CS43 OR What is an Heap? Write an algorithm to sort the elements using Heap Sort (08 Marks) Obtain the shortest distance cost and paths from node 5ito other nodes from the graph shown in Fig.Q6(b). (08 Marks) Module-4 Write Warshall’s algorithm and find the transitive closure of the matrix given below: 0 0 R= aoa (08 Marks) 0000 ce ) Explain multistage graphs with example. Write multistage graph algorithm using forward approach (08 Marks) oR Using dynamic programming, solve the follow nod [Wie Wa, Wa, Wa] = 13,2 Ipi- pos ps, pal = [12, 10 20, 15] and M=5 (08 Marks) Solve the following traveling sales person problem using dynamic programming. ng knapsack instance: 10 15. 20 5 08 18) caiting city (08 Marks) starting city 1. aks) 6B oR sey Ix x 9 0] Modu Discuss the general backtracking algorithm, Draw the state space tree for 4 — Queen's problem. (08 Marks) Solve the following instance of Knapsack problem us ng Branch and Bound Approach, 1 [01.02.05 Wa] = [705.3]. [Vie Van Vae Va) = [40, 42, 25, 12] ‘The knapsack’s capacity w is 10. (08 Marks) OR Detine P, NP, NP. complete and NP - Hard classes. (08 Marks) Solve the following instances of assignment problem using Branch and Bound, Job! Job2 Job3 Joba {9 2 7 8)persona é _| 6 4 3 7 |person b (08 Marks), | 5 8 1 8 [persone l7 6 9 4 [person d eeeee 2of2a i 2 = rien eg, 42+8 2. Any revealing of identification, appeal to evaluator and /or eq 1. On complesing your answers, compu iz — & a GRCS Schleile usw | | | | | Lh] 170843 Fourth Semester B.E. Degree Examination, Jan./Feb. 2021 Design and Analysis of Algorithms Time: 3 hrs Max. Marks: 100 Note: Answer any FIVE full questions, choosing ONE full question from each module. Modul 1a. Define algorithm, Explain asymptotic notations Big oh, Big omega and Big theta with example. (08 Marks) b. List and explain the important problem types that are solved by computer (07 Marks) c. Prove that: Ift(n) €O(gu(n)) and b(n) & O(ga(n)) then y(n) + t36n) = OCmax fenin), go(n)}). (05 Marks) OR 2 a, Design an algorithm for checking whether all elements in a given array are distinet or note Derive its time complexity. (08 Marks) b. Give general plan of analyzing recursive algorithm, Mathematically analyze the tower of hhanoi problem and find its time efficiency. (08 Marks) . 1 2 ©. Compare the order of growth —n(n=1) and n? (04 Marks) Modu 3 Explain divide and conquer method. Write the algorithm for binary search and derive its time complexity (10 Marks) b. List out the advantages and disadvantages of divide and conquer method. Mlustrate the topological sorting algorithm for the graph in Fig Q3(b). using DES metho. Fig Q3(b) (10 Marks) OR 4a. Apply Quicksort algorithm for the following list of elements 5, 3. 1.9. 8.2.4.7. (8 Marks) b. Write algorithm for mergesort and Analyze its efliciency (08 Marks) ¢. Explain Strassen’s matrix multiplication (04 Marks) Lof25a b, 6 a b Ta b 170843 Module-3 Write Dijkstras shortest path algorithm, Apply Dijkstras shortest path algorithm on Fig Q5(a) to obtain shortest path. Assume vertex 6 as source. Fig Qsta) (10 Marks) Write an algorithm for the heapsort. Sort the given list of number using heapsort, Derive its lime complexity: 100, 75, 80, 25, 50, 30, 45. (10 Marks) OR Define minimum spanning tree. Apply prims algorithm on the graph Fig Q6(a) 60 Fig Q6(a) (08 Marks) Solve the knapsack problem using greedy method for n= 3, m=20, (P), Ps, Py) = 25, 24,15 and (Wy, W2, W3) = (18, 15, 10). (04 Marks) Construct a Hultinan code for the following data: T [Character B D [probability [0.4] 0.1 [0.2 [0.15 I:ncode the text ABACABAD and decode the encoded text 11001010. (08 Marks) Module-4 Write the pseudocode to find on optimal Binary search tree by dynamic C programming, (08 Marks) Write Bellman Ford algorithm to compute shortest path. (05 Marks) Find the optimal solut programming, on for the following instance of knapsack problem using dynamic 15 (07 Marks)170843 OR 8 a. Explain dynamic programming. Apply Warshalls algorithm to compute transitive closure for the graph in Fig 8(a). O—% Fig 8(a) (10 Marks) 5. Write Floyd’s algorithm, Find all pairs shortest path using Floyd’ algorithm for the graph in Fig Q8(b). Fig 8(b) (10 Marks) Module-5 9 a With necessary state space diagram, explain the solving of four-queens problem by backtracking. (10 Marks) b. What is branch and bound technique? How it is different fiom backtracking? (0S Marks) c. Explain how the Travelling Salesman Problem (TSP) can be solved using branch and bound. (0sM OR 10 a Apply Backtracking method to solve subset sum problem for the instance d af 6.7) (08M b. Explain the classes of NP-hard and NP-complete. (06 Marks) ©. Draw portion of state space tree for m-colouring with n= 3 and m = 3 and explain m-colouring (06 Marks) teeee 30f3CAICS Senlelile USN 17843 Fourth Semester B.E. Degree Examination, Dec.2019/Jan.2020 Design and Analysis of Algorithms Time: 3 hrs. Max. Marks: 100 Note: Answer any FIVE full questions, choosing ONE full question from each module. Module-1 1a. Explain Asymptotic notations in detail with example. (12 Marks) b. Outline an algorithm to find maximum of n elements and obtain its time complexity. (08 Marks) OR 2 a. Design algorithm for tower of Hanoi problem and obtain time complexity. (10 Marks) Prove the theorem if fi(n) € 0 (g, (n)) and f,(n) €0 (g2 (n) Then fi(n) + f2(n) € 0 (max {zr(n), g2(n)}). (10 Marks) Module-2 3 Design a recursive algorithm for binary search and calculate time complexity. (10 Marks) b. Write the algorithm for merge sort and Trace 60, 50, 25, 10, 35, 25, 75, 30. (10 Marks) OR 4 Develop an algorithm for Quick sort and derive its time complexity. (10 Marks) a ‘What is topological sorting? Apply DFS for below graph to solve topological sorting. 5 (10 Marks) a 2 Z Fig.Q.4(b) Module-3 5 Find the optimal solution to the knap sack instant n= 7, m= 15 using greedy method. Object | 1 | 2 415 [6[7 Weight | 02 [ 0: 07 [01 | 04 | 01 Profit [10 [05 07 [06 | 18 [03 Important Note: I. On com (10 Marks) Find the minimum spanning tree using Kruskal’s algorithm. 6 pe og 2 Fig. Q.5(b) (10 Marks) Lof2OR 6 a, Construct a Huffman code for the following data: Characters [A B cI Probability [ 0.4 | 0.1 0. 2 0.15 0.15 Encode the text ABACABAD and decode 100010111001010 b. Calculate the shortest distance and shortest path Fig.Q.6(b) with an example. b. Construct an optimal binary search tree for the following: A Probabilities : [0.1 Module-4 Explain the general procedure to solve a mult Items B D 0. 2 c 04 03 OR 170843 (10 Marks) from vertex 5 to vertex 0 using Dijkstra’s, (10 Marks) tage graph problem using backward approach (10 Marks) (10 Marks) 8 a. Design Floyd's algorithm to find shortest distances from all nodes to all other nodes. b. Apply Warshall’s algorithm to compute transitive closure for the graph below, Fig.Q.8(b) € Module-5 S) (10 Marks) (10 Marks) 9 a, What is Hamiltonian circuit problem? What is the procedure to find Hamiltonian circuit of a graph? b, Explain the classes of NP-Hard and NP-complete. OR (10 Marks) (10 Marks) 10 a. Apply the branch and bound algorithm to solve the travelling salesman problem for the graph below. Fig.Q.10(a) b. Obtain the optimal solution assignment 3 ioe @ Sox roblem given: Ji [be [bs [de a[9 [2 {7/8 b{6 [4 [3 [7 e[s{[s[i [8 d{7 [6 ]9 [4 (10 Marks) (10 Marks)ns written eg, 42+8 = 50, will be treated as malpractice. ines on the remaining blank pages. squat : Note: 1. Oncompleting your answers, compulsorily draw diagonal cross 2. Any revealing of identification, app Imps USN BCS ScHlEliE | 17C843, Fourth Semester B.E. Degree Examination, Aug./Sept.2020 Design and Analysis of Algorithms Time: 3 hrs. Max. Marks: 100 Note: Answer any FIVE full questions, choosing ONE full question from each module. Module. Define an algorithm. Explain the characteristics of an algorithm, (04 Marks) What are Asymptotic notations? List and describe the various asymptotic notations with an ‘example of each, (08 Marks) Explain the general plan of mathematical analysis of non-recursive algorithm. with an example. (08 Marks) OR What is the worst case, best case and average case efficiencies of sequential search? (04 Marks) Ilustrate mathematical analysis of recursive algorithm for Towers of Hanoi problem, (08 Marks) Discuss the important problem types and fundamental data structures. (08 Marks) Module-2 Discuss how Quick sort algorithm works to sort an array and trace for the following data set. Draw the tree of recursive calls made. 25 OL 46 35 82. 4 55, Derive best case complexity of quick sort algorithm. (10 Marks) Obtain the topological sorting for the digraph shown in Fig.Q3(b), using source removal method. © © od Fig.Q3(b) (06 Marks) List out the advantages and disadvantages of divide and conquer technique. (04 Marks) OR Explain divide and conquer technique with its control abstraction. (04 Marks) Develop an algorithm for sorting elements using Simple merge. Apply the same for sorting list of elements given below: 7 [| 2 [ss] oe] 4] ® (08 Marks) Apply Strassen’s algorithm to compute 1021] fo1o0 11 of 130 021 1 4 4 0 1 5 0. = Nw 1 0 3 woe 1of4170843 Module-3 a. State Job sequencing with deadline problem. Find the solution generated by job sequencing problem for 7 jobs given profits 3, 5, 20, 18, 1, 6, 30 and deadlines 1, 3, 4, 3, 2, 1, 2 respectively, (04 Marks) b. Explain the concept of greedy technique for Prim’s algorithm, Obtain a minimum cost spanning tree for the graph below in Fig.Q5(b). ‘ Fig. Q5(b) (08 Marks) ©. Sort the given list of number using Heap sort: 2 [771 T6¢ Ts T4773 (08 Marks) OR a. Explain Greedy criterion. Apply greedy method for the following instance of knapsack problem. Capacity of the knapsack (M) = 5. Item Weight [Value] 1 2 $12 z i S10 3 3 $20 4 2 SIS) (08 Marks) b. Construct a Huffman code for the following data and encode the test BADEC. Character A_| B c DIE Probabil 04 [or [02 [01s | 015 (06 Marks) c. Solve the below instance (Fig.Q6(e)) of single source shortest path problem with vertex a as the source. (06 Marks) a, What is Dynamic programming? Using Warshall’s algorithm, obtain the transitive closure of the graph defined by the following adjacency matrix. o100 ooo) R= (04 Marks) 0000 1o1o 2o0f417CS843 Define multistage graph problem. Determine the minimum cost path from source (S) to sink (T) for the graph in Fig.Q7(b) using forward approach z Fig.Q7(b) (06 Marks) Solve the below instance of Bellman-Ford algorithm [Fig.Q7(c)} OKA-Pey, ' Fig.Q7(c) (10 Marks) OR Explain Travelling Salesperson Problem (TSP). Solve the below instance of TSP using dynamic programmin; 1 1 2 3 4 1 o 10 15 20 215 0 9 10 3] 6 3 0 12 4{[ 8 8 9 0 (08 Marks) Obtain optimal Binary search Tree for the following identifiers. 1 2 3 4 afi] ("do [if [int] while pti] or | 02 | 04 | 03 (12 Marks) Draw the state-space tree top generate solutions to 4-Queen’s problem. (04 Marks) . Apply backtracking technique to solve the below instance of the subset sum problem s={1,3,4,6} d=? (08 Marks) Apply Branch_and_Bound technique to the following insurance of assignmen: problem jobl job2 job3. job4 9 2 7 8] Person a Person b (08 Marks) ares 4p 8 1 8] Persone 6 9 4} Person d 30f417CS43 oR How the Branch_and_Bound technique is different from backhacking? Solve the following insurance of knapsack problem using Branch_and_Bound technique. Give knapsack capacity = 10. Item 1 Weight | 4 _|_ Valve 40 (08 Marks) Define Hamiltonian cycle. Check whether the Hamiltonian eycle exists for the graph given below in Fig.Q10(b) Fig.Q10(b) (04 Marks) Define the following : (i) Class P (ii) Class NP (iii) NP Complete Problem (iv) NP Hard Problem, (08 Marks) 4o0f4'50, willbe treated as malpractice. Jor equations writen eg, 42+8 your answers, compulsorily 1y revealing of identification, appeal to evaluator 2 z z Schleifle USN | ] 15CS43 Fourth Semester B.E. Degree Examination, Aug./Sept. 2020 Design and Analysis of Algorithm Time: 3 hrs. Max. Marks: 80 Note: Answer any FIVE full questions, choosing ONE full question from eack module. Module-1 What is an Algorithm? Explain any six properties to specify an algoithtm. (07 Marks) 1f y(n) € O(g)(n)) and t3(n) ¢ O(g2(n)) then prove that ty(n) + t(n)€O (max4gi(n), g2(n)}) (05 Marks) Design an Algorithm to find a largest of a given number and analyze its efficiency. (04 Marks) OR Define Asymptotic rotation, explain Big-Oh notation and show that 10n' + 5 €O(n"). (07 Marks) Consider a recurrence relation T(n) = T(n ~ 1) + n, with initial condition T(0) = 0. Solve it using subsituational method (04 Marks) ‘Compare the order of growth of log2(n) and Vn using limits (05 Marks) Module-2 Design Binary search algorithm and derive its time complexity by applying Master Theorem, (07 Marks) Apply quick sort to sort the list E, X, A, M, P, L, E and draw the recursive calls tree. (06 Marks) Derive Strassen’s matrix multiplication time complexity by applying substitutional method. (03 Marks) Design Merge sort algorithm. Apply it to sort the list of elements 70, 20, 30, 40, 10, 50, 60 (07 Marks) Write two advantages and disadvantages of Divide and conquer (04 Marks) Apply source removal algorithm to solve topological sorting problem for the following graph. (Ref. Fig Q No.4 (c)) Fig Q4(c) (05 Marks)15CS43 Module-3 Define Greedy technique, feasible solution and optimal solution, Write general algorithm of greedy method. (05 Marks) What is Knapsack problem? Find a feasible solution considering maximum profit, minimum. weight and profit by weight ration to the Knapsack instance n= 7, m= 5, (P,, P2, Ps, Pa, Ps, Ps, Pr) =(10, 5, 15, 7,6, 18, 3) and (wi, wo, ws, Wa, ws, Wo, Wa) = (2, 3,5, 7, 1,4, 1) (05 Marks) i) Construct a Huffinan tree for the following data and obtain in Huffman code. Character A BC D E Probability 0.5 035 0.5 0.1 04 02 ii) Encode the text DAD_BE using the code of Question (i) iii) Decode the text whose encoding is 1100110110 in the code of question (i) (06 Marks) OR Define a Heap and list the important properties of Heap. (03 Marks) Compute a minimum cost spanning tree for the graph shown below in Fig Q6(b). Using i) Prim’s and ii) Kruskal algorithm. Fig Q6(b) (08 Marks) Solve the following instances of the single source shortest paths problems with vertex a as the source, (Ref Fig Q No 6(c)). Fig Q6(c) (05 Marks) 2o0f47 a 15CS43 Module-4 Design Warshall Algorithm. Apply Warshalls to find the transitive closure of the graph defined by the following adjacency matrix. abed af0 10 0 blo oo 1 (08 Marks) cl0 000 dil ot 0 Design Floyd's Algorithm, write one difference between FLOYD’s and Dijkstra’s algorithm. Apply Floyd’s algorithm to the following graph. Ref Fig Q7(b)). Fig Q7(b) (08 Marks) oR Write the recurrence relation to find the optimal solution for the Knapsack problem using Dynamic programming and find the optimal solution for the following instance. Tiem | Weight | Value 2 1 2_ [sR 2 I $10 3 3 $20 4 2 SIS |__Capacityw=5__| (08 Marks) Find shortest path from node | to every other node in the graph as given below in Fig Q8(b). Using Bellamn Ford Algorithm, Fig Q8(b) (08 Marks) 3of410 ee 15CS43 Module-5 Design and implement in Java to find a subset of a given set S = {S1, Sx Ss......Sa} of n positive integers whose sum is equal to a given positive integer d. (08 Marks) Explain Backtracking concept and generate atleast 4 solutions for 5 Queen’s problem. (08 Marks) OR Explain the following NP problems NP — Complete problems Graph coloring Hamilton cycles. (16 Marks) seeee 4of4CAICS Senlelile USN 17843 Fourth Semester B.E. Degree Examination, Dec.2019/Jan.2020 Design and Analysis of Algorithms Time: 3 hrs. Max. Marks: 100 Note: Answer any FIVE full questions, choosing ONE full question from each module. Module-1 1a. Explain Asymptotic notations in detail with example. (12 Marks) b. Outline an algorithm to find maximum of n elements and obtain its time complexity. (08 Marks) OR 2 a. Design algorithm for tower of Hanoi problem and obtain time complexity. (10 Marks) Prove the theorem if fi(n) € 0 (g, (n)) and f,(n) €0 (g2 (n) Then fi(n) + f2(n) € 0 (max {zr(n), g2(n)}). (10 Marks) Module-2 3 Design a recursive algorithm for binary search and calculate time complexity. (10 Marks) b. Write the algorithm for merge sort and Trace 60, 50, 25, 10, 35, 25, 75, 30. (10 Marks) OR 4 Develop an algorithm for Quick sort and derive its time complexity. (10 Marks) a ‘What is topological sorting? Apply DFS for below graph to solve topological sorting. 5 (10 Marks) a 2 Z Fig.Q.4(b) Module-3 5 Find the optimal solution to the knap sack instant n= 7, m= 15 using greedy method. Object | 1 | 2 415 [6[7 Weight | 02 [ 0: 07 [01 | 04 | 01 Profit [10 [05 07 [06 | 18 [03 Important Note: I. On com (10 Marks) Find the minimum spanning tree using Kruskal’s algorithm. 6 pe og 2 Fig. Q.5(b) (10 Marks) Lof2OR 6 a, Construct a Huffman code for the following data: Characters [A B cI Probability [ 0.4 | 0.1 0. 2 0.15 0.15 Encode the text ABACABAD and decode 100010111001010 b. Calculate the shortest distance and shortest path Fig.Q.6(b) with an example. b. Construct an optimal binary search tree for the following: A Probabilities : [0.1 Module-4 Explain the general procedure to solve a mult Items B D 0. 2 c 04 03 OR 170843 (10 Marks) from vertex 5 to vertex 0 using Dijkstra’s, (10 Marks) tage graph problem using backward approach (10 Marks) (10 Marks) 8 a. Design Floyd's algorithm to find shortest distances from all nodes to all other nodes. b. Apply Warshall’s algorithm to compute transitive closure for the graph below, Fig.Q.8(b) € Module-5 S) (10 Marks) (10 Marks) 9 a, What is Hamiltonian circuit problem? What is the procedure to find Hamiltonian circuit of a graph? b, Explain the classes of NP-Hard and NP-complete. OR (10 Marks) (10 Marks) 10 a. Apply the branch and bound algorithm to solve the travelling salesman problem for the graph below. Fig.Q.10(a) b. Obtain the optimal solution assignment 3 ioe @ Sox roblem given: Ji [be [bs [de a[9 [2 {7/8 b{6 [4 [3 [7 e[s{[s[i [8 d{7 [6 ]9 [4 (10 Marks) (10 Marks)CHGS Seema e« (COT Hes Fourth Semester B.E. Degree Examination, June/July 2018 Design and Analysis of Algorithms ‘Time: 3 hrs. Max. Marks: 80 Note: Answer any FIVE full questions, choosing ONE full question from each module, Module-1 1a. Write an algorithm to find the maximum element in an array of n element. Give the mathematical analysis of this non-recursive algorithm, (06 Marks) b. Explain the asymptotic notations BigO, BigQ and big theta used to compare orders of growth of an algorithm, (06 Marks) ¢. Explain with an example how a new variable count introduced in a program can be used to find the number of steps needed by a program to solve a particular problem instance. (04 Marks) OR 2 a. Write a recursive function to find and print all possible permutations of a given set of elements, (05 Marks) b. Solve the recurrence relation : M(n) = 2M(n — 1) + 1. Take M(1) = 1, M(n) is given for n>1 (05 Marks) ©. Define algorithm. What are the criteria that an algorithm must satisfy? (06 Marks) Module-2 3-4. Write a function to find the maximum and minimum elements in a given array of n elements by applying the divide and conquer technique. (06 Marks) b. Explain the divide and conquer technique. Give the general algorithm DAndC(P)[Where P is. the problem to be solve] to illustrate this technique. (04 Marks) c. Apply source removal method to obtain topological sort for the given graph in Fig.Q3(c). (06 Marks) ~~ E g ig. Q3(c) OR 4a, Explain the merge sort algorithm, Illustrate with an example and give the worst case efficiency of merge-sort. (08 Marks) b. Apply quick sort algorithm to the following set of numbers. 65, 70, 75. 80. 85, 60, 55, 50, 45. (08 Marks) 1of36 1 a b, a 15CS43, Modul Apply greedy method to obtain an optimal solution to the knapsack problem given M = 60, (81, Was Wa, Wa, W5) = (5, 10, 20, 30, 40) (Pr, po, PH. Pa Ps) = 30, 20, 100, 90, 160). Find the total profit earned. (04 Marks) Explain Huffman algorithm. With an example show the construction of Huffman tree and ‘generate the Huffiman code using this tree. (06 Marks) Apply Prim’s algorithm to obtain a minimum spanning tree for the given weighted connected graph. [Fig.Q5(c)}. (06 Marks) Fig.QS(c) OR Explain the bottom up heap construction algorithm with an example. Give the worst case efficiency of this algorithm. (08 Marks) Apply single source shortest path problem assuming vertex a as source,[Reter Fig.Q6(b)] (08 Marks) Fig.Q6(b) Module-4 Explain multistage graph with ai example. Write multistage graph algorithm using backward approach. (08 Marks) Apply Floyd’s algorithm to soive all pair shortest path problem for the graph given below in Fig. Q7(b). (08 Marks) Fig.Q7(b) 2of310 15CS43, OR Explain Bellman Ford al to find shortest path from single source to all destinations for a directed graph with negative edge cost (08 Marks) Apply Warshall’s algorithm to the digraph given below in Fig.Q8(b) and find the transitive closure. (08 Marks) Fig.Q8(b) Mod Apply backtracking method to solve subset-sum problem for the instance d = 30. and $= {5, 10, 12, 13, 15, 18}. Give all possible solutions. (08 Marks) Explain how travelling salesman problem can be solved using branch and bound technique. (06 Marks) Define deterministic and non deterministic algorithms. (02 Marks) OR What is Hamiltonian cycle? Explain the algorithm to find the Hamiltonian cycle ina given connected graph. Write the functions used for generating next vertex and. for finding Hamiltonian cycles. (09 Marks) Apply the best-first branch-and-bound algorithm to solve the instance of the given job assignment problem. (07 Marks) Job! Job2 Job3 Job4 9 2 7 $8) Persona 4 3 7} Person b ga 8 | Persone 6 9 4) Persond 30f3‘written eg, 42+8 = 50, will be treated as malpractice, nswers, compulsorily draw diagonal cross lines on the remaining blank pages fication, appeal to evaluator and /or equatio 2. Any revealing of identi Important Note : 1. On completing your an Shells Fourth Semester B.E. Degree Examination, June/July 2019 Design and Analysis of Algorithms Time: 3 hrs. Max. Marks: 100 Note: Answer any FIVE full questions, choosing ONE full question from each module. Mod 1 Design an algorithm to search an element in a array using sequential search. Discuss the worst case, best case and average case efficiency of this algorithm, (08 Marks) Discuss adjacency matrix and adjacency list representation of a graph with suitable example. (06 Marks) Give the recursive algorithm to solve towers of Hanoi problem. Show that the efficiency of this algorithm is exponential (06 Marks) oR Give the general plan for analyzing time efficiency of non recursive algorithms. Derive the worst case analysis for the algorithm to check whether all the elements in a given array are distinct. (08 Marks) List and define any three asymptotic notations. What are the various basic asymptotic efficiency classes? (06 Marks) Explain the following types of problems: (i) Combinatorial problems (ii) Graph problems. (06 Marks) Moduk Write an algorithm to sort ‘n’ numbers using Quick sort. Trace the algorithm to sort the following list in ascending order. 80 60 70 40 10 30 50 20 (08 Marks) Discuss general divide and conquer technique with control abstraction and recurrence relation (06 Marks) Apply DFS based algorithm and source removal method to find the topological sequence for the graph shown in Fig.Q3(¢) (06 Marks) on Fig.Q3(c) OR Apply Strassen’s matrix multiplication to multiply following matrices. Discuss how this ‘method is better than direct matrix multiplication method. i: Aon ‘l (08 Marks) 21)" 6 Write recursive algorithm to find maximum and minimum element in an array. (06 Marks) Write an algorithm to sort ‘n’ number using merge sort, (06 Marks) Lof217CS843 Module-3 Write an algorithm to solve knapsack problem using Greedy technique. Find the optimal solution to the knapsack instance n= 7, m= 15 (Pi, Po P,) = (10, 5, 15, 7, 6, 18, 3) (Wi, Wa.....Wo) = (2,3, 5, 7.1.4, 0) (10 Marks) Apply Prim’s algorithm and Kruskal’s method to find the minimum cost spanning tree to the graph shown in Fig.Q5(b). (10 Marks) Fig.Q5(b) OR Write an algorithm to solve single source shortest path problem. Apply the algorithm to the graph shown in Fig, Q6(a) by considering ‘a’ as source. (10 Marks) Fig. Q6(a) Define heap. Write bottom-up heap construction algorithm. Construct heap for the list 1, 8,6, 5, 3, 7, 4 using bottom-up algorithm and successive key insertion method. (10 Marks) Module-4 Define transitive closure of a directed graph. Find the transitive closure matrix for the graph whose adjacency matrix is given 10010 01000 ooo1t (10 Marks) 10000 o1001 Find the optimal tour for salesperson using dynamic programming technique. The directed graph is shown in Fig.Q7(b) (10 Marks) 10 c \i3 oli SI iz Fig.Q7(b) 2of310 17CS43 OR Write an algorithm to construct optimal binary search tree for the following data: Key A B ic D Probability or | 02 [04 [03 (10 Marks) Apply the bottom-up dynamic programming algorithm to the following instance of the knapsack problem, Knapsack capacity W= 10. Item Weight Value 1 7 2 2 3 12 3 4 40 4 5 25 (10 Marks) Module-5 Construct state-space tree for solving four queens problem using backtracking, (06 Marks) Discuss graph coloring problem. Find different solutions for 4 nodes and all possible 3 coloring problem. (06 Marks) Write a note on: (i) Non deterministic algorithms. (ii) LC branch and bound solution to solve O/I knapsack problem (08 Marks) OR What are the two additional items required by Branch and Bound technique, compared with backtracking. Solve the following assignment problem using branch and bound technique, ‘whose cost matrix for assigning four jobs to four persons are given (10 Marks) us aon wre a 8 8g 7 4 Discuss the following : (i) Subset sum problem (ii) NP hard and NP complete classes. (10 Marks) weer 30f3CHGS Seema e« (COT Hes Fourth Semester B.E. Degree Examination, June/July 2018 Design and Analysis of Algorithms ‘Time: 3 hrs. Max. Marks: 80 Note: Answer any FIVE full questions, choosing ONE full question from each module, Module-1 1a. Write an algorithm to find the maximum element in an array of n element. Give the mathematical analysis of this non-recursive algorithm, (06 Marks) b. Explain the asymptotic notations BigO, BigQ and big theta used to compare orders of growth of an algorithm, (06 Marks) ¢. Explain with an example how a new variable count introduced in a program can be used to find the number of steps needed by a program to solve a particular problem instance. (04 Marks) OR 2 a. Write a recursive function to find and print all possible permutations of a given set of elements, (05 Marks) b. Solve the recurrence relation : M(n) = 2M(n — 1) + 1. Take M(1) = 1, M(n) is given for n>1 (05 Marks) ©. Define algorithm. What are the criteria that an algorithm must satisfy? (06 Marks) Module-2 3-4. Write a function to find the maximum and minimum elements in a given array of n elements by applying the divide and conquer technique. (06 Marks) b. Explain the divide and conquer technique. Give the general algorithm DAndC(P)[Where P is. the problem to be solve] to illustrate this technique. (04 Marks) c. Apply source removal method to obtain topological sort for the given graph in Fig.Q3(c). (06 Marks) ~~ E g ig. Q3(c) OR 4a, Explain the merge sort algorithm, Illustrate with an example and give the worst case efficiency of merge-sort. (08 Marks) b. Apply quick sort algorithm to the following set of numbers. 65, 70, 75. 80. 85, 60, 55, 50, 45. (08 Marks) 1of36 1 a b, a 15CS43, Modul Apply greedy method to obtain an optimal solution to the knapsack problem given M = 60, (81, Was Wa, Wa, W5) = (5, 10, 20, 30, 40) (Pr, po, PH. Pa Ps) = 30, 20, 100, 90, 160). Find the total profit earned. (04 Marks) Explain Huffman algorithm. With an example show the construction of Huffman tree and ‘generate the Huffiman code using this tree. (06 Marks) Apply Prim’s algorithm to obtain a minimum spanning tree for the given weighted connected graph. [Fig.Q5(c)}. (06 Marks) Fig.QS(c) OR Explain the bottom up heap construction algorithm with an example. Give the worst case efficiency of this algorithm. (08 Marks) Apply single source shortest path problem assuming vertex a as source,[Reter Fig.Q6(b)] (08 Marks) Fig.Q6(b) Module-4 Explain multistage graph with ai example. Write multistage graph algorithm using backward approach. (08 Marks) Apply Floyd’s algorithm to soive all pair shortest path problem for the graph given below in Fig. Q7(b). (08 Marks) Fig.Q7(b) 2of310 15CS43, OR Explain Bellman Ford al to find shortest path from single source to all destinations for a directed graph with negative edge cost (08 Marks) Apply Warshall’s algorithm to the digraph given below in Fig.Q8(b) and find the transitive closure. (08 Marks) Fig.Q8(b) Mod Apply backtracking method to solve subset-sum problem for the instance d = 30. and $= {5, 10, 12, 13, 15, 18}. Give all possible solutions. (08 Marks) Explain how travelling salesman problem can be solved using branch and bound technique. (06 Marks) Define deterministic and non deterministic algorithms. (02 Marks) OR What is Hamiltonian cycle? Explain the algorithm to find the Hamiltonian cycle ina given connected graph. Write the functions used for generating next vertex and. for finding Hamiltonian cycles. (09 Marks) Apply the best-first branch-and-bound algorithm to solve the instance of the given job assignment problem. (07 Marks) Job! Job2 Job3 Job4 9 2 7 $8) Persona 4 3 7} Person b ga 8 | Persone 6 9 4) Persond 30f3