BSc CS Sem 4 BSc CS Semester 4 (2018 2019) Apr 2019 FUNDAMENTALS OF ALGORITHM Question Paper - Mumbai University | munotes

Questions asked in this paper

• 2) Figures to the right indicate marks

1. Q3 Draw suitable diagrams and illustrations wherever necessary
2. Q4 Mixing of sub-questions is not allowed
3. Q1 Attempt All the Questions
   • A) Choose the correct alternative (5M)
   • i) Time taken by a known algorithm to solve a problem with worse case input gives us the
   • a) lower b) upper
   • c) both lower and upper d) None of these li) is an unambiguous specification of how to solve a class of problems
   • a) program b) instruction
   • c) algorithm d) none of these
   • iii) BST is the abbreviation for
   • c) Binary Solution Technique d) None of these
   • iv) The matching algorithm on a sequence of length n runs in time
   • v) A path that starts and ends on the same vertex is called
   • a) cycle b) tree
   • c) spanning tree d) none of these the blanks( rapidly, longest, shortest, slowly, child, parent, tree, linked-list) (5M)
4. Q1 Leaf nodes represent the nodes that do not have any
   • ii) Pre-order and Post-order traversals are operations associated with data structure
   • iii) Prim’s algorithm is an example of path problem
   • iv) The sequential search runs in time
   • v) The n-log-n function grow a little more than the linear function
   • C) Explain the following terms in one or two lines (5M)
5. Q1 Big-Omega
   • v) Selection algorithms
6. Q2 Attempt the following: (Any THREE) (15M) What is Asymptotic analysis of an algorithm? Explain Paper Subject Code: 78901 Fundamentals of Algotrithm What is divide-and —conquer method of problem solving? Given an example where this method is used C Write a note on method of guessing and confirming D_ Write the algorithm for printing lines of a file in reverse order Write a note on commonly used logarithms and summations in algorithmic analysis F Explain how to compare algorithms. Give example Attempt the following: (Any THREE) (15M) What is an AVL tree? Explain its characteristics What is a traversal of a tree? Compute any two such traversals for the following tree Briefly describe the concept of topological sorting. Give example Explain with suitable example the adjacency list and adjacency matrix representations of a graph. Give example E What is a shortest path problem? Explain any one algorithm for finding shortest path in a F Define graph. Differentiate between directed and undirected graph. Give examples
7. Q4 Attempt the following: (Any THREE) (15M) What is breadth-first traversal of a tree? Give the algorithm for performing a breadth-first traversal on a tree Write a note on algorithm design techniques Briefly explain the Longest Common Subsequence problem Explain any two problems that can be solved using dynamic programming E What are the elements of greedy algorithm? Explain F Explain the concept of Classification by Implementation Method
8. Q5 Attempt the following: (Any THREE) (15M) Write a note on median-of-median algorithm Explain the structure of threaded binary tree? Give suitable example to illustrate the Define algorithm. State its essential characteristics D_ Write a note on Master theorem. Give example Write a note on partition based selection algorithms F Write a note on upper and lower bounds of algorithm

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