Scribd Logo
Upload

Welcome to Scribd!

  • 33 views

    MCS-031 J16 Compressed

    Uploaded by

    chandrashekhar adarsh
    This document is an exam for the course MCS-031: Design and Analysis of Algorithms. It contains 6 questions, with question 1 being compulsory and students to attempt any 3 of the remaining questions. Question 1 covers characteristics of algorithms, writing a recursive factorial algorithm, importance of asymptotic analysis, and Chomsky grammar classification. It also asks to use Dijkstra's algorithm on a graph and justify whether worst-case analysis is more important than best-case analysis. The other questions cover topics like greedy algorithms, solving recurrences, Turing machines, minimum spanning trees, sorting algorithms, graph traversals, asymptotic notation, dynamic programming, and NP-complete problems.

    Copyright:

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

    MCS-031 J16 Compressed

    Uploaded by

    chandrashekhar adarsh
    33 views4 pages
    This document is an exam for the course MCS-031: Design and Analysis of Algorithms. It contains 6 questions, with question 1 being compulsory and students to attempt any 3 of the remaining questions. Question 1 covers characteristics of algorithms, writing a recursive factorial algorithm, importance of asymptotic analysis, and Chomsky grammar classification. It also asks to use Dijkstra's algorithm on a graph and justify whether worst-case analysis is more important than best-case analysis. The other questions cover topics like greedy algorithms, solving recurrences, Turing machines, minimum spanning trees, sorting algorithms, graph traversals, asymptotic notation, dynamic programming, and NP-complete problems.

    Original Description:

    this is a question paper

    Original Title

    - MCS-031 J16 Compressed

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document is an exam for the course MCS-031: Design and Analysis of Algorithms. It contains 6 questions, with question 1 being compulsory and students to attempt any 3 of the remaining questions. Question 1 covers characteristics of algorithms, writing a recursive factorial algorithm, importance of asymptotic analysis, and Chomsky grammar classification. It also asks to use Dijkstra's algorithm on a graph and justify whether worst-case analysis is more important than best-case analysis. The other questions cover topics like greedy algorithms, solving recurrences, Turing machines, minimum spanning trees, sorting algorithms, graph traversals, asymptotic notation, dynamic programming, and NP-complete problems.

    Copyright:

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

    MCS-031 J16 Compressed

    Uploaded by

    chandrashekhar adarsh
    This document is an exam for the course MCS-031: Design and Analysis of Algorithms. It contains 6 questions, with question 1 being compulsory and students to attempt any 3 of the remaining questions. Question 1 covers characteristics of algorithms, writing a recursive factorial algorithm, importance of asymptotic analysis, and Chomsky grammar classification. It also asks to use Dijkstra's algorithm on a graph and justify whether worst-case analysis is more important than best-case analysis. The other questions cover topics like greedy algorithms, solving recurrences, Turing machines, minimum spanning trees, sorting algorithms, graph traversals, asymptotic notation, dynamic programming, and NP-complete problems.

    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 I MCS-031 I


    MCA (Revised)
    Term-End Examination
    June, 2016

    06022
    MCS-031 : DESIGN AND ANALYSIS OF
    ALGORITHMS

    Time : 3 hours Maximum Marks : 100

    Note : Question no. 1 is compulsory. Attempt any three


    questions from the rest. Parts of the same question
    . may be attempted together,

    1. (a) Explain five characteristics of an algorithm


    briefly.

    (b) Write and explain recursive algorithm to


    find the factorial of any given number
    n ?_ O.

    (c) Explain the importance of asymptotic


    analysis for running time of an algorithm
    with the help of an example.

    (d) Briefly describe Chomsky classification for


    Grammars. 5

    MCS-031 1 P.T.O.
    (e) Using Dijkstra's algorithm, find the
    minimum distances of all the nodes from
    node 'a' which is taken as the source node,
    for the following graph : 10

    (0 "The best-case analysis is not as important


    as the worst-case analysis of an algorithm."
    Yes or No ? Justify your answer with the
    help of an example. 10

    2. (a) Explain how greedy approach is useful to


    find the solution to fractional knapsack
    problem.

    (b) Solve the following recurrence relation : 5

    fn fn - 1 - fn - 2 =
    such that fo = 0 and f1 = 1.

    (c) Explain Turing Machine (TM)' as a


    computer of functions, with the help of an
    example. 8

    MCS-031
    3. (a) Using Prim's algorithm, find a minimal
    spanning tree for the graph given below : 10
    2 A 3

    6
    (b) Sort the following sequence of numbers,
    using Selection Sort. Also find the number
    of comparisons and copy operations
    required by the algorithm in sorting this
    list : 10
    20 5 15 8 6 28

    4. (a) Using Depth First Search (DFS) traverse


    the following graph by using A as the
    starting node 5

    MCS-031 3 P.T.O.
    (b) Define f2 notation used for comparing two
    functions.
    For ftx) = 2x3 + 3x2 + 1
    h(x) = 2x3 — 3x2 + 2
    show that
    (1) f(x) = a (x3)
    (ii) x2 f2 (h(x)) 5

    (c) What is dynamic programming ? Explain


    briefly the optimal substructure property of
    a dynamic programming problem. 5

    (d) What is NP-complete problem ? Is it


    necessary that every NP-complete problem
    must also be a NP-hard problem ? Justify. 5

    5. (a) Write an algorithm for Heap Sort and


    analyse its Best and Worst run time
    complexity. 10

    (b) Define a Turing Machine. 5


    (c) Consider the CFG :
    S SS/X.aXaX/A
    X —* bX/A
    Find the language generated by this CFG. 5

    MCS-031 4 7,000

    You might also like