ADSA 2Marks Questions PDF

## Short Answer (2Marks) Question Bank ### Unit No: I (Unit Name: INTRODUCTION TO ALGORITHMS, AVL TREES, B TREES) #### Short Answer (10Marks) Questions | Q.NO | Questions | M | |---|---|---| | 1 | Define an algorithm. List the desirable properties of the algorithm. | 2 | | 2 | Classify the best,...

## Short Answer (2Marks) Question Bank ### Unit No: I (Unit Name: INTRODUCTION TO ALGORITHMS, AVL TREES, B TREES) #### Short Answer (10Marks) Questions | Q.NO | Questions | M | |---|---|---| | 1 | Define an algorithm. List the desirable properties of the algorithm. | 2 | | 2 | Classify the best, worst and average case time complexities for an algorithm? | 2 | | 3 | Write an algorithm using recursive function to find sum of n numbers. | 2 | | 4 | Compare time complexity and space complexity | 2 | | 5 | Define Asymptotic notation. | 2 | | 6 | Identify how an algorithm's time efficiency measured? | 2 | | 7 | Define Omega Notations | 2 | | 8 | Define Little-oh notation. | 2 | | 9 | What are Applications of AVL Trees? | 2 | | 10 | What are Applications of B Trees? | 2 | **Course Outcome:** - **CO-1** Illustrate the working of the advanced tree data structures and their applications. - **CO-2** Understand the Graph data structure, traversals and apply them in various contexts. (L2) ### Unit No: II (Unit Name: Heap trees, Graphs, Divide & Conquer) #### Short Answer (10Marks) Questions | Q.NO | Questions | M | |---|---|---| | 1 | Define Heap Tree. | 2 | | 2 | Define Min Heaps and Max Heap. | 2 | | 3 | Define Graph. | 2 | | 4 | List out representations of Graphs. | 2 | | 5 | List out graph travelling techniques. | 2 | | 6 | Define Connected Components with example. | 2 | | 7 | Define Bi connected Components with example. | 2 | | 8 | Define Convex Hull. | 2 | | 9 | Develop an algorithm for control abstraction of divide-and conquer | 2 | | 10 | Compare and contrast quick sort and Merge sort. | 2 | **Course Outcome:** - **CO-1** Illustrate the working of the advanced tree data structures and their applications. - **CO-2** Understand the Graph data structure, traversals and apply them in various contexts. (L2) ### Unit No: III (Unit Name: Greedy Method, Dynamic Programming) #### Short Answer (10Marks) Questions | Q.NO | Questions | M | |---|---|---| | 1 | Compare and contrast Greedy Technique and divide and conquer strategy | 2 | | 2 | Define a spanning tree? Give an example | 2 | | 3 | Outline the steps required to develop a greedy algorithm? | 2 | | 4 | Distinguish between Greedy method and Dynamic programming | 2 | | 5 | Explain the control abstraction for Greedy method. | 2 | | 6 | Define feasible and optimal solution. | 2 | | 7 | Define the Principle of Optimality. | 2 | | 8 | Explain the applications of Greedy method | 2 | | 9 | Write an applications of Dynamic Programming | 2 | | 10 | Explain the principle of dynamic programming? | 2 | **Course Outcome:** - **CO-3** Recommend appropriate data structures based on the problem being solved - **CO-4** Analyze algorithms with respect to space and time complexities (L4) - **CO-5** Design new algorithms (L6) ### Unit No: IV (Unit Name: Back Tracking, Branch & Bound) #### Short Answer (10Marks) Questions | Q.NO | Questions | M | |---|---|---| | 1 | Explain general Backtracking method | 2 | | 2 | What is Hamiltonian cycle? Give an example | 2 | | 3 | Define the Sum of subsets problem in Backtracking. | 2 | | 4 | List out the factors that influence the efficiency of the backtracking algorithm? | 2 | | 5 | What is the Graph colouring problem in Backtracking? | 2 | | 6 | What is the solution vector for 8-queens problem in Backtracking? | 2 | | 7 | List out the application for Backtracking. | 2 | | 8 | What are the applications of Branch and Bound | 2 | | 9 | Develop an algorithm for control abstraction of Branch and Bound | 2 | | 10 | Define Travelling sales person problem | 2 | **Course Outcome:** - **CO-3** Recommend appropriate data structures based on the problem being solved - **CO-4** Analyze algorithms with respect to space and time complexities (L4) - **CO-5** Design new algorithms (L6) ### Unit No: V (Unit Name: NP-Hard and NP- Complete) #### Short Answer (10Marks) Questions | Q.NO | Questions | M | |---|---|---| | 1 | What is class P and NP? | 2 | | 2 | Define NP-completeness. | 2 | | 3 | Define node cover decision problem. | 2 | | 4 | Show the relationship between P and NP graphically. | 2 | | 5 | Define non-deterministic algorithm. | 2 | | 6 | Define the NP-Hard problem. | 2 | | 7 | Define the NP-Complete problems. | 2 | | 8 | Define Cook's theorem. | 2 | | 9 | Define NP Hard Graph Problems. | 2 | | 10 | Define NP Hard Scheduling Problems. | 2 | **Course Outcome:** - **CO-3** Recommend appropriate data structures based on the problem being solved - **CO-4** Analyze algorithms with respect to space and time complexities (L4) - **CO-5** Design new algorithms (L6)