Scribd Logo
Upload

Welcome to Scribd!

  • 22 views

    Gujarat Technological University

    Uploaded by

    Shiv Patel
    This document is an exam for the subject Analysis & Design of Algorithms. It contains 5 questions testing students' knowledge of various algorithm analysis topics. Question 1 covers asymptotic notation, dynamic programming, and complexity analysis. Question 2 covers recurrence relations, sorting algorithms like counting sort and quicksort. Question 3 covers greedy algorithms, minimum spanning trees, and fractional knapsack. Question 4 covers optimal subproblems, all pairs shortest path, and longest common subsequence. Question 5 covers NP-complete problems, backtracking, and string matching algorithms. Students are instructed to attempt all questions which involve explaining concepts, writing pseudocode, and solving algorithm problems.

    Copyright:

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

    Gujarat Technological University

    Uploaded by

    Shiv Patel
    22 views2 pages
    This document is an exam for the subject Analysis & Design of Algorithms. It contains 5 questions testing students' knowledge of various algorithm analysis topics. Question 1 covers asymptotic notation, dynamic programming, and complexity analysis. Question 2 covers recurrence relations, sorting algorithms like counting sort and quicksort. Question 3 covers greedy algorithms, minimum spanning trees, and fractional knapsack. Question 4 covers optimal subproblems, all pairs shortest path, and longest common subsequence. Question 5 covers NP-complete problems, backtracking, and string matching algorithms. Students are instructed to attempt all questions which involve explaining concepts, writing pseudocode, and solving algorithm problems.

    Original Title

    s21

    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 is an exam for the subject Analysis & Design of Algorithms. It contains 5 questions testing students' knowledge of various algorithm analysis topics. Question 1 covers asymptotic notation, dynamic programming, and complexity analysis. Question 2 covers recurrence relations, sorting algorithms like counting sort and quicksort. Question 3 covers greedy algorithms, minimum spanning trees, and fractional knapsack. Question 4 covers optimal subproblems, all pairs shortest path, and longest common subsequence. Question 5 covers NP-complete problems, backtracking, and string matching algorithms. Students are instructed to attempt all questions which involve explaining concepts, writing pseudocode, and solving algorithm problems.

    Copyright:

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

    Gujarat Technological University

    Uploaded by

    Shiv Patel
    This document is an exam for the subject Analysis & Design of Algorithms. It contains 5 questions testing students' knowledge of various algorithm analysis topics. Question 1 covers asymptotic notation, dynamic programming, and complexity analysis. Question 2 covers recurrence relations, sorting algorithms like counting sort and quicksort. Question 3 covers greedy algorithms, minimum spanning trees, and fractional knapsack. Question 4 covers optimal subproblems, all pairs shortest path, and longest common subsequence. Question 5 covers NP-complete problems, backtracking, and string matching algorithms. Students are instructed to attempt all questions which involve explaining concepts, writing pseudocode, and solving algorithm problems.

    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 (NEW) EXAMINATION – SUMMER 2021
    Subject Code:3150703 Date:05/10/2021
    Subject Name:Analysis & Design of Algorithms
    Time:10:30 AM TO 01:00 PM Total Marks: 70
    Instructions:
    1. Attempt all questions.
    2. Make suitable assumptions wherever necessary.
    3. Figures to the right indicate full marks.
    4. Simple and non-programmable scientific calculators are allowed.

    MARKS
    Q.1 (a) Explain Asymptotic notations. 03
    (b) What is Principle of Optimality? Explain its use in Dynamic 04
    Programming Method.
    (c) Explain why algorithm analysis is important. Also explain Worst Case, 07
    Best Case & Average Case Complexity of algorithm.

    Q.2 (a) Explain Master method for solving Recurrence. 03


    (b) Explain Counting Sort algorithm with example. 04
    (c) Explain Quick Sort algorithm with suitable example. Also give its 07
    complexity analysis.
    OR
    (c) Explain Binary search algorithm with divide and conquer strategy and 07
    show that the solution to the binary search recurrence T(n)= T(n/2) +
    Ѳ (1) is T(n) = Ѳ(lgn).

    Q.3 (a) Explain general characteristics of Greedy algorithm. 03


    (b) Write Kruskal’s algorithm to find Minimum Spanning Tree. 04
    (c) Write Huffman code algorithm and Generate Huffman code for 07
    following:
    Symbol a b c d e
    Frequency 35 25 20 12 8
    OR
    Q.3 (a) Define amortized analysis. Briefly explain any two techniques. 03
    (b) Write algorithm to find Minimum Spanning Tree (MST) using Prim’s 04
    method.
    (c) Using Greedy method find an optimal solution for fractional knapsack 07
    problem given below:
    n=7, W=15.
    Weight (w) 2 3 5 7 1 4 1
    Profit (p) 10 5 15 7 6 18 3

    Q.4 (a) Explain Optimal Substructure and Overlapping sub problems with 03
    suitable example.
    (b) Explain All Pair Shortest Path Algorithm. 04
    (c) Given two sequences of characters, M=<A,B,C,D,B,A,C,D,F>, 07
    N=<C,B,A,F> Obtain the Longest Common Subsequence. Write
    equations and necessary steps.

    1
    OR
    Q.4 (a) Explain: Articulation Point, Graph, Minimum Spanning Tree. 03
    (b) Explain Depth First Search algorithm. 04
    (c) Solve the following Knapsack Problem using Dynamic Method. Write 07
    the equation and steps for solving above problem. n = 5, W = 100
    Object 1 2 3 4 5
    Weight (w) 10 20 30 40 50
    Value (v) 20 30 66 40 60

    Q.5 (a) Explain Hamiltonian problem. 03


    (b) Explain Knuth-Morris-Pratt string matching algorithm with example. 04
    (c) Give state space tree after application of backtracking for Knapsack 07
    problem given below and explain it briefly.
    Number of objects=4, Capacity of knapsack= W= 8 units. Objects
    weight are (2, 3, 4, 5) and values are (3, 5, 6, 10) respectively
    OR
    Q.5 (a) Explain Branch and Bound technique briefly. 03
    (b) Define P, NP, NP-Hard and NP-Complete Problem 04
    (c) Explain Rabin-Karp Algorithm for string matching with example and 07
    show all necessary steps.

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

    You might also like