DAA PYQs

print rush

print rush

S T U D I O S PYQs DAA BTECH 3RD YEAR SHEET 

[4]

Q.6 i. ii. iii. Define Hamiltonian Cycle with the Example What is backtracking? Find a solution to the 4 queens Problem using Backtracking Strategy. What is Branch and Bound Technique? Solve the TSP for the following matrix. ∞ 7 3 12 8 3 ∞ 6 14 9 5 8 ∞ 6 18 9 3 5 ∞ 11 18 14 9 8 ∞ ****** Total No. of Questions: 6 Total No. of Printed Pages:4 Enrollment No...................................... 3 7 Faculty of Engineering End Sem (Odd) Examination Dec-2018 CS3CO13/IT3CO06 Design and Analysis of Algorithms 7 Programme: B.Tech. Duration: 3 Hrs. Branch/Specialisation: CSE/IT Maximum Marks: 60 Note: All questions are compulsory. Internal choices, if any, are indicated. Answers of Q.1 (MCQs) should be written in full instead of only a, b, c or d. Q.1 i. ii. iii. iv. v. vi. If algorithm A has running time 7n^2+3n+9 and algorithm B has running time 2n^2 then, (a) Both have same asymptotic time complexity (b) A is asymptotically greater (c) B is asymptotically greater (d) None of these Complexity of the recurrence relation T(n)=3T(n/3)+n^2 (a) Ɵ (n log n) (b) Ɵ (log n) (c) Ɵ (n^2) (d) Ɵ (n^3) Average case complexity of binary search is (a) Ɵ (n^2) (b) Ɵ (n/2) (c) Ɵ (1) (d) Ɵ (log n) When the given inputs are already sorted, which sorting technique gives worst performance. (a) Merge Sort (b) Quick Sort (c) Heap Sort (d) None of these Which of the following is true about Huffman Coding (a) Huffman Coding may become lossy in some cases (b) Huffman Codes may not be optimal lossless codes in some cases (c) In Huffman coding, no code is prefix of any other code (d) All of these Number of Spanning tree of a complete graph with n vertices are (b) nC(n-1) (c) (d) None of these (a) 1 1 1 1 1 1 P.T.O. 

[2]

vii. If an optimal solution can be created for a problem by constructing optimal solutions for its subproblems, the problem possesses __________ property. (a) Overlapping subproblems (b) Optimal substructure (c) Memorization (d) Greedy viii. When a top-down approach of dynamic programming is applied to a problem, it usually _________ (a) Decreases both, the time complexity and the space complexity (b) Decreases the time complexity and increases the space complexity (c) Increases the time complexity and decreases the space complexity (d) Increases both, the time complexity and the space complexity ix. Which of the following is not a backtracking algorithm? (a) Knight tour problem (b) N queen problem (c) Tower of Hanoi (d) M coloring problem x. What is the minimum colour required to color a cube’s vertices (a) 4 (b) 3 (c) 2 (d) 6 Q.2 i. ii. OR iii. (a) Differentiate between Recursive and Iterative Algorithm. (b) Explain formula of Master’s Method for solving recursive algorithm. Sort these elements using Insertion Sort in ascending order. 75, 65, 45, 47, 94, 85, 77, 62, 87 How many number of shifting is required to sort the above elements. Solve these Recurrence Relation (a) T(n)= 3T(n/3) + Ɵ (n) (b) T(n)= T(n-1) + 5n (c) T(n)= 8T(n/4) + Ɵ (n log n) [3] 1 5 OR iv. Construct the Huffman Code for the following data. Character A B C D E Probability 0.4 0.1 0.2 0.15 0.15 Decode the text whose ending 100010111001010 using the above Huffman Code. 5 Q.5 i. 1 Find the single source shortest path with vertex ‘A’ as the source Solve the following instances of 0/1 Knapsack Problem using Dynamic Programming Item 1 2 3 4 Weight 4 7 5 3 Value 40 42 25 12 The Capacity of Knapsack W is 10. Explain how a reliability design can be obtained using Dynamic Programming. Consider Multistage Graph G 4 iii. 1 4 6 6 ii. OR iii. Q.3 i. ii. OR iii. Q.4 i. ii. What is Stable Sort? Name any two Stable Sorting Algorithm What is Divide & Conquer Strategy. Write Binary Search Algorithm. Analyse complexity of algorithm in best and worst case. Sort these elements using Heap sort (Max Heap) 98, 77, 55, 80, 99, 64, 91, 22, 83, 44, 65, 86, 90 3 7 What is basic difference between Prim’s and Kruskal’s Algorithm Find Optimal Merge Pattern for 7 files whose length are 12, 9,3,11,15,20,13 2 3 7 Find the Cost from shortest path from S to T using Multistage graph method? 6 6 

Marking Scheme

CS3CO13/IT3CO06 Design and Analysis of Algorithms Q.1 Q.2 i. If algorithm A has running time 7n^2+3n+9 and algorithm B has running time 2n^2 then, (a) Both have same asymptotic time complexity ii. Complexity of the recurrence relation T(n)=3T(n/3)+n^2 (c) Ɵ (n^2) Average case complexity of binary search is iii. (d) Ɵ (log n) iv. When the given inputs are already sorted, which sorting technique gives worst performance. (b) Quick Sort v. Which of the following is true about Huffman Coding (c) In Huffman coding, no code is prefix of any other code Number of Spanning tree of a complete graph with n vertices are vi. (c) n^(n-2) vii. If an optimal solution can be created for a problem by constructing optimal solutions for its subproblems, the problem possesses ____________ property. (b) Optimal substructure viii. When a top-down approach of dynamic programming is applied to a problem, it usually _________ (b) Decreases the time complexity and increases the space complexity Which of the following is not a backtracking algorithm? ix. (c) Tower of Hanoi x. What is the minimum colour required to color a cube’s vertices. (c) 2 i. ii. Differentiate between Recursive and Iterative Algorithm. 2 differences 2 marks Formula of Master’s Method for solving recursive algorithm. 2 marks Sort these elements using Insertion Sort in ascending order. 75, 65, 45, 47, 94, 85, 77, 62,87 Sorting Passwise 4 marks OR iii. 1 Number of shifting is required to sort the above elements. . 2 marks Solve these Recurrence Relation (a) T(n)= 3T(n/3)+ Ɵ (n) (b) T(n)= T(n1)+ 5n (c) T(n)= 8T(n/4)+ Ɵ (n log n) . 6 2 marks 2 marks 2 marks 1 Q.3 i. 1 1 ii. 1 1 OR iii. Q.4 i. 1 ii. iii. What is Stable Sort ? Definition 2 marks Name any two Stable Sorting Algorithm Names 1 mark What is Divide & Conquer Strategy. 2 marks Write Binary Search Algorithm. 3 marks Analyse complexity of algorithm in best and worst case. 2 marks Sort these elements using Heap sort (Max Heap) 98,77,55,80,99,64,91,22,83,44,65,86,90 Stepwise 3 What is basic difference between Prims and Krukal Algorithm 2 differences 2 marks Find Optimal Merge Pattern for 7 files whose length are 12, 9,3,11,15,20,13 Stepwise 2 marks Find the single source shortest path with vertex ‘A’ as the source 2 7 7 3 5 1 1 4 6 OR iv. Till 2 steps Relaxation Formula 5 marks Construct the Huffman Code for the following data. Character A B C D E Probability 0.4 0.1 0.2 0.15 0.15 5 

Tree

3 marks Decode the text whose ending 100010111001010 using the above Huffman Code. Decoding 2 marks Q.5 i. ii. OR iii. Solve the following instances of 0/1 Knapsack Problem using Dynamic Programming Item 1 2 3 4 Weight 4 7 5 3 Value 40 42 25 12 The Capacity of Knapsack W is 10. Full Solution 4 marks Explain how a reliability design can be obtained using Dynamic Progrmming. Algorithm or complete definition 4 marks Example 2 marks Consider Multistage Graph G ii. 4 ****** 6 6 Find the Cost from shortest path from S to T using Multistage graph method? At least till 2 steps formula 6 marks If direct solution then 4 marks Q.6 i. i. Define Hamiltonian Cycle with the Example Definition 2 marks Example 1 marks What is backtracking? Find a solution to the 4 queens Problem using Backtracking Strategy. Definition 2 marks Solution 5 marks What is Branch and Bound Technique? Solve the TSP for the following matrix. ∞ 7 3 12 8 3 ∞ 6 14 9 5 8 ∞ 6 18 9 3 5 ∞ 11 18 14 9 8 ∞ Definition 2 marks Solution 5 marks 3 7 7 

Total No. of Questions: 6

Total No. of Printed Pages:3 Enrollment No...................................... Faculty of Engineering End Sem (Odd) Examination Dec-2019 IT3CO06 Design and Analysis of Algorithms Programme: B.Tech. Duration: 3 Hrs. Branch/Specialisation: IT Maximum Marks: 60 Note: All questions are compulsory. Internal choices, if any, are indicated. Answers of Q.1 (MCQs) should be written in full instead of only a, b, c or d. Q.1 i. ii. iii. iv. v. vi. What is the asymptotic runtime for traversing all nodes in a binary search tree with n nodes and printing them in order? (a) O(n ⋅ log(n)) (b) O(n) (c) O( n) (d) O(log(n)) What is the best time complexity of bubble sort? (a) N^2 (b) NlogN (c) N (d) N(logN)^2 What is recurrence for worst case of QuickSort and what is the time complexity in Worst case? (a) Recurrence is T(n)=T(n-2) + O(n) and time complexity is O(n^2) (b) Recurrence is T(n)=T(n-1) + O(n) and time complexity is O(n^2) (c) Recurrence is T(n)=2T(n/2)+O(n) and time complexity is O(nLogn) (d) Recurrence is T(n)=T(n/10)+T(9n/10)+O(n) and time complexity is O(nLogn) In a Max heap the largest key is at (a) The root (b) A leaf (c) A node (d) None of these Which of the following algorithms is the best approach for solving Huffman codes? (a) Exhaustive search (b) Greedy algorithm (c) Brute force algorithm (d) Divide and conquer algorithm Dijkstra’s Algorithm cannot be applied on ______________ (a) Directed and weighted graphs (b) Graphs having negative weight function (c) Unweighted graphs (d) Undirected and unweighted graphs 1 1 1 1 1 1 P.T.O. 

[3]

[2] vii. The Knapsack problem is an example of ____________ (a) Greedy algorithm (b) 2D dynamic programming (c) 1D dynamic programming (d) Divide and conquer viii. Bellmann ford algorithm provides solution for ___________ problems. (a) All pair shortest path (b) Sorting (c) Network flow (d) Single source shortest path ix. What happens when the backtracking algorithm reaches a complete solution? (a) It backtracks to the root (b) It continues searching for other possible solutions (c) It traverses from a different route (d) Recursively traverses through the same route x. Which one of the following is an application of the backtracking algorithm? (a) Finding the shortest path (b) Finding the efficient quantity to shop (c) Ludo (d) Crossword Q.2 i. ii. OR iii. Q.3 i. ii. OR iii. 1 State the general principle of greedy algorithm. 3 Using Dijkstra’s algorithm, find the shortest path from the source node 0. 7 OR iii. Explain in detail the Huffman coding algorithm with example. 7 Q.5 i. ii. Differentiate between divide and conquer and dynamic programming. Solve the following instance of the 0/1 knapsack problem given the knapsack capacity is W=5 3 7 OR iii. Using Floyd Warshall’s (all pair shortest path) algorithms find the shortest path of the given directed graph. 7 Q.6 i. ii. OR iii. Give example for NP Complete problems Explain how backtracking can be applied to solve 8-queen’s problem. Apply backtracking to the problem of finding a Hamiltonian circuit in the following graph. 3 7 7 1 1 1 Write an algorithm using recursive function to find the sum of n numbers. 4 Solve the following recurrence relations 6 (a) x(n)=x(n -1) + 5 for n > 1 x(1)=0 (b) x(n)=3x(n-1) for n > 1 x(1)=4 Write the asymptotic notations used for best case, average case and 6 worst-case analysis of algorithms in detail. Write a note on quick sort Algorithm. Apply quick sort algorithm for the following array and sort the element (Take the first element as the pivot element) 24, 56,47,35,10,90,82,31,22,32,55,11. Also discuss complexity of algorithm. Sort the following list using heap sort 66,33,40,20,50,88,60,11,77,30,45,65. Also discuss the complexity of the heap sort. Q.4 i. ii. 3 7 7 ****** 

ii.

Marking Scheme IT3CO06 Design and Analysis of Algorithms Q.1 i. What is the asymptotic runtime for traversing all nodes in a binary search tree with n nodes and printing them in order? (b) O(n) ii. What is the best time complexity of bubble sort? (c) N iii. What is recurrence for worst case of QuickSort and what is the time complexity in Worst case? (b) Recurrence is T(n)=T(n-1) + O(n) and time complexity is O(n^2) iv. In a Max heap the largest key is at (a) The root v. Which of the following algorithms is the best approach for solving Huffman codes? (b) Greedy algorithm vi. Dijkstra’s Algorithm cannot be applied on ______________ (b) Graphs having negative weight function vii. The Knapsack problem is an example of ____________ viii. Bellmann ford algorithm provides solution for ___________ problems. (d) Single source shortest path ix. What happens when the backtracking algorithm reaches a complete solution? (b) It continues searching for other possible solutions x. Which one of the following is an application of the backtracking algorithm? (d) Crossword Q.2 i. ii. OR iii. Q.3 i. 1 OR iii. Apply quick sort algorithm for the following array and sort the element Sorting 4 marks Analysis 3 marks Sort the following list using heap sort Sorting 5 marks Analysis 2 marks 7 7 1 1 Q.4 i. ii. OR iii. 1 1 Q.5 i. ii. 1 1 1 OR iii. 1 1 Q.6 i. ii. Algorithm using recursive function to find the sum of n numbers Solve the following recurrence relations (a) x(n)=x(n -1) + 5 for n > 1 x(1)=0 3 marks (b) x(n)=3x(n-1) for n > 1 x(1)=4 3 marks Asymptotic notations used for best case, average case and worst-case analysis of algorithms Function 3 marks Graph 3 marks 4 6 OR iii. Quick sort Algorithm. 3 6 General principle of greedy algorithm. 3 Using Dijkstra’s algorithm, find the shortest path from the source node 0. 7 Complete Solution Huffman coding algorithm 4 marks 7 Example 3 marks Differentiate between divide and conquer and dynamic programming 1 mark for each difference (1 mark * 3) Solve the following instance of the 0/1 knapsack problem given the knapsack capacity is W=5 Steps 5 marks Solution 2 marks Using Floyd Warshall’s (all pair shortest path) algorithms find the shortest path of the given directed graph. Complete solution 3 Example for NP Complete problems Backtracking can be applied to solve 8-queen’s problem. Explanation 4 marks Tree 3 marks Apply backtracking to the problem of finding a Hamiltonian circuit in the following graph. Complete Solution ****** 3 7 7 7 7 

https://flipbooks.fleepit.com/f-45512-daa_pyqs

Fleepit Digital © 2021