BIHAR ENGINEERING UNIVERSITY Design and analysis of algorithms previous year question. BEU computer science engineering question paper solution. Design and Analysis of Algorithms question paper solution 2022.
(a) Any decision trees that sorts n elements has height
(i) Ω(lg n)
(ii) Ω(n)
(iii)Ω(n lg n)
(iv)Ω(n2)
(b) Which one of the following is an Sapplication of Queue Data Structure?
(i) When a resource is shared among multiple consumers
(ii) When data is transferred asynchro- MHFMOD nously (data not necessarily received at same rate as sent) adjust between two processes
(iii) Load balancing
(iv) All of the above
(c) The complexity of binary search algorithm is
(i) O(n)
(ü) O(logn)
(iii) O(n²)
(iv) O(nlogn)
(d) In linear search algorithm the worst case occurs when
(i) the item is somewhere in the middle of the array
(ii) the item is not in the array at all
(ii) the item is the last element in the array
(iu) the item is the last element in the array or is not there at all
(e) Given an unsorted array. The array has dua this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?
(i) Insertion sort with time complexity 0(kn)
(ii) Heap sort with time complexity O(n log k)
(iii) Quick sort with time complexity O(klog k)
(iv) Merge sort with time complexity O (k log k)
(f)Approach of dynamic programming is similar to
(i) parsing
(ii) hash table
(iii) divide and conquer algorithm
(iv) greedy algorithm
(g)In the divide and conquer process breaking the problem into smaller su problems is the responsibility of
(i) divide/break
(ii) sorting/divide
(iii) conquer/solve
(iv) merge/combine
(h)A priority queue is implemented as a Max-heap. Initially it has 5 elements. The level order traversal of the heap is 10, 8, 5, 3, 2. Two new elements ‘1’ and 7′ are inserted into the heap in that order. The level order traversal of the heap after the insertion of the elements is
(i) 10, 8, 7, 5, 3, 2, 1
(i) 10, 8, 7, 2, 3, 1,510
(ii) 10, 8, 7, 1, 2, 3, 5
(iv) 10, 8, 7, 3, 2, 1, 5
(i) If a problem can be solved by combining optimal solutions to non- overlapping problems, the strategy is called
(i) dynamic programming
ii) greedy
(iii) divide and conquer
(iv) recursion
(j) The choice of polynomial class has led to the development of an extensive theory called
(i) computational complexity
(ii) time complexity
(iii) problem complexity
(iv) decision complexity
BEU Design and Analysis of Algorithms question solution pdf is provided below
- (a) Calculate the time complexity following problem using divide and conquer strategies:
(i) T(n) = √nT(=√n) + n, n >2 = a, n ≤2
(ⅱ) T(n)=T(n-1)+1/n, n > 1 = 1, n=1
(b) Write time function and calculate the time complexity, space complexity and number of function calls of the following pseudocode using substitution method:
rec (n) {
if (n≤1) return(1); else { rec (n/2); for (i=1; i < n; i++) printf(“algorithm”); }
3. (a) Explain the working of merge sort, algorithm with an example. Give the complexity calculation of merge sort.
(b) What are the rules of manipulate Big-Oh expression and about the typical growth rates of algorithms.
4. (a) What is heap sort? What is the effect of calling MAX-HEAPIFY(A, i) when the element A[i] is larger than its children?
(b) Explain how radix sort works, to what inputs it can be applied and what is its asymptotic complexity?
5. What do you mean by optimal solution in greedy approach? Define the properties and function of greedy approach. Consider the graph G (V, E) given below. Find the minimum algorithms. spanning tree by Prim’s
6. Find the optimal way to multiply the following matrices to perform the fewest multiplications:
7. You are given a graph containing n vertices and m edges and given that the graph doesn’t contain cycle of odd length. What is the time complexity of the best known algorithm to find out whether the graph is bipartite or not?
8. What is activity selection problem? Suppose that instead of always selecting the first activity to finish, we select the last activity to start that is compatible with all previously selected activities. Describe how this approach is a greedy algorithm, and prove that it yields an optimal solution.
9.Write short notes on the following:
(a) Cook’s theorem
(b) Approximation algorithms
CLICK HERE TO JOIN WHATSAPP GROUP
BEU Design and Analysis of Algorithms SOLUTION 2022 ==> Available soon
BEU Design and Analysis of Algorithms question paper 2022 ==> Download