Summary

This document is a past paper containing questions on algorithms, including short answer and long answer questions. Topics covered range from algorithm design techniques to problem types used in algorithm design. The paper also covers basic concepts such as time and space complexity, various problem solving strategies, and asymptotic notations.

Full Transcript

Short Answer Questions: 1. Define Algorithm & Notion of algorithm. 2. What is analysis framework? 3. What are the algorithm design techniques? 4. How is an algorithm‘s time efficiency measured? 5. Mention any four classes of algorithm efficiency. 6. Define Order of Growth. 7. State the following Ter...

Short Answer Questions: 1. Define Algorithm & Notion of algorithm. 2. What is analysis framework? 3. What are the algorithm design techniques? 4. How is an algorithm‘s time efficiency measured? 5. Mention any four classes of algorithm efficiency. 6. Define Order of Growth. 7. State the following Terms. (i) Time Complexity (ii) Space Complexity 8. What are the various asymptotic Notations? 9. What are the important problem types? 10. Define algorithmic Strategy (or) Algorithmic Technique. 11. What are the various algorithm strategies (or) algorithm Techniques? 12. What are the ways to specify an algorithm? 13. Define Best case Time Complexity. 14. Define Worst case Time Complexity. 15. Define Average case time complexity. 16. What are the Basic Efficiency Classes. 17. Define Asymptotic Notation. 18. Define O / θ / Ω 19. Define Tail recursion, principle of optimality, feasible solution, optimal solution, objective function, overlapping problems, E-node, Live node, dead node, Memoization, pendant vertex, Edge Relaxation in BF Algo Long Answer Questions: Explain some of the problem types used in the design of algorithm. Discuss the fundamentals of analysis framework. Explain the various asymptotic notations used in algorithm design. What is Pseudo-code? Explain with an example. Greedy Method What is the difference between DFS & BFS? What is Greedy method? Explain Compare Greedy algorithm & Dynamic programming. Define Knapsack’s problem. Or Explain the Knapsack Problem Expalin the difference between depth first search & Breadth first search Solve the all pair shortest path problem for the diagraph with the weighted matrix given below:- a b c d a0 ∞3∞ b2 0∞∞ c∞7 0 1 d6∞∞ 0 Backtracking Define/Explain Travelling salesman problem. State principle of backtracking. Compare Backtracking & Branch and Bound techniques with an example. In Backtracking strategy, how the problem can be categorized? How is a solution determined in backtracking algorithm? Obtain all possible solutions to 4-Queen‘s problem. Generate atleast 3-solutions for 5-Queen‘s problem. Draw a pruned state space tree for a given sum of subset problem: S={3,4,5,6} and d=13 Explain the n-Queen‘s problem & discuss the possible solutions. Apply backtracking technique to solve the following instance of subset sum problem : S={1,3,4,5} and d=11 Explain subset sum problem & discuss the possible solution strategies using backtracking. B&B Define hamiltonian circuit problem Define branch and bound. Traveling salesman problem. What are the applications of branch & bound?(or) What are the examples of branch & bound? Discuss the solution for Travelling salesman problem using branch & bound technique. Short note on LIFO B&B , FIFO B&B, LCBB General Questions: Differentiate between Dynamic programming and Greedy strategy Advantages of B&B / DP / Greedy / BT Dis Adv of B&B / DP / Greedy / BT Explain in detail about Knapsack problem. Explain traveling salesman problem with example.

Use Quizgecko on...
Browser
Browser