DEPARTMENT OF INTELLIGENT COMPUTING & BUSINESS SYSTEMS ST JOSEPH ENGINEERING COLLEGE, MANGALURU Artificial Intelligence & Machine Learning Module-1 Question Bank Course: Design and Analysis of Algorithms Course Code: 22AIM42 Faculty: Ms Renuka Tantry Note: The question bank serves as reference or study guide only Use diagrams, programs and illustration wherever possible. The questions include theoretical concepts only. Be prepared for problems covered in the curriculum 1. What do you understand by an algorithm? Write an algorithm to find the ged of two positive integers. 2. Define Algorithm, Explain the characteristics of algorithms. 3. Discuss the various stages of algorithm design and analysis process. 4, Explain different asymptotic notations used to analyze an algorithm, with an example for cach, 5. Explain Best Case, Worst Case and Average Case efficiencies of an algorithm with suitable example. 6. Describe the general plan of mathematical analysis of recursive algorithms. Set up a recurrence relation for Tower of Hanoi and find its efficiency. 7. What are space and time complexities of an algorithm? Explain with suitable examples. 8. Write an algorithm to search a key using sequential search. Obtain its efficiencies. 9. Explain general plan of mathematical analysis of recursive algorithms. Apply the same for the recursive algorithm to find the factorial of a given number. 10. Explain the general framework of algorithm analysis 11. With at least two examples each, Define and explain 0, @ and 2 12. Explain the general plan of mathematical analysis of non-recursive algorithm with an example. 13, Explain the method of comparing orders of growth of two functions using limits. Also compare the following functions: (i) logn and Vn (ii) (logen)? and logon? 14, Calculate the efficiency of an algorithm for finding the largest element in an array. 15. Write an algorithm to perform matrix multiplication and calculate its efficiency. 16. For the following algorithms, indicate:a) Natural size metric for the inputs (b) Basic operations (c) Whether the basic operation counts can be different for inputs of the same size (i) Computing sum of ‘n’ numbers Gi) Computing x” (iii) Finding largest element in a list of ‘n’ numbers (iv) Euclid’s algorithm 17. Prove that: (i) % n(n-1) © @(n°) in! © Q (2n) ii, 3n'+2n? € O(n’) (ii) 10n*+5 € O(n’) 18. Consider the following algorithm Algorithm X(int N} "se: for =O 10.N NAP); (i) What does this algorithm comput: (ii) What is the basic operation? (ii) How many times basic operation is executed? (iv) What is the efficiency class of this algorithm? 19. Consider the following algorithm Algorithm Mystery int N) toN =S+i*i Return S (i) What does this algorithm compute? (i) What is the basic operation? (iii) How many times basic operation is executed? (iv) What is the efficiency of this algorithm? 20. Consider the following algorithm Algorithm PQ(AI0..1-1.0...0-1]) for nO 100-2 return false: end for end for reiurn true (i) What does this algorithm compute? (ii) What is the basic operation? (ii) log2n and Inn (ii) How many times basic operation is executed? (iv) What is the efficiency of this algorithm?21. Consider the following algorithm Algorithm Test{n) s=0 for i-ttondo forj=1tondo sari retum s (i) What does this algorithm compute’ (ii) What is the basic operation? (ii) How many times basic operation is executed? (iv) What is the efficiency of this algorithm? 22. Consider the following algorithm Algorithm GUESS(AIIID for i=0 to n-1 do for) =O1wido AULD (i) What does this algorithm compute? (ii) What is the basic operation? (iii) How many times basic operation is executed? (iv) What is the efficiency of this algorithm? 23, Write a note on the following: (i) Important Problem Types (ii) Empirical Analysis of Algorithms 24, Design an algorithm to check whether all elements in an array are distinct. What is its time complexity? 25. Write an algorithm to compute n! recursively. Set up a recurrence relation for the algorithm’s basic operation and solve it. 26, Discuss the important problem types. 27. Explain Empirical Analysis of Algorithms. 28, List out the key differences between mathematical and empirical analysis of algorithms