BCA V Semester Design and Analysis of Algorithms Exam Jan 2024 PDF

# BCACACN 501 ## Fifth Semester B.C.A. Degree Examination, December 2023/January 2024 **(NEP 2020) (2023 – 2024 Batch Onwards)** **DESIGN AND ANALYSIS OF ALGORITHMS (DSCC)** * Time: 2 Hours * Max. Marks: 60 **Note**: Answer any six questions from Part – **A** and any one full question in each...

# BCACACN 501 ## Fifth Semester B.C.A. Degree Examination, December 2023/January 2024 **(NEP 2020) (2023 – 2024 Batch Onwards)** **DESIGN AND ANALYSIS OF ALGORITHMS (DSCC)** * Time: 2 Hours * Max. Marks: 60 **Note**: Answer any six questions from Part – **A** and any one full question in each Unit from Part – **B**. ## Part - A (6x2=12) 1. a) What are double linked list and queue data structures ? 2. b) Define sets and dictionaries. 3. c) List any two importance of Brute force approach. 4. d) Define convex and convex hull. 5. e) Define decrease and conquer technique and list any two of its variations. 6. f) Write an algorithm to find height of Binary tree. 7. g) What is Greedy problem? List requirements of the solution at each step in Greedy approach. 8. h) What is NP complete problem? Write example. ## Part - B ### Unit - I (6+6) 1. a) Explain Algorithm design and analysis process with flow diagram. 2. b) Write an algorithm to find the factorial of a number using recursion and also perform mathematical analysis. ### Unit - II (4+4+4) 1. a) Write an algorithm to sort N numbers using selection sort. Derive the number of operations and time complexity. 2. b) Write and explain the algorithm for Closest-Pair Problem. Derive its complexity. 3. c) Consider the Knapsack problem with the following inputs. Solve the problem using exhaustive search. Enumerate all possibilities and indicate unfeasible solutions and optimal solution. Knapsack total capacity W = 15 kg. | Items | A | B | C | D | |---|---|---|---|---| | Weight (kg) | 3 | 5 | 4 | 6 | | Value | 36 | 25 | 41 | 34 | (4+4+4) 1. a) Write an algorithm to sort N numbers by applying Bubble sort. Derive the number of operations and time complexity. 2. b) Write and describe Brute force String Matching Algorithm. 3. c) Find the optimal solution for the Travelling Salesman problem using exhaustive search method by considering 'A' as the starting city. A diagram showing the following graph: * Node A with the value 20 * Node B with the value 34 and connected to node A with edge value 42 * Node C with the value 30 and connected to node A with edge value 30 * Node D with the value 35 and connected to node B with edge value 35 and connected to node C with edge value 12 ### Unit - III (4+4+4) 1. a) Write and explain Depth-First Search Algorithm with its time complexity. 2. b) Apply the source-removal (Decrease by one) algorithm to solve the topological sorting problem for the digraph given. A digraph showing the following: * Node a connected to node b and node f with edge value 1 * Node b connected to node c and node d with edge value 2 * Node c connected to node f with edge value 4 * Node d connected to node e and node g with edge value 3 * Node e connected to node f with edge value 5 * Node g connected to node h with edge value 6 1. c) Compute 34 × 26 using divide and conquer approach for the multiplication of two large numbers. ### Unit - IV (6+6) 1. a) Write the Prim's algorithm and find Minimum Spanning tree for the given graph. A digraph showing the following: * Node a connected to node b with edge value 1, connected to node d with edge value 5 and connected to node c with edge value 6 * Node b connected to node a with edge value 1, connected to node c with edge value 4 and connected to node d with edge value 2 * Node c connected to node a with edge value 6, connected to node b with edge value 4, connected to node d with edge value 8 and connected to node e with edge value 5 * Node d connected to node a with edge value 5, connected to node b with edge value 2, connected to node c with edge value 8 and connected to node e with edge value 6 * Node e connected to node c with edge value 5 and connected to node d with edge value 6 * Node f connected to node c with edge value 3 1. b) Construct Huffman tree and write the Huffman code for given data. | Character | Probability | |---|---| | A | 0.35 | | B | 0.1 | | C | 0.2 | | D | 0.2 | | E | 0.15 | (6+6) 1. a) Write the Kruskal's algorithms and apply Kruskal's algorithm to find a minimum spanning tree of the given graph. A diagram showing the following graph: * Node 0 connected to node 1 with edge value 7 and connected to node 4 with edge value 4 * Node 1 connected to node 0 with edge value 7 and connected to node 2 with edge value 8 * Node 2 connected to node 1 with edge value 8 and connected to node 3 with edge value 2 * Node 3 connected to node 2 with edge value 2 and connected to node 4 with edge value 9 * Node 4 connected to node 0 with edge value 4 and connected to node 3 with edge value 9 and connected to node 5 with edge value 14 * Node 5 connected to node 4 with edge value 14 and connected to node 6 with edge value 10 * Node 6 connected to node 5 with edge value 10 and connected to node 7 with edge value 6 * Node 7 connected to node 6 with edge value 6 and connected to node 8 with edge value 1 and connected to node 5 with edge value 8 * Node 8 connected to node 7 with edge value 1 and connected to node 5 with edge value 9 1. b) Draw the decision tree for the following: * (i) Minimum of three numbers. * (ii) Binary search in a four-element array.