Scribd Logo
Upload

Welcome to Scribd!

  • 3 views

    MCS-211

    Uploaded by

    s553b
    snm

    Copyright:

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

    MCS-211

    Uploaded by

    s553b
    3 views4 pages
    snm

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    snm

    Copyright:

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

    MCS-211

    Uploaded by

    s553b
    snm

    Copyright:

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

    No.

    of Printed Pages : 4 MCS–211

    MASTER OF COMPUTER
    APPLICATIONS
    (MCA-NEW)
    Term-End Examination
    December, 2023
    MCS-211 : DESIGN AND ANALYSIS OF
    ALGORITHMS
    Time : 3 Hours Maximum Marks : 100
    (Weightage : 70%)

    Note : Question No. 1 is compulsory and carries


    40 marks. Attempt any three questions from
    the rest.

    1. (a) What is Euclid’s algorithm to find GCD of


    two given integers ? Write the steps
    involved in finding GCD of (a, b) using
    Euclid’s algorithm. 5

    (b) What are Big ‘O’ and Big ‘’ notations ?


    Explain with the help of representative
    diagram. 5

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

    (c) Write and explain linear search


    algorithm. Mention best case, worst case
    and average case scenarios of linear
    search. 5
    (d) Explain Breadth First Search (BFS)
    algorithm with a suitable example. 5
    (e) What is Task Scheduling algorithm ? Write
    pseudo code for task scheduling algorithm.
    5
    (f) Solve the given recurrence relation using
    recursion tree method : 5
    n
     n   2T  n
    2
    (g) What are P, NP and NP-complete
    problems ? Give example of each. 5
    (h) What is a Minimum Cost Spanning Tree
    (MCST) ? Write Generic MCST algorithm.
    5
    2. (a) What are the building blocks of an
    algorithm ? Explain how to judge an
    algorithm, whether it is efficient or not ? 6
    (b) Using mathematical induction, prove that
    the sum of first ‘n’ positive integers is
     n  n  1 
      i.e. 1 + 2 + 3 ............ + n
     2 
    n  n  1
    = . 6
    2
    [3] MCS–211

    (c) What is polynomial evaluation ? What are


    its methods of evaluation ? Evaluate

    P  x   3x 2  5x  6 using Horner’s rule at

    x = 3. 2+2+4

    3. (a) What is Greedy approach for problem


    solving ? How does a Greedy algorithm
    work ? Write the activities performed in
    Greedy method. 6

    (b) Explain merge sort algorithm using divide


    and conquer approach. Also mention its
    best case and worst case time complexities.

    6+2

    (c) Explain any three of the following terms


    with the help of a suitable diagram : 3×2=6

    (i) Subgraph

    (ii) Connected graph

    (iii) Adjacency matrix

    (iv) Directed acyclic graph

    4. (a) Show the step by step execution of


    Dijkstra’s single source shortest path

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

    algorithm on the given directed graph from


    source vertex ‘a’ : 6

    (b) What is string matching problem ? Explain


    Knuth Morris Pratt algorithm of string
    matching with a suitable example. Explain
    the process of building LPS array for a
    pattern ‘P’. 2+4+2
    (c) What is all pair shortest path problem ?
    Write and explain Floyd Warshall
    algorithm for shortest paths with the help
    of a diagram. 6
    5. Write short notes on any four of the following :
    4×5=20
    (i) Tractable vs. Intractable problems
    (ii) CNF Satisfiability problem
    (iii) Optimization and decision problems
    (iv) Prim’s algorithm
    (v) Approximation algorithms
    (vi) Master’s theorem

    MCS–211

    You might also like