Scribd Logo
Upload

Welcome to Scribd!

  • 19 views

    Be Summer 2020

    Uploaded by

    coloringcraft318
    The document is a test exam for the subject Analysis and Design of Algorithms. It contains 5 questions testing knowledge of algorithm analysis techniques like asymptotic analysis, recurrences, sorting algorithms, greedy algorithms and NP-complete problems. It also contains graph problems like minimum spanning trees and string/pattern matching algorithms.

    Copyright:

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

    Be Summer 2020

    Uploaded by

    coloringcraft318
    19 views2 pages
    The document is a test exam for the subject Analysis and Design of Algorithms. It contains 5 questions testing knowledge of algorithm analysis techniques like asymptotic analysis, recurrences, sorting algorithms, greedy algorithms and NP-complete problems. It also contains graph problems like minimum spanning trees and string/pattern matching algorithms.

    Original Description:

    none

    Original Title

    2150703-BE-SUMMER-2020

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document is a test exam for the subject Analysis and Design of Algorithms. It contains 5 questions testing knowledge of algorithm analysis techniques like asymptotic analysis, recurrences, sorting algorithms, greedy algorithms and NP-complete problems. It also contains graph problems like minimum spanning trees and string/pattern matching algorithms.

    Copyright:

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

    Be Summer 2020

    Uploaded by

    coloringcraft318
    The document is a test exam for the subject Analysis and Design of Algorithms. It contains 5 questions testing knowledge of algorithm analysis techniques like asymptotic analysis, recurrences, sorting algorithms, greedy algorithms and NP-complete problems. It also contains graph problems like minimum spanning trees and string/pattern matching algorithms.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 2

    Seat No.: ________ Enrolment No.

    ___________

    GUJARAT TECHNOLOGICAL UNIVERSITY


    BE - SEMESTER– V EXAMINATION – SUMMER 2020
    Subject Code: 2150703 Date:26/10/2020
    Subject Name: ANALYSIS AND DESIGN OF ALGORITHMS
    Time: 02:30 PM TO 05:00 PM Total Marks: 70
    Instructions:
    1. Attempt all questions.
    2. Make suitable assumptions wherever necessary.
    3. Figures to the right indicate full marks.

    MARKS

    Q.1 (a) Define the terms: 03


    1) Principal of Optimality 2) Feasible solution 3) Quantifier
    (b) Analyze Binary search algorithm in best and worst case. 04
    (c) Define Asymptotic notation. Arrange the following functions in increasing 07
    order of growth.
    2n, n2, 1, log n, n log n, 3n and n.

    Q.2 (a) Define the function types: 03


    1) One-to-One 2) Into (Injective) and 3) Onto (Surjective)
    (b) What is the smallest value of n such that an algorithm whose running time is 04
    100n2 runs faster than an algorithm whose running time is 2n on the same
    machine?
    (c) Analyze Quick sort algorithm in best and worst case. 07
    OR
    (c) Analyze insertion sort algorithm in best and worst case. 07
    Q.3 (a) Differentiate divide and conquer approach with dynamic programming 03
    approach.
    (b) Solve the following recurrence using Master Theorem. 04
    T(n)=9T(n/3) + n.
    (c) Write equation for Matrix Chain Multiplication using Dynamic programming. 07
    Find out optimal sequence for multiplication:
    A1 [5 × 4], A2 [4 × 6], A3 [6 × 2], and A4 [2 × 7]. Also give the optimal
    solution.
    OR
    Q.3 (a) Differentiate greedy programming approach with dynamic programming 03
    approach.
    (b) Solve the following recurrence using Master Theorem. 04
    T(n) = T(2n/3) + 1.
    (c) Using greedy algorithm find an optimal schedule for following jobs with n=6. 07
    Profits: (P1, P2, P3, P4, P5, P6) = (20, 15, 10, 7, 5, 3)
    Deadline: (d1, d2, d3, d4, d5, d6) =(3, 1, 1, 3, 1, 3).
    Q.4 (a) Define and explain P and NP problems with suitable example. 03
    (b) Solve the following Knapsack Problem using greedy method. Number of 04
    items = 7, knapsack capacity W = 15, weight vector = {2, 3, 5, 7, 1, 4, 1}
    and profit vector = {10, 5, 15, 7, 6, 18, 3}.
    (c) Find minimum spanning tree using Krushkal’s algorithm of the following 07
    graph.

    1
    OR
    Q.4 (a) Define and explain NP-complete and NP-hard problems with suitable example. 03
    (b) Explain Dijkstra’s algorithm to find the shortest path. 04
    (c) Find minimum spanning tree using Prim’s algorithm of the following graph. 07

    Q.5 (a) Explain the naive string matching algorithm 03


    (b) Differentiate between depth first search and breadth first search. 04
    (c) Working modulo q = 11. How many spurious hits does the Rabin-Karp matcher 07
    encounter in the text T = 3141592653589793 when looking for the pattern P
    =26?
    OR
    Q.5 (a) Explain polynomial-time reduction algorithm. 03
    (b) Prove that if G is an undirected bipartite graph with an odd number of vertices, 04
    then G is non-Hamiltonian.
    (c) Explain Backtracking Method. What is N-Queens Problem? Give solution of 4 07
    Queens Problem using Backtracking Method.

    *************

    You might also like