BSc CS Sem 2 BSc CS Semester 2 (2021 2022) May 2022 DESIGN ANALYSIS OF ALGORITHMS Question Paper - Mumbai University | munotes

Questions asked in this paper

1. Q1 Attempt the following. 40 marks
   • i) O(n),where O(n)stands for order n is il) notation gives the tight upper bound of the given function ili) one of is the following false?
   • iv) is a special format for organizing and storing data
   • c) Searching d) Sorting vy) A solves a problem by calling a copy of itself to work on a smaller
   • a) Method b) Searching
   • vi) A is an ordered list in which insertionand deletion are done ai
   • a) Stack b) List vil) An is the step-by-step unambiguous instructions to solve a given problem
   • a) Queue b) Algorithm
   • c) Searching d) Program is an algorithm that arranges the elements of a list in a certain order
   • a) Searching b) Sorting
   • c) Finding d) Shuffling
   • x) Which of the following algorithms has lowest worst case complexity is rearranging pairs of elements which are out of order, until no such pairs remain
   • a) Insertion b) Exchange
   • c) Selection d) Distribution Xii) order is the best possible for array sorting algorithm which Xili) is space complexity of Binary Search
   • c) log(n) d) nlog(N) stores already computed values in table
   • a) Hashing b) Memoization
   • c) Searching d) Sorting Which of the following standard algorithms is not Dynamic Programming Bellman—Ford Algorithm for single source shortest path Warshall Algorithm for all pairs shortest paths take advantage architectures to
   • a) Serial b) Parallel Which of these is a Postfix expression?
   • b) +ab Xvili) Which of the following is the disadvantage of the array?
   • a) Stack and Queue data structures can be implemented through an array
   • b) Index of the first element in an array can be negative Wastage of memory if the elements inserted in an array are lesser than the
   • d) Elements can be accessed sequentially an optimal solution to a problem contains optimal solutions to sub An ADT consists of Attempt the following(Solve any 02) [10 marks]
   • i) What is an algorithm?Explain characteristics of algorithms
   • ii) Explain Big-O notation with proper example
   • iii) Define data structure and explain its types
   • iv) Explain stack data structure and its operations in detail
2. Q3 Attempt the following(Solve any 02) {10 marks]
   • i) Write a note on recursion.Enlist application of recursion il) Given an array: 6 8 l 4 5 3 7 2 Sort using insertion sort algorithm and state the performance ili) What is searching and explain different ty pes of linear search?
   • iv) Explain Brute Force algorithm
3. Q4 Attempt the following(Solve any 02) { 10 marks
4. Q1 Explain different types of classification bs design method
   • ii) Explain greedy strategy and difterent elements of greedy algorithm
   • iii) Let us consider an algorithm A which solves problems by dividing them into five subproblems of half the size.recursively solving each subproblem and then combining the solutions in linear tme. What is the complexity of this
   • iv) What is a Dynamic Programming Strategy?
5. Q5 Attempt the following(Solve any 01) 5 marks
   • i) Convert the (X - Y /(Z + U) * V) infix expression into postfix expression
   • ii) Write an algorithm to find the largest element in an array A of size n and do iil) What is Backtracking?

Read from the scan above, so a character or two may differ. The scan is the original.