Name of the Institute : Babu Banarasi Das National Institute of Technology & Management
Degree : MCA
Department : Computer Applications
Subject Code/Name : (MCA-312) Design & Analysis of Algorithm
Year : 2nd
Semester : 3rd
Document Type : Question Bank
Website : bbdnitm.ac.in
Download Model/Sample Question Paper :https://www.pdfquestion.in/uploads/bbdnitm.ac.in/3151-MCA-312-Design&Analysis-of-Algorithm-QuestionBank.pdf
BBDNITM Analysis of Algorithm Question Paper
Unit I
1) What is an Algorithm? What is the need to study Algorithms?
2) Define : a) Time Efficiency b) Space Efficiency
Related : BBDNITM MCA112 Computer Organisation & Architecture Question Bank : www.pdfquestion.in/3146.html
3) Briefly discuss the Algorithm Analysis Framework. Write a note on measuring the input size of an algorithm. What are different ways of measuring the running time of an algorithm?
4) What is Order of Growth? Define Worst case, Average case and Best case efficiencies.
5) Explain the Linear Search algorithm.
6) Give the general plan for analyzing the efficiency of Recursive algorithms with an eg.
7) Give an algorithm to find the smallest element in a list of n numbers and analyze the efficiency.
8) Give an algorithm to check whether all the elements in a list are unique or not and analyze the efficiency.
9) State the Master theorem and its use.
10) Explain the Quick Sort algorithm with an example and also draw the tree structure of the recursive calls made. Analyze the efficiency of Quick sort algorithm.
11) What is the solution of the recurrence T(n) = T(n/2) + n log n, T(1) = 1 ?
Unit II
1) Give the algorithm to find the height of a Binary tree and analyze the efficiency.
2) Explain Strassen?s Matrix multiplication with an example and analyze the efficiency.
3) Give the Insertion Sort algorithm and analyze the efficiency.
4) Give an algorithm to multiply two matrices of order N * N and analyze the efficiency.
5) What is Heap? What are the different types of heaps? Explain how do you construct heap? Explain the Heap Sort algorithm with an example.
6) Apply Quick sort algorithm to sort the list E,X,A,M,P,L,E in alphabetical order. Draw the tree of recursive calls made.
7) Explain the Merge Sort algorithm with an example and also draw the tree structure of the recursive calls made. Analyze the efficiency of Merge sort algorithm
8) Suppose that we had defined AVL trees to be binary search trees in which, for each node v, the heights of the left and right subtrees of v differ by at most 2 (instead of at most 1). Let ah be the minimum possible number of keys in such a tree of height h. (Define height as the length of the longest path from the root to an external node (i.e., to a leaf in the extended tree.) Then a0 = 0, a1 = 1, and a2 = 2. Give a recurrence for the value of ah when h = 3. (You don?t have to solve the recurrence.)
9) Give the Binary search algorithm and analyze the efficiency.
10) Write an algorithm for finding the largest key in a B-Tree.
11) Construct a 2-3 tree for the list 9,5,8,3,2,4,7
12) Show that Two Binomial heaps can be combined in O(log n) steps where the total number of nodes in the two trees is n.
Unit III
1) What are Huffman trees? Explain how to construct Huffman trees with an eg.
2) Explain the subset sum problem with an example.
3) Explain the Branch and Bound technique with an example.
4) What is amortized efficiency?
5) Write an algorithm for multiplying two square matrices of order n. What is the time complexity of the algoritm?Explain.
6) Write a pseudo code for a divide and conquer algorithm for finding values of both the largest and the smallest elements in any array of n numbers
7) Explain Divide and Conquer technique and give the general divide and conquer recurrence.
8) What is a rotation in AVL tree used for? Write about the efficiency of AVL trees?
9) Explain the concept of Backtracking with an example. How is it implemented in knapsack problem.
10) What is n-Queen?s problem? Generate the state space tree for n = 4.
Unit IV :
1) Draw a decision tree and find the number of key comparisons for the worst and average cases for the three-element basic bubble sort
2) Prove that any weighted connected graph with distinct weights has exactly one minimum spanning tree
3) Write an algorithm for finding an element in an optimal binary search tree
4) Describe Warshall?s algorithm for finding the transitive closure of a digraph
5) Construct a heap for the list 1,8,6,5,3,7,4 by successive key insertions (top-down algorithm)
6) Explain Kruskal?s algorithm with an example
7) Explain Dijkstra?s algorithm with an example.
8) Explain DFS and BFS with an example and analyze the efficiency
9) Explain Prim?s algorithm with an eg. Prove that Prim?s algorithm always yields a minimum spanning tree.
10) Write an algorithm for depth first search of a graph and explain with an example
11) In the flow network each direction as is labeled with its capacity. Illustrate Ford-Fulkerson algorithm to find the maximum flow with example.
Unit IV
1) What are Decision Trees? Explain.
2) For each of the following assertions, indicate whether it is True : known to be true, False: known to be false, or Unknown: unknown based on our current scientific knowledge. In each case provide a short explanation for your answer.
(i) No problems in NP can be solved in polynomial time. (ii) Every NP-complete problem requires at least exponential time to be Solved.
3) Write short note on the following
i) Randomized algorithm
ii) Approximation algorithm
4) Explain Euclids Algorithm to find the GCD of two integers with an eg.
5) Compute whether the pattern P = 10100111 is present in the string T = 1001010100111 or not.
6) Describe RSA crypto systems.
7) Discuss about data structure for disjoint sets and its algorithms for finding connected components of a graph.
8) Define P, NP and NP-Complete problems.
9) Explain the concept of input enhancement in String Matching