BSc CS Sem 4 ATKT 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 (SM)
   • i) By using which method sorting is not possible?
   • ii) In binary search trees, tree walk prints the key of the root of a sub tree Between the values in its left sub tree and those in its right sub tree
   • a) post order b) preorder c) in order d) none of these
   • iii) Algorithms can be represented:
   • a) Relaxtion Improvment
   • c) Shortning costing
   • iv) Prim's and Kruskal's algorithm are examples of
   • v) A pivot element to partition unsorted list is used in., is based on the divide-and-conquer paradigm
   • B) Fill in the blanks:
   • j) ---------------is any well-defined computational procedure that takes some value. or values, as input and produces some value, or set of values, as output
   • ii) algorithm as a tool for solving a well-specified
   • iii) ----------- bounds a functions from above and below, so it defines exact asymptotic behavior
   • iv) ----------------Select the next shortest edge which does not create a cycle
   • v) IN ----------- algorithm uses a priority queue worst-case running time of insertion sort ts
   • C) Explain the following terms in one or two lines (5M)
   • i) Asymptotic Analysis
   • iii) Correctness of Algorithm
   • v) N-ary tree
4. Q2 Attempt the following: (Any THREE) (15M) A Write short note what is Algorithm B Briefly describe the Master method for solving recurrences C Explain Running time analysis in detail D Write a note on Worst Case ,Best case,Avg case E Briefly describe the Notation” F Write a note on divide-and-conquer approach
5. Q3 Attempt the following: (Any THREE) (15M)
   • A. Explain properties of binary tree B Write a note on shortest path algorithm j C What is an AVL tree? Explain D Explain with suitable example the Kruskal algorithm F Write a note on median-of-median algorithm
6. Q4 Attempt the following: (Any THREE) (15M) A Explain Rod cutting problem that is based on dynamic programming. B what are Elements of Greedy Algorithms? C Explain Advantages and Disadvantages of Divide and Conquer strategy D write short note on Master Theorem E Explain top-down with memorization, and bottom-up in dynamic approach F Write advantages and disadvantages of greedy strategy?
7. Q5 Attempt the following: (Any THREE) (15M)
   • A. List the various properties of binary tree B What is a threaded binary tree? Explain C What is a Topological Sort? Explain it with a suitable example
   • E. What is inorder and post order traversal of a binary tree? Compute them for the

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