Scribd Logo
Upload

Welcome to Scribd!

  • 49 views

    2019-20 University Paper

    Uploaded by

    Khushi Pachauri
    This document contains a 7 section exam on the design and analysis of algorithms. It includes questions on comparing algorithm performance, analyzing time complexities of functions, properties of different algorithms like binary search and greedy algorithms, and applications like fast Fourier transforms. Later sections include problems on sorting, trees, graphs, strings, knapsack, and approximation algorithms. Students are asked to solve recurrences, implement algorithms on given inputs, compare different paradigms, and determine time complexities.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    2019-20 University Paper

    Uploaded by

    Khushi Pachauri
    49 views2 pages
    This document contains a 7 section exam on the design and analysis of algorithms. It includes questions on comparing algorithm performance, analyzing time complexities of functions, properties of different algorithms like binary search and greedy algorithms, and applications like fast Fourier transforms. Later sections include problems on sorting, trees, graphs, strings, knapsack, and approximation algorithms. Students are asked to solve recurrences, implement algorithms on given inputs, compare different paradigms, and determine time complexities.

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains a 7 section exam on the design and analysis of algorithms. It includes questions on comparing algorithm performance, analyzing time complexities of functions, properties of different algorithms like binary search and greedy algorithms, and applications like fast Fourier transforms. Later sections include problems on sorting, trees, graphs, strings, knapsack, and approximation algorithms. Students are asked to solve recurrences, implement algorithms on given inputs, compare different paradigms, and determine time complexities.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    49 views2 pages

    2019-20 University Paper

    Uploaded by

    Khushi Pachauri
    This document contains a 7 section exam on the design and analysis of algorithms. It includes questions on comparing algorithm performance, analyzing time complexities of functions, properties of different algorithms like binary search and greedy algorithms, and applications like fast Fourier transforms. Later sections include problems on sorting, trees, graphs, strings, knapsack, and approximation algorithms. Students are asked to solve recurrences, implement algorithms on given inputs, compare different paradigms, and determine time complexities.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    Printed Page 1 of 2 Sub Code: RCS502

    Paper Id: 110502 Roll No: 0 0 0 0 0 0 0 0 0 0 0 0 0

    B. TECH.
    (SEM V) THEORY EXAMINATION 2019-20
    DESIGN AND ANALYSIS OF ALGORITHM
    Time: 3 Hours Total Marks: 70
    Note: 1. Attempt all Sections. If require any missing data; then choose suitably.

    SECTION A

    1. Attempt all questions in brief. 2 x 7 = 14


    a. How do you compare the performance of various algorithms?
    b. Take the following list of functions and arrange them in ascending order of
    growth rate. That is, if function g(n) immediately follows function f(n) in your
    list, then it should be the case that f(n) is O(g(n)).
    f1(n) = n2.5, f2(n) = √2n, f3(n) = n + 10, f4(n) = 10n, f5(n) = 100n, and
    f6(n) = n2 log n
    c. What is advantage of binary search over linear search? Also, state limitations of
    binary search.
    d. What are greedy algorithms? Explain their characteristics?
    e. Explain applications of FFT.
    f. Define feasible and optimal solution.
    g. What do you mean by polynomial time reduction?
    www.aktuonline.com

    SECTION B

    2. Attempt any three of the following: 7 x 3 = 21


    a. (i) Solve the recurrence T (n) = 2T(n/2) + n2+ 2n+ 1
    (ii) Prove that worst case running time of any comparison sort is Ω(nlogn)

    b. Insert the following element in an initially empty RB-Tree.


    12, 9, 81, 76, 23, 43, 65, 88, 76, 32, 54. Now Delete 23 and 81.

    c. Define spanning tree. Write Kruskal’s algorithm for finding minimum cost
    spanning tree. Describe how Kruskal’s algorithm is different from Prim’s
    algorithm for finding minimum cost spanning tree.

    d. What is dynamic programming? How is this approach different from recursion?


    Explain with example.

    e. Define NP-Hard and NP- complete problems. What are the steps involved in
    proving a problem NP-complete? Specify the problems already proved to be
    NP-complete.

    SECTION C
    3. Attempt any one part of the following: 7x1=7
    (a) Among Merge sort, Insertion sort and quick sort which sorting technique is the
    best in worst case. Apply the best one among these algorithms to Sort the list E,
    X, A, M, P, L, E in alphabetic order.
    (b) Solve the recurrence using recursion tree method:
    T (n) = T (n/2) + T (n/4) + T (n/8) + n

    http://www.aktuonline.com
    Printed Page 2 of 2 Sub Code: RCS502

    Paper Id: 110502 Roll No: 0 0 0 0 0 0 0 0 0 0 0 0 0

    4. Attempt any one part of the following: 7x1=7


    (a) Using minimum degree ‘t’ as 3, insert following sequence of integers 10, 25,
    20, 35, 30, 55, 40, 45, 50, 55, 60, 75, 70, 65, 80, 85 and 90 in an initially empty
    B-Tree. Give the number of nodes splitting operations that take place.

    (b) Explain the algorithm to delete a given element in a binomial Heap. Give an
    example for the same.

    5. Attempt any one part of the following: 7x1=7


    (a) Compare the various programming paradigms such as divide-and-conquer,
    dynamic programming and greedy approach.

    (b) What do you mean by convex hull? Describe an algorithm that solves the
    convex hull problem. Find the time complexity of the algorithm.

    6. Attempt any one part of the following: 7x1=7


    (a) Solve the following 0/1 knapsack problem using dynamic programming.
    P=[11,21,31,33] w=[2,11,22,15] c=40, n=4.

    (b) Define Floyd Warshall Algorithm for all pair shortest path and apply the same
    on following graph:
    www.aktuonline.com

    7. Attempt any one part of the following: 7x1=7


    (a) Describe in detail Knuth-Morris-Pratt string matching algorithm. Compute the
    prefix function 𝜋 for the pattern ababbabbabbababbabb when the alphabet is
    Σ = {a,b}.

    (b) What is an approximation algorithm? What is meant by P (n) approximation


    algorithms? Discuss approximation algorithm for Travelling Salesman
    Problem.

    http://www.aktuonline.com

    You might also like