FirstRanker Logo

FirstRanker.com - FirstRanker's Choice is a hub of Question Papers & Study Materials for B-Tech, B.E, M-Tech, MCA, M.Sc, MBBS, BDS, MBA, B.Sc, Degree, B.Sc Nursing, B-Pharmacy, D-Pharmacy, MD, Medical, Dental, Engineering students. All services of FirstRanker.com are FREE

📱

Get the MBBS Question Bank Android App

Access previous years' papers, solved question papers, notes, and more on the go!

Install From Play Store

Download GTU B.Tech 2020 Summer 5th Sem 2150703 Analysis And Design Of Algorithms Question Paper

Download GTU (Gujarat Technological University Ahmedabad) B.Tech/BE (Bachelor of Technology/ Bachelor of Engineering) 2020 Summer 5th Sem 2150703 Analysis And Design Of Algorithms Previous Question Paper

This post was last modified on 04 March 2021

This download link is referred from the post: GTU BE 2020 Summer Question Papers || Gujarat Technological University


FirstRanker.com

A Firstranker's choice

GUJARAT TECHNOLOGICAL UNIVERSITY

--- Content provided by FirstRanker.com ---

BE - SEMESTER- V EXAMINATION - SUMMER 2020

Date: 26/10/2020

Subject Code: 2150703

Subject Name: ANALYSIS AND DESIGN OF ALGORITHMS

Total Marks: 70

--- Content provided by FirstRanker.com ---

Time: 02:30 PM TO 05:00 PM

Instructions:

  1. Attempt all questions.
  2. Make suitable assumptions wherever necessary.
  3. Figures to the right indicate full marks.
  4. --- Content provided by FirstRanker.com ---

Q.1

  1. (a) Define the terms:
    1. Principal of Optimality
    2. Feasible solution
    3. Quantifier

    MARKS 03

    --- Content provided by FirstRanker.com ---

  2. (b) Analyze Binary search algorithm in best and worst case.

    04

  3. (c) Define Asymptotic notation. Arrange the following functions in increasing order of growth: 2n, n2, 1, log n, n log n, 3n and n.

    07

  4. --- Content provided by FirstRanker.com ---

Q.2

  1. (a) Define the function types:
    1. One-to-One
    2. Into (Injective)
    3. Onto (Surjective)

    03

    --- Content provided by FirstRanker.com ---

  2. (b) What is the smallest value of n such that an algorithm whose running time is 100n2 runs faster than an algorithm whose running time is 2n on the same machine?

    07

  3. (c) Analyze Quick sort algorithm in best and worst case.

    07

  4. --- Content provided by FirstRanker.com ---

Q.3

  1. (a) Analyze insertion sort algorithm in best and worst case.

    03

  2. (b) Differentiate divide and conquer approach with dynamic programming approach.

    04

  3. --- Content provided by FirstRanker.com ---

  4. (c) Solve the following recurrence using Master Theorem: T(n) = 9T(n/3) + n.

    04

OR

  1. (a) Write equation for Matrix Chain Multiplication using Dynamic programming.

    07

  2. --- Content provided by FirstRanker.com ---

  3. (b) Find out optimal sequence for multiplication: A1 [5 x 4], A2 [4 x 6], A3 [6 x 2], and A4 [2 x 7]. Also give the optimal solution.

    03

  4. (c) Differentiate greedy programming approach with dynamic programming approach.

    04

Q.4

--- Content provided by FirstRanker.com ---

  1. (a) Solve the following recurrence using Master Theorem: T(n) = T(n/3) + 1.

    03

  2. (b) Using greedy algorithm find an optimal schedule for following jobs with n=6. 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).

    04

  3. (c) Define and explain P and NP problems with suitable example. Solve the following Knapsack Problem using greedy method. Number of 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}.

    07

    --- Content provided by FirstRanker.com ---

OR

  1. (a) Define and explain NP-complete and NP-hard problems with suitable example.

    03

  2. (b) Explain Dijkstra’s algorithm to find the shortest path.

    04

    --- Content provided by FirstRanker.com ---

  3. (c) Find minimum spanning tree using Prim’s algorithm of the following graph.

    07

Q.5

  1. (a) Explain the naive string matching algorithm.

    03

    --- Content provided by FirstRanker.com ---

  2. (b) Differentiate between depth first search and breadth first search.

    04

  3. (c) Working modulo q=11. How many spurious hits does the Rabin-Karp matcher encounter in the text T = 3141592653589793 when looking for the pattern P = 26?

    07

  4. --- Content provided by FirstRanker.com ---

OR

  1. (a) Explain polynomial-time reduction algorithm.

    03

  2. (b) Prove that if G is an undirected bipartite graph with an odd number of vertices, then G is non-Hamiltonian.

    04

  3. --- Content provided by FirstRanker.com ---

  4. (c) Explain Backtracking Method. What is N-Queens Problem? Give solution of 4 Queens Problem using Backtracking Method.

    07

FirstRanker.com


--- Content provided by FirstRanker.com ---


This download link is referred from the post: GTU BE 2020 Summer Question Papers || Gujarat Technological University