Scribd Logo
Upload

Welcome to Scribd!

  • 53 views

    Winter 20

    Uploaded by

    HS Harshil Parmar
    This document contains 8 questions related to the analysis and design of algorithms. The questions cover topics like asymptotic notation, analysis of sorting algorithms like insertion sort, divide and conquer algorithms like quicksort, greedy algorithms, dynamic programming, string matching, finite automata, knapsack problem, backtracking, and complexity classes. Students need to attempt any 4 questions out of the 8 questions given in the paper. Each question consists of 3 sub-questions carrying different marks.

    Copyright:

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

    Winter 20

    Uploaded by

    HS Harshil Parmar
    53 views2 pages
    This document contains 8 questions related to the analysis and design of algorithms. The questions cover topics like asymptotic notation, analysis of sorting algorithms like insertion sort, divide and conquer algorithms like quicksort, greedy algorithms, dynamic programming, string matching, finite automata, knapsack problem, backtracking, and complexity classes. Students need to attempt any 4 questions out of the 8 questions given in the paper. Each question consists of 3 sub-questions carrying different marks.

    Original Title

    WINTER 20

    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 8 questions related to the analysis and design of algorithms. The questions cover topics like asymptotic notation, analysis of sorting algorithms like insertion sort, divide and conquer algorithms like quicksort, greedy algorithms, dynamic programming, string matching, finite automata, knapsack problem, backtracking, and complexity classes. Students need to attempt any 4 questions out of the 8 questions given in the paper. Each question consists of 3 sub-questions carrying different marks.

    Copyright:

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

    Winter 20

    Uploaded by

    HS Harshil Parmar
    This document contains 8 questions related to the analysis and design of algorithms. The questions cover topics like asymptotic notation, analysis of sorting algorithms like insertion sort, divide and conquer algorithms like quicksort, greedy algorithms, dynamic programming, string matching, finite automata, knapsack problem, backtracking, and complexity classes. Students need to attempt any 4 questions out of the 8 questions given in the paper. Each question consists of 3 sub-questions carrying different marks.

    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 – WINTER 2020
    Subject Code:3150703 Date:29/01/2021
    Subject Name:Analysis & Design of Algorithms
    Time:10:30 AM TO 12:30 PM Total Marks: 56
    Instructions:
    1. Attempt any FOUR questions out of EIGHT questions.
    2. Make suitable assumptions wherever necessary.
    3. Figures to the right indicate full marks.

    MARKS
    Q.1 (a) What is an algorithm? Why analysis of algorithm is required? 03
    (b) What is asymptotic notation? Find out big-oh notation of the f(n)= 04
    3n2+5n+10

    (c) Write an algorithm for insertion sort. Analyze insertion sort algorithm 07
    for best case and worst case.

    Q.2 (a) What is the difference between selection sort and bubble sort? 03
    (b) Write iterative and recursive algorithm for finding the factorial of N. 04
    Derive the time complexity of both algorithms.
    (c) Solve following recurrence relation using iterative method 07
    T(n)=2T(n / 2) + n
    Q.3 (a) How divide and conquer approach work? 03
    (b) Trace the quick sort for data A = {6,5,3,11,10,4,7,9} 04
    (c) Explain master theorem and solve the recurrence T(n)=9T(n/3)+n with 07
    master method

    Q.4 (a) Write the characteristics of greedy algorithm. 03


    (b) Trace the merge sort for data A = {6,5,3,11,10,4,7,9} 04
    (c) Find minimum spanning tree for the given graph in fig-1 using prim’s 07
    algorithm

    Fig-1
    Q.5 (a) How huffman code is memory efficient compare to fixed length code? 03
    (b) Give difference between greedy approach and dynamic programming. 04
    (c) Find the Huffman code for each symbol in following text 07
    ABCCDEBABFFBACBEBDFAAAABCDEEDCCBFEBFCAE

    Q.6 (a) What is principal of optimality? Explain its use in Dynamic 03


    Programming Method.
    (b) Find out minimum number of multiplications required for multiplying: 04
    A[1 × 5], B[5 × 4], C[4 × 3], D[3 × 2], and E[2 × 1].
    (c) Solve following knapsack problem using dynamic programming 07
    algorithm with given capacity W=5, Weight and Value are as follows :
    1
    (2,12),(1,10),(3,20),(2,15)

    Q.7 (a) What is finite automata? How it can be used in string matching? 03
    (b) Differentiate BFS and DFS 04
    (c) Explain Backtracking Method. What is N-Queens Problem? Give 07
    solution of 4-Queens Problem using Backtracking Method.

    Q.8 (a) Explain Minimax principal. 03


    (b) Define P, NP, NP-complete, NP-Hard problems. 04
    (c) Explain rabin-karp string matching algorithm. 07

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

    You might also like