# V T U 4th Semester B.E Analysis and Design of Algorithms Question Bank

Visvesvaraya Technological University Fourth Semester B.E Computer Science and Information Science, Analysis and Design of Algorithms Question Bank

**SUBJECT: ANALYSIS AND DESIGN OF ALGORITHMSSubject Code: CSE43**

1. What is an Algorithm? What is the need to study Algorithms?

2. Explain Euclids Algorithm to find the GCD of two integers with an eg.

3. Explain Consecutive Integer Checking algorithm to find the GCD of two numbers with an eg.

4. Middle School Algorithm with an eg.

5. Explain the Seive of Eratosthenis with an eg.

6. Explain the Algorithm design and analysis process with a neat diagram.

7. Define:

a) Time Efficiency

b) Space Efficiency

8. What are the important types of problems that encounter in the area of computing.

9. What is a Data Structure? How are data structures classified?

10. Briefly explain linear and non-linear data structures.

11. What is a Set? How does it differ from a list?

12. What are the different operations that can be performed on a Set?

13. What are the different ways of defining a Set?

14. How can sets be implemented in computer application?

15. What is a Dictionary? Give an example.

16. Briefly discuss the Algorithm Analysis Framework.

17. Write a note on measuring the input size of an algorithm.

18. What are different ways of measuring the running time of an algorithm?

19. What is Order of Growth?

20. Define Worst case, Average case and Best case efficiencies.

21. Explain the Linear Search algorithm.

22. Define O, T, O notations.

23. Give the general plan for analyzing the efficiency of non-recursive algorithms with an eg.

24. Give an algorithm to find the smallest element in a list of n numbers and analyze the efficiency.

25. Give an algorithm to check whether all the elements in a list are unique or not and analyze the efficiency.

26. Give an algorithm to multiply two matrices of order N * N and analyze the efficiency.

27. Give the general plan for analyzing the efficiency of Recursive algorithms with an eg.

28. Give an algorithm to compute the Factorial of a positive integer n and analyze the efficiency.

29. Give an algorithm to solve the Tower of Hanoi puzzle and analyze the efficiency.

30. Define an explicit formula for the nth Fibonacci number.

31. Define a recursive algorithm to compute the nth Fibonacci number and analyze its efficiency.

32. What is Exhaustive Search?

33. What is Traveling Salesman Problem (TSP)? Explain with an eg.

34. Give a Brute Force solution to the TSP. What is the efficiency of the algorithm?

35. What is an Assignment Problem? Explain with an eg.

36. Give a Brute Force solution to the Assignment Problem. What is the efficiency of the algorithm?

37. Explain Divide and Conquer technique and give the general divide and conquer recurrence.

38. Define:

a) Eventually non-decreasing function

b) Smooth function

c) Smoothness rule

d) Master's Theorem

39. Explain the Merge Sort algorithm with an eg. And also draw the tree structure of the recursive calls made.

40. Analyze the efficiency of Merge sort algorithm.

41. Explain the Quick Sort algorithm with an example and also draw the tree structure of the recursive calls made.

42. Analyze the efficiency of Quick sort algorithm.

43. Give the Binary search algorithm and analyze the efficiency.

44. Give the algorithm to find the height of a Binary tree and analyze the efficiency.

45. Give an algorithm each to traverse the binary tree in Inorder, Preorder and Postorder.

46. Explain how do you multiply two large integers and analyze the efficiency of the algorithm. Give an eg.

47. Explain Strassen's Matrix multiplication with an eg. And analyze the efficiency.

48. Explain the concept of Decrease and Conquer technique and explain its three major variations.

49. Give the Insertion Sort algorithm and analyze the efficiency.

50. Explain DFS and BFS with an eg. And analyze the efficiency.

51. Give two solutions to sort the vertices of a directed graph Topologically.

52. Discuss the different methods of generating Permutations.

53. Discuss the different methods of generating Subsets.

54. What is Heap? What are the different types of heaps?

55. Explain how do you construct heap?

56. Explain the Heap Sort algorithm with an eg.

57. Explain the Horspool's algorithm with an eg.

58. Explain the concept of input enhancement in String Matching

59. What is Hashing? Explain with an eg.

60. Explain the concept of Dynamic programming with an eg.

61. What is Binomial Co-Efficient? Give an algorithm to find the binomial co-efficient and analyze the efficiency.

62. What is Transitive closure? Explain how do you find out the Transitive closure with an eg.

63. Give the Warshall's algorithm and analyze the efficiency.

64. Explain how do you solve the All-Pairs-Shortest-Paths problem with an eg.

65. Give the Flloyd's algorithm and analyze the efficiency.

66. What is Knapsack problem? Give the solution to solve it using dynamic programming technique.

67. What are Memory functions? What are the advantages of using memory functions?

68. Give an algorithm to solve the knapsack problem.

69. Explain the concept of Greedy technique.

70. Explain Prim's algorithm with an eg.

71. Prove that Prim's algorithm always yields a minimum spanning tree.

72. Explain Kruskal's algorithm with an eg.

73. Explain Quick find and Quick union implementations of disjoint subsets

74. Explain Dijkstra's algorithm with an eg.

75. What are Huffman trees? Explain how to construct Huffman trees with an eg.

76. Explain the concept of Backtracking with an eg.

77. What is a state space tree? Explain how to construct a state space tree?

78. What is n-Queen's problem? Generate the state space tree for n = 4.

79. Explain the subset sum problem with an eg.

80. What are Decision Trees? Explain.

81. Define P, NP and NP-Complete problems.

82. Explain the Branch and Bound technique with an eg.

83. Give the Approximation Algorithm for NP-Hard problems.