Scribd Logo
Upload

Welcome to Scribd!

  • 4 views

    DAA - Average Learner Assignment-2

    Uploaded by

    Lalit Singhal

    Copyright:

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

    DAA - Average Learner Assignment-2

    Uploaded by

    Lalit Singhal
    4 views2 pages

    Original Title

    DAA_Average Learner Assignment-2 (1)

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

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

    DAA - Average Learner Assignment-2

    Uploaded by

    Lalit Singhal

    Copyright:

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

    DEPARTMENT OF

    COMPUTER SCIENCE & ENGINEERING

    Subject: Design and Analysis of Algorithms with Lab


    Subject Code: 21ITH-311/21CSH-311 Semester: 5th

    Assignment- 2

    Last date of Submission: Total Marks: 10 (2 Questions of 3


    marks , 1 Question of 4 marks)

    *Note: Every student needs to submit assignment as per the allotted


    set by respective faculty.

    Set – 1

    S Question Marks CO’s


    No.
    1. Write an algorithm of merge sort and also explain 2-way Merge Sort 3 marks CO2
    with suitable example.

    2. Solve using fractional knapsack: 3 marks CO3


    M=20, n=4
    P= (3, 10, 15, 5)
    W= (5, 13, 12, 8).

    3. A networking company uses a compression technique to encode the 4 marks CO3


    message before transmitting over the network. Suppose the message
    contains the following characters with their frequency:

    If the compression technique used is Huffman Coding, how many bits


    will be saved in the message?
    DEPARTMENT OF
    COMPUTER SCIENCE & ENGINEERING

    Set – 2

    S Question Marks CO’s


    No.
    1. Find longest common subsequence for: 3 marks CO3
    A= BACDB B= BDCB
    2. Find minimum spanning tree using prim and kruskal’s algorithm: 3 marks CO3

    3. Solve the given sequence matrices using matrix chain multiplication: 4 marks CO2
    P=<5, 10, 15, 20 , 25>

    Set – 3

    S Question Marks CO’s


    No.
    1. For each of following Divide and Conquer algorithms, state the 3 marks CO2
    corresponding recurrence relation, and state a runtime bound (using O)
    (you do not need to show work for solving the runtime recurrence).
    a.) If you solve 7 sub-problems of size n/7 , then the cost of
    combining the solutions of the sub-problems to obtain a solution
    for the original problem is 3n + 20
    b.) If you solve 16 sub-problems of size n/4 , then the cost for
    combining the solutions is 100
    2. Out of Quick Sort and Merge Sort, which algorithm is preferred 3 marks CO2
    to sort an array and a Linked List andwhy?

    3. Solve the activity selection problem by sorting the activities according 4 marks CO3
    to increasing finish times:

    You might also like