Scribd Logo
Upload

Welcome to Scribd!

  • 42 views

    Daa Model

    Uploaded by

    karthick Vijayan
    This document contains a model exam for the subject "Design Analysis and Algorithm" with 3 parts: Part A contains 10 short answer questions worth 2 marks each about algorithms, data structures, and computational complexity. Part B contains 5 algorithm design and analysis problems worth 13 marks each, including problems on string matching, matrix multiplication, dynamic programming, and graph algorithms. Part C contains 1 short question worth 15 marks on constructing an optimal binary search tree given node names and probabilities.

    Copyright:

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

    Daa Model

    Uploaded by

    karthick Vijayan
    42 views2 pages
    This document contains a model exam for the subject "Design Analysis and Algorithm" with 3 parts: Part A contains 10 short answer questions worth 2 marks each about algorithms, data structures, and computational complexity. Part B contains 5 algorithm design and analysis problems worth 13 marks each, including problems on string matching, matrix multiplication, dynamic programming, and graph algorithms. Part C contains 1 short question worth 15 marks on constructing an optimal binary search tree given node names and probabilities.

    Original Description:

    hi

    Original Title

    DAA MODEL

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains a model exam for the subject "Design Analysis and Algorithm" with 3 parts: Part A contains 10 short answer questions worth 2 marks each about algorithms, data structures, and computational complexity. Part B contains 5 algorithm design and analysis problems worth 13 marks each, including problems on string matching, matrix multiplication, dynamic programming, and graph algorithms. Part C contains 1 short question worth 15 marks on constructing an optimal binary search tree given node names and probabilities.

    Copyright:

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

    Daa Model

    Uploaded by

    karthick Vijayan
    This document contains a model exam for the subject "Design Analysis and Algorithm" with 3 parts: Part A contains 10 short answer questions worth 2 marks each about algorithms, data structures, and computational complexity. Part B contains 5 algorithm design and analysis problems worth 13 marks each, including problems on string matching, matrix multiplication, dynamic programming, and graph algorithms. Part C contains 1 short question worth 15 marks on constructing an optimal binary search tree given node names and probabilities.

    Copyright:

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

    RRASE COLLEGE OF ENGINNERING

    MODEL EXAM
    DEPARTMENT OF INFORMATION TECHNOLOGY
    COMMON TO CSE & IT
    SUBJECTCODE/TITLE: CS8451/DESIGN ANALYSIS AND ALGORITHM YEAR/SEM: II/IV
    MAX. MARKS: 100 DURATION: 3 HRS
    PART-A[10*2=20]
    1. What do you mean by algorithm?
    2. Define big oh notation.
    3. What do you mean by Divide and Conquer strategy?
    4. Derive the complexity of Binary Search algorithm.
    5. Write down the optimization technique used for Floyds’s algorithm. State the rules and assumptions which are implied behind
    that.
    6. Differentiate variable length encoding and fixed length encoding
    7. What do you mean by ‘perfect matching ‘in bipartite graphs?
    8. What is maximum cardinality matching?
    9. What is Hamiltonian cycle?
    10. An NP-hard problem can be solved in deterministic polynomial time, how?

    PART-B –(13*5=65)
    11. A) i) Briefly explain the time complexity, space complexity estimation. (4)
    ii) Write the linear search algorithm and analyze its time complexity. (9)
    [or]
    B) Write the asymptotic notations used for best case ,average case and worst case analysis of algorithms and Write an algorithm
    for finding maximum element of an array perform best , worst and average case complexity with appropriate order notations.(13)

    12. A) i) Solve the following using Brute-Force algorithm. (8)


    Find whether the given string follows the specified pattern and return 0 or 1 accordingly.
    Examples:
    1) Pattern: “abba” input: “redblueredblue” should return 1
    2) Pattern: “aaaa” input: “asdasdasdasd” should return 1
    3) Pattern: “aabb” input: “xyzabcxzyabc” should return 0
    ii) Explain the convex hull problem and the solution involved behind it. (5)
    [or]
    B) Apply Stassen’s algorithm to compute (13)

    1 2 1 1 2 1 0 2
    0 3 2 4 * 1 2 1 1
    0 1 1 1 0 3 2 1
    5 0 1 0 4 0 0 4

    13 A) i) How do you construct a minimum spanning tree using Kruskal’s Algorithm? Explain. (5)
    ii) Let A={l/119, m/96,c/247, g/283, h/72, f/77, k/92, j/19} be the letters and its frequency of distribution in a text file.
    Compute a suitable Huffman coding to compress the data effectively. (8)
    [or]
    B) Apply the bottom up dynamic programming algorithm to the following instance of Knapsack Problem. Capacity W=10.(13)

    Item Weight Value


    1 7 $42
    2 3 $12
    3 4 $40
    4 5 $25

    14. A) i) Maximize p=2x+3y+z (10)


    Subject to x+y+z<=40
    2x+y-z>=10
    -y+z>=10
    x>=0, y>=0, z>=0
    ii) Write down the optimality condition and algorithmic implementation for finding M-augumenting paths in bipartite graphs.(3)
    [or]
    B) i)Briefly describe on the Stable marriage problem. (3)
    ii) How do you compute maximum flow for the following graph using Ford-Fulkerson method? (10)
    15 A) Explain how job assignment problem could be solved, given n tasks and n agents where each agent has to complete each
    task, using Branch and Bound technique. (13)
    [Or]
    B) i) The knight is placed on the first block of an empty board and moving according to the rules of chess, must visit each square
    exactly once. Solve the problem using backtracking procedure. (8)
    ii) Write a note on NP complete Problems. (5)

    PART-C [15*1=15]
    16. Obtain a Optimal Binary Search Tree for following nodes(do,if,int,while) with following probabilities(0.1,0.2,0.4,0.3)

    You might also like