Analysis and Design of Algorithms Past Paper PDF - GUJARAT Technical University - Summer 2022
Document Details
Uploaded by Deleted User
2022
GUJARAT TECHNOLOGICAL UNIVERSITY
Tags
Summary
This is a past paper for a BE-semester V(NEW) Examination in Analysis and Design of Algorithms from Summer 2022 at Gujarat Technological University. The paper covers multiple questions spanning various algorithmic concepts, including time and space complexity, sorting algorithms (like quick sort), searching (binary search), and selection sort and more. Students will need to demonstrate understanding of dynamic programming, greedy algorithms, backtracking, and graph theory concepts as included in the exam questions.
Full Transcript
Seat No.: ________ Enrolment No.___________ GUJARAT TECHNOLOGICAL UNIVERSITY BE - SEMESTER–V(NEW) EXAMINATION – SUMMER 2022 Subject Code:3150703 Date:07/06/2022 Subject Name:Analys...
Seat No.: ________ Enrolment No.___________ GUJARAT TECHNOLOGICAL UNIVERSITY BE - SEMESTER–V(NEW) EXAMINATION – SUMMER 2022 Subject Code:3150703 Date:07/06/2022 Subject Name:Analysis and Design of Algorithms Time:02:30 PM TO 05:00 PM Total Marks: 70 Instructions: 1. Attempt all questions. 2. Make suitable assumptions wherever necessary. 3. Figures to the right indicate full marks. 4. Simple and non-programmable scientific calculators are allowed. Marks Q.1 (a) Define Algorithm, Time Complexity and Space Complexity 03 (b) Explain: Worst Case, Best Case and Average Case Complexity 04 with suitable example. (c) Sort the following list using quick sort algorithm:< 5, 07 3 ,8 ,1 ,4 ,6 ,2 ,7 > Also write Worst and Best case and Average case of quick sort algorithm. Q.2 (a) Write an algorithm of Selection Sort Method. 03 (b) Demonstrate Binary Search method to search Key = 14, form the 04 array A= (c) Write the Master theorem. Solve following recurrence using it. 07 (i)T(n)= T(n/2) + 1 (ii) T(n)=2T(n/2) + n log n OR (c) Solve following recurrence relation using iterative method T(n) = 07 T(n - 1) + 1 with T(0) = 0 as initial condition. Also find big oh notation Q.3 (a) What is Principle of Optimality? Explain its use in Dynamic 03 Programming Method (b) Find out LCS of A={K,A,N,D,L,A,P} and B = {A,N,D,L} 04 (c) Discuss Assembly Line Scheduling problem using dynamic 07 programming with example. OR Q.3 (a) Give the characteristics of Greedy Algorithms 03 (b) Give difference between greedy approach and dynamic 04 programming. (c) Consider Knapsack capacity W=15, w = (4, 5, 6, 3) and v=(10, 15, 07 12, 8) find the maximum profit using greedy method. Q.4 (a) Explain: Articulation Point, Graph, Tree 03 (b) Find Minimum Spanning Tree for the given graph using Prim’s 04 Algorithm. 1 (c) Explain Breath First Traversal Method for Graph with algorithm 07 with example. OR Q.4 (a) Explain Huffman code with Example. 03 (b) Write the Kruskal’s Algorithm to find out Minimum Spanning 04 Tree. Apply the same and find MST for the graph given below (c) Explain fractional knapsack problem with example. 07 Q.5 (a) What is string-matching problem? Define valid shift and invalid 03 shift. (b) Define P, NP, NP-Hard and NP-Complete Problem 04 (c) Explain Backtracking Method. What is N-Queens Problem? Give 07 solution of 4- Queens Problem using Backtracking Method. OR Q.5 (a) Explain “P = NP ?” problem. 03 (b) Explain Minimax principal. 04 (c) What is Finite Automata? Explain use of finite automata for string 07 matching with suitable example. 2
