This document contains the question bank for the subject "CS6402- Design & Analysis of Algorithm" from the Department of Computer Science & Engineering at Chendu College of Engineering & Technology. It includes questions in 5 units that cover topics like algorithm analysis, brute force and divide-and-conquer techniques, dynamic programming, greedy algorithms, and limitations of algorithm power. The questions range from short answer to longer explanations and examples.
This document contains the question bank for the subject "CS6402- Design & Analysis of Algorithm" from the Department of Computer Science & Engineering at Chendu College of Engineering & Technology. It includes questions in 5 units that cover topics like algorithm analysis, brute force and divide-and-conquer techniques, dynamic programming, greedy algorithms, and limitations of algorithm power. The questions range from short answer to longer explanations and examples.
This document contains the question bank for the subject "CS6402- Design & Analysis of Algorithm" from the Department of Computer Science & Engineering at Chendu College of Engineering & Technology. It includes questions in 5 units that cover topics like algorithm analysis, brute force and divide-and-conquer techniques, dynamic programming, greedy algorithms, and limitations of algorithm power. The questions range from short answer to longer explanations and examples.
This document contains the question bank for the subject "CS6402- Design & Analysis of Algorithm" from the Department of Computer Science & Engineering at Chendu College of Engineering & Technology. It includes questions in 5 units that cover topics like algorithm analysis, brute force and divide-and-conquer techniques, dynamic programming, greedy algorithms, and limitations of algorithm power. The questions range from short answer to longer explanations and examples.
(Approved by AICTE, New Delhi and Affiliated to Anna University)
Zamin Endathur, Madurantakam, Kancheepuram District – 603311 +91-44-27540091/92 www.ccet.org.in
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
Question Bank Subject Name: CS6402- Design & Analysis of Algorithm Year/Sem : II/IV UNIT-I
INTRODUCTION PART-A
1. Define Algorithm 2. Write about Notion of Algorithm. 3. Write a short note on Algorithm Design and Analysis of Process. 4. What are the 2 kinds of Algorithm Efficiency 5. How can you specify Algorithms? 6. What is Pseudo Code? 7. What are the Important Problem Types? 8. How can you Classify Algorithms 9. Write the Euclid Algorithm 10. What is Sorting Problem? 11. What is Searching Problem? 12. What is Graph Problem? 13. What is Combinatorial Problem. 14. Differentiate Time Efficiency and Space Efficiency? 15. What are the features of efficient algorithm? 16. Define Order of Algorithm 17. Define Big Omega Notation. 18. What is Big ‘Oh’ Notation. 19. What are the different types of time complexity? 20. How the algorithm’s time efficiency is measured.
PART – B (16 MARKS)
1. Explain an Algorithm? 2. What are the Fundamentals of Algorithmic Problem Solving? 3. What are the Important Problem Types? 4. How Fundamentals of the Analysis of Algorithm Efficiency? 5. What is the Analysis Framework? 6. What are the Asymptotic Notations and its properties? 7. What is all Mathematical analysis for Recursive algorithms? 8. What a Binomial Coefficient is all Mathematical analysis for Non recursive algorithms? 9. Describe about Time complexity of an algorithm. 10. Illustrate about Space complexity with an algorithm. 11. What are the types of notation and compare the types of notation? 12. Write the fast exponentiaion routine without recursion. 13. Implement the binary search so that only one two way comparison is performed in each iteration. 14. What are the feautures of efficient slgorithm? Explain with an example. 15. What is space complexity? Illustrate with an example for fixed and variable part in space complexity? UNIT-II
BRUTE FORCE AND DIVIDE AND CONQUER
PART-A
1. What is Empirical Analysis?
2. Define Convex-Hull Problem. 3. What is Divide and Conquer Algorithm 4. What are the Features of Algorithm Visualization. 5. Define O-Notation. 6. What is Algorithm Visualization? 7. Define Static Algorithm Visualization? 8. What is Fibonacci Numbers? 9. What are the Classification of Algorithm Visualization? 10. What is Brute Force? 11. What are the different criteria used to improve the effectiveness of algorithm? 12. What is recursive call? 13. What is meant by Direct Recursive call? 14. Define indirect recursive call? 15. List the application areas of algorithm visualization? 16. Give some example for animation systems. 17. Define Interpolation? 18. Define Extrapolation? 19. Define profiling? 20. What is meant by basic operations.?
PART – B (16 MARKS)
1. Explain Brute Force?
2. Define Convex-Hull Problems. 3. How Exhaustive Search will be made? 4. What is Traveling Salesman Problem? 5. Explain Knapsack Problem. 6. What is Assignment problem with an example? 7. What is Divide and conquer methodology with its type? 8. How Merge sort will be made. Explain with an example? 9. Illustrate Quick sort will an example? 10. What is Binary search Explain with an example? 11. What is Strassen’s Matrix Multiplication. 12. Sort the sequence 3,1,4,1,5,9,2,6,5 using insertion sort. 13. Show the result of running shell sort on the input 9,8,7,6,5,4,3,2,1 using the increment (1,3,7). 14. Sort 3,1,4,1,5,9,5,9,2,6,5,3,5 using quick sort. 15. Trace mximum and minimum (using divide and conquer) algorithm for the following sequence 20,18,15,18,8,4,41,39,-3. UNIT-III
DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE
PART-A
1. What is articulation point?
2. List the advantages of binary search? 3. Define binary search Tree? 4. Explain the principle used in quick sort? 5. What is binary search? 6. What are the objectives of sorting algorithm? 7. Why is bubble sort called by the name? 8. What are the 3 variations in transform and conquer? 9. Explain principle of Optimality? 10. What is need for finding minimum spanning tree? 11. What is critical path? 12. What is spanning tree? 13. What is Dynamic programming? 14. What is greedy method? 15. List the advantage of greedy algorithm 16. Define the term control abstraction? 17. List the applications of minimum spanning tree? 18. Define AVL Tree 19. What do you mean by row major and column major? 20. What is Minimum Cost Spanning Tree?
PART – B (16 MARKS)
1. Briefly Explain What is Binomial Coefficient and its types.
2. Explain Warshall’s algorithm with an example? 3. Explain Floyd’ algorithm with an example? 4. Explain Optimal Binary Search Trees with an example? 5. Briefly explain Knapsack Problem with an example? 6. Memory functions with an example? 7. What is Greedy Technique with an example? 8. What is Prim’s algorithm with an example? 9. Illustrate Kruskal's Algorithm with an example? 10. Briefly explain Dijkstra's Algorithm with an example? 11. Explain in detail about Huffman Trees with an example? 12. Give a backtracking algorithm with a suitable example. 13. Using backtracking technique solve thefollowing instance for the subset prblem s=(1,3,4,5) and d=11. 14. Compare the running time of various greedy technique algorithms. 15. Distinguish between running time of various dynamic programming techniques.
UNIT-IV
ITERATIVE IMPROVEMENT PART-A
1. Define mode? 2. Define rotation? 3. What are the different types of rotations? 4. What are the drawbacks of AVL Tree? 5. What is 2-3 tree? 6. Define Heap. 7. What is a priority queue? 8. Define warshall’s algorithm? 9. Define Floyd’s algorithm? 10. Define prim’s algorithm. 11. How efficient is prim’s algorithm? 12. Define Kruskal’s algorithm? 13. What is path compression? 14. Define Dijkstra’s Algorithm? 15. Define Huffman trees? 16. What do you mean by Huffman code? 17. What is meant by compression ratio? 18. List the advantage of Huffman’s encoding? 19. What is dynamic Huffman encoding? 20. What do you mean by optimal solution?
PART – B (16 MARKS)
1. The Simplex Method
2. Explain the Maximum-Flow Problem with an example? 3. Explain Maximum Matching in Bipartite Graphs 4. Bipartite Graphs with an example? 5. Explain the The Stable marriage Problem with an example? UNIT – V
COPING WITH THE LIMITATIONS OF ALGORITHM POWER
PART-A
1. Define backtracking? 2. What is Hamiltonian cycle in an undirected graph? 3. What is Feasible solution? 4. What is optimal solution? 5. List the application of backtracking technique? 6. Given an application for knapsack problem? 7. Define subset sum problem? 8. What is heuristic? 9. State the concept of branch and bound method? 10. Give the upper bound and lower bound of matrix multiplication algorithm? 11. What is state space tree? 12. What is promising and non promising node? 13. What are the additional items are required for branch and bound compare To backtracking technique? 14. Differentiate backtracking and branch bound techniques. 15. What is called all pair shortest path problem? 16. When do you say a tree as minimum spanning tree? 17. How will you construct an optimal binary search tree? 18. What is the runtime of shortest path algorithm? 19. What is mathematical modeling? 20. What is pre structure? 21. Define Heap sort?
PART – B (16 MARKS)
1. Limitations of Algorithm Power
2. Lower-Bound Arguments 3. Explain the Decision Trees 4. Backtracking n-Queens problem 5. Explain 8-Queens problem 6. Explain the Hamiltonian Circuit Problem with an example? 7. Subset Sum Problem with an example? 8. Branch and Bound 9. Explain the Assignment problem with an example? 10. Briefly Explain the Knapsack Problem with an example? 11. Give the short notes on the Traveling Salesman Problem with an example? 12. How the Approximation Algorith will differ from NP with an example? 13. Explain the Hard Problems with an example? 14. Explain the Traveling Salesman problem with an example? 15. Explain the Knapsack problem with an example?
