Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 11 views

    June - 2023 MCS-211

    Uploaded by

    shilpishrivastava105

    Copyright:

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

    June - 2023 MCS-211

    Uploaded by

    shilpishrivastava105
    11 views4 pages

    Original Title

    June_2023 MCS-211

    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
    11 views4 pages

    June - 2023 MCS-211

    Uploaded by

    shilpishrivastava105

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 4

    No.

    of Printed Pages : 4 MCS-211

    om
    MASTER OF COMPUTER

    u.c
    APPLICATIONS
    (MCA-NEW)

    ur
    Term-End Examination
    June, 2023

    tG
    MCS-211 : DESIGN AND ANALYSIS OF
    ALGORITHMS
    en
    Time : 3 Hours Maximum Marks : 100
    (Weightage : 70%)
    m

    Note : Question No. 1 is compulsory and carries


    40 marks. Attempt any three questions from
    ign

    the rest.

    1. (a) What is an algorithm ? What are its


    ss

    desirable characteristics ? 5
    UA

    (b) What are asymptotic notations ? Explain


    any two asymptotic notations with suitable
    example for each. 5
    NO

    (c) Solve the following recurrence relation


    using substitution method : 5
    n
    T  n   2T    n
    IG

    2

    P. T. O.
    [2] MCS-211

    (d) Write and explain binary search algorithm


    with an suitable example. 5

    om
    (e) Explain Depth First Search (DFS)
    algorithm with an suitable example. 5

    u.c
    (f) What is Dynamic Programming approach
    of problem solving ? Write the steps
    involved in dynamic programming. 6

    ur
    (g) What are Optimization and Decision
    problems ? Give an example of each. 5

    tG
    (h) Design a state space tree for the given
    subset sum problem. S = {4, 6, 7, 8}, W = 8.
    en
    4
    2. (a) Explain all the three cases of Master’s
    m

    Theorem. Apply Master’s theorem to solve


    the given recurrence relation : 8
    ign

    n
    T  n   9T  
    3
    ss

    (b) Evaluate :
    p  x   3x 4  2x 3  5x  7 at x  2
    UA

    using Horner’s rule. Show stepwise


    iterations. 6
    NO

    (c) Prove that for all non-negative integers


    ‘n’ : 6
    20  21  22  .......2n  2n 1  1.
    IG
    [3] MCS-211

    3. (a) What is Huffman coding ? Write the steps


    for building the Huffman tree with an

    om
    example. 6
    (b) Explain Quick sort algorithm using divide
    and conquer approach. 6

    u.c
    (c) What are strongly connected components ?
    Explain how adjacency matrix and

    ur
    adjacency list are created for a connected
    graph with the help of a suitable diagram.

    tG
    2+3+3
    4. (a) Show the step by step execution of
    en
    Kruskal’s algorithm for the following
    graph : 6
    m
    ign
    ss

    (b) What is Matrix chain multiplication


    problem ? Find an optimal parenthesiza-
    UA

    tion of a martix-chain product whose


    sequence of dimensions are as follows : 2+6
    Matrix Dimension
    NO

    A1 30 × 35
    A2 35 × 15
    IG

    A3 15 × 5

    P. T. O.
    [4] MCS-211

    (c) Explain Rabin Karp Algorithm for string


    matching with suitable example. 6

    om
    5. Write short notes on any four of the following :
    4×5=20

    u.c
    (i) Deterministic vs. Non-deterministic
    algorithms
    (ii) CLIQUE and vertex cover problem

    ur
    (iii) Backtracking problem with example

    tG
    (iv) Bellman-Ford algorithm
    (v) Fractional Knapsack problem
    en
    m
    ign
    ss
    UA
    NO
    IG

    MCS–211

    You might also like