Scribd Logo
Upload

Welcome to Scribd!

  • 4 views

    DAA 2012 (SXS7AKCJ) - Unlocked

    Uploaded by

    yash patil
    The document is an exam paper for the subject "Design & Analysis of Algorithms" containing 6 questions. It provides instructions to candidates regarding answering questions and includes information like total marks, time duration etc. The questions cover topics like quicksort algorithm and its complexity, asymptotic notations, recursive binary search, dynamic programming approaches like chain matrix multiplication and binomial coefficients, backtracking for graph coloring, branch and bound method and its characteristics, algorithms for N-Queens problem and knapsack problem.

    Copyright:

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

    DAA 2012 (SXS7AKCJ) - Unlocked

    Uploaded by

    yash patil
    4 views2 pages
    The document is an exam paper for the subject "Design & Analysis of Algorithms" containing 6 questions. It provides instructions to candidates regarding answering questions and includes information like total marks, time duration etc. The questions cover topics like quicksort algorithm and its complexity, asymptotic notations, recursive binary search, dynamic programming approaches like chain matrix multiplication and binomial coefficients, backtracking for graph coloring, branch and bound method and its characteristics, algorithms for N-Queens problem and knapsack problem.

    Original Title

    DAA 2012 (SXS7AKCJ)_unlocked

    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 an exam paper for the subject "Design & Analysis of Algorithms" containing 6 questions. It provides instructions to candidates regarding answering questions and includes information like total marks, time duration etc. The questions cover topics like quicksort algorithm and its complexity, asymptotic notations, recursive binary search, dynamic programming approaches like chain matrix multiplication and binomial coefficients, backtracking for graph coloring, branch and bound method and its characteristics, algorithms for N-Queens problem and knapsack problem.

    Copyright:

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

    DAA 2012 (SXS7AKCJ) - Unlocked

    Uploaded by

    yash patil
    The document is an exam paper for the subject "Design & Analysis of Algorithms" containing 6 questions. It provides instructions to candidates regarding answering questions and includes information like total marks, time duration etc. The questions cover topics like quicksort algorithm and its complexity, asymptotic notations, recursive binary search, dynamic programming approaches like chain matrix multiplication and binomial coefficients, backtracking for graph coloring, branch and bound method and its characteristics, algorithms for N-Queens problem and knapsack problem.

    Copyright:

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

    Total No. of Questions : 6] SEAT No.

    P162 [Total No. of Pages : 2


    OCT/BE/Insem.-91

    0
    8:0
    B.E. (Computer Engineering)

    3:5
    DESIGN & ANALYSIS OF ALGORITHMS

    1
    91
    4/0 87
    (2012 Pattern)

    01
    3
    8/2
    7.1 P01
    Time : 1 Hour] [Max. Marks : 30
    02

    Instructions to the candidates :


    .11 EG

    1) Answer Q1 or Q2, Q3 or Q4 and Q5 or Q6.


    C
    9.5

    2) Draw neat diagram whenever necessary.


    3) Figures to the right indicate full marks.

    0
    8:0
    45

    4) Assume suitable data, if necessary.

    3:5
    71
    91
    Q1) a) Write quick sort algorithm using divide and conquer strategy and
    38
    01

    compute its complexity. [6]


    8/2
    01

    b) Define asymptotic notations. Explain their significance in analyzing


    4/0
    GP

    algorithms. [4]
    02

    OR
    CE
    7.1
    9.5

    Q2) a) Write an algorithm for Recursive Binary Search. What is the time
    complexity for Successful Search and Unsuccessful Search? [6]
    .11

    0
    8:0
    45

    b) Explain amortized analysis. [4]


    3:5
    71
    91

    Q3) a) Explain Chain Matrix multiplication using dynamic programming.[6]


    38
    01
    8/2

    b) State the difference between greedy approach and dynamic


    01

    programming approach. [4]


    4/0
    GP
    02

    OR
    CE
    7.1

    Q4) a) Explain use of dynamic programming to compute a binomial


    9.5

    coefficient. State its time complexity. [6]


    .11

    b) Explain job scheduling algorithm using greedy approach. [4]


    45

    P.T.O.
    Q5) a) Explain graph coloring problem using backtracking approach. [6]
    b) What are the general characteristics of branch and bound approach?
    [4]

    0
    8:0
    OR

    3:5
    Q6) a) Write an algorithm to solve N-Queens problem. [6]

    1
    91
    4/0 87
    b) Explain knapsack problem using branch and bound method. [4]

    01
    3
    8/2
    7.1 P01

    
    02
    .11 EG
    C
    9.5

    0
    8:0
    45

    3:5
    71
    91
    38
    01
    8/2
    01
    4/0
    GP
    02
    CE
    7.1
    9.5
    .11

    0
    8:0
    45

    3:5
    71
    91
    38
    01
    8/2
    01
    4/0
    GP
    02
    CE
    7.1
    9.5
    .11
    45

    BE/Insem.-91 2

    You might also like