Scribd Logo
Upload

Welcome to Scribd!

  • 22 views

    Cs 402 Analysis

    Uploaded by

    Sandeep Kumar mehta
    This document contains an 8 question practice exam for the course CS-402 Choice Based Grading System (CBGS) Analysis Design of Algorithms. The questions cover topics like asymptotic notations, algorithm time and space complexity, sorting algorithms like quicksort and merge sort, graph algorithms like Dijkstra's and Floyd-Warshall, knapsack problem, traveling salesman problem, state space trees, backtracking, graph coloring, binary search trees, tree traversals, and NP-completeness. Students are instructed to attempt any 5 of the 8 questions.

    Copyright:

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

    Cs 402 Analysis

    Uploaded by

    Sandeep Kumar mehta
    22 views4 pages
    This document contains an 8 question practice exam for the course CS-402 Choice Based Grading System (CBGS) Analysis Design of Algorithms. The questions cover topics like asymptotic notations, algorithm time and space complexity, sorting algorithms like quicksort and merge sort, graph algorithms like Dijkstra's and Floyd-Warshall, knapsack problem, traveling salesman problem, state space trees, backtracking, graph coloring, binary search trees, tree traversals, and NP-completeness. Students are instructed to attempt any 5 of the 8 questions.

    Original Title

    cs-402-analysis

    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 contains an 8 question practice exam for the course CS-402 Choice Based Grading System (CBGS) Analysis Design of Algorithms. The questions cover topics like asymptotic notations, algorithm time and space complexity, sorting algorithms like quicksort and merge sort, graph algorithms like Dijkstra's and Floyd-Warshall, knapsack problem, traveling salesman problem, state space trees, backtracking, graph coloring, binary search trees, tree traversals, and NP-completeness. Students are instructed to attempt any 5 of the 8 questions.

    Copyright:

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

    Cs 402 Analysis

    Uploaded by

    Sandeep Kumar mehta
    This document contains an 8 question practice exam for the course CS-402 Choice Based Grading System (CBGS) Analysis Design of Algorithms. The questions cover topics like asymptotic notations, algorithm time and space complexity, sorting algorithms like quicksort and merge sort, graph algorithms like Dijkstra's and Floyd-Warshall, knapsack problem, traveling salesman problem, state space trees, backtracking, graph coloring, binary search trees, tree traversals, and NP-completeness. Students are instructed to attempt any 5 of the 8 questions.

    Copyright:

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

    https://www.rgpvonline.

    com

    Total No. of Questions : 8] [1] [Total No. of Printed Pages : 4

    Roll No ..................................
    CS-402-CBGS
    B.Tech., IV Semester
    Examination, June 2020
    Choice Based Grading System (CBGS)
    Analysis Design of Algorithms
    Time : Three Hours
    Maximum Marks : 70
    Note: i) Attempt any five questions.
    {H$Ýht nm±M àíZm| H$mo hb H$s{OE&
    ii) All questions carries equal marks.
    g^r àíZm| Ho$ g_mZ A§H$ h¢&
    iii) In case of any doubt or dispute the English version
    question should be treated as final.
    {H$gr ^r àH$ma Ho$ g§Xho AWdm {ddmX H$s pñW{V ‘| A§JO
    o« r ^mfm
    Ho$ àíZ H$mo A§{V‘ ‘mZm Om¶oJm&
    1. a) What do you mean by Asymptotic Notations? Explain
    different asymptotic notations used in algorithms.
    A{g‘mo{Q>H$ ZmoQ>e
    o Z go AmnH$m ³¶m VmËn¶© h¡? EëJmo[aÏ‘ ‘| à¶w³V
    {d{^Þ ñnem}Ý‘wI g§Ho$VZ ~VmBE&
    b) What is the need of obtaining the time and space
    complexity measures of an algorithm? Justify your answer
    by some example.
    EH$ EëJmo[aÏ‘ Ho$ Q>mB©‘ VWm ñnog O{Q>bVm Cnm¶m| H$mo àmá H$aZo
    H$s Amdí¶H$Vm ³¶m h¡? Hw$N> CXmhaU Ûmam AnZo CÎma H$mo ghr
    R>hamE±&
    CS-402-CBGS PTO

    https://www.rgpvonline.com
    https://www.rgpvonline.com

    [2]

    2. a) Show the various steps involved in the quick sorting of


    (23, 67, 12, 78, 33, 28, 97, 10, 6, 87, 39)
    Quick sorting N>±Q>mB© ‘| em{‘b {d{^Þ MaUm| H$mo {XImE±&
    (23, 67, 12, 78, 33, 28, 97, 10, 6, 87, 39)
    b) Explain merge sort algorithm and find the complexity of
    the algorithm.
    Merge sort EëJmo[aÏ‘ H$mo g‘PmBE Am¡a EëJmo[aÏ‘ H$s O{Q>bVm
    H$m nVm bJmBE&
    3. a) Using Dijkstra’s algorithm find the shortest path from A
    to D for the following graph.
    Dijkstra’s EëJmo[aÏ‘ H$m Cn¶moJ {ZåZ J«m’$ Ho$ {bE E (A) go S>r (D)
    VH$ H$m g~go N>moQ>m amñVm Imo{O¶o&

    7
    B C
    2 3
    2 3
    2
    A E F D
    1 2
    6 2
    G H

    b) Write a short note for the following:


    {ZåZ{b{IV Ho$ {bE EH$ g§{já ZmoQ> {bI| …
    i) Divide and Conquer technique
    ii) Greedy algorithm

    CS-402-CBGS PTO
    Contd...

    https://www.rgpvonline.com
    https://www.rgpvonline.com

    [3]

    4. a) Write an algorithm to solve Knapsack problem using


    Greedy technique. Find the optimal solution to the
    Knapsack instance n = 7, m = 15
    (P1, P2, P3 ... P7) = (10, 515, 7, 6, 18, 3)
    (W1, W2, W3 ... W7) = (2, 3, 5, 7, 1, 4, 1)
    Greedy VH$ZrH$ H$m Cn¶moJ H$aHo$ g‘ñ¶m H$mo hb H$aZo Ho$ {bE
    EH$ Z¡H$n¡H$ EëJmo[aÏ‘ {bI|& n = 7, m = 15 Ho$ {bE Bï>V‘
    g‘mYmZ ImoO&|
    (P1, P2, P3 ... P7) = (10, 515, 7, 6, 18, 3)
    (W1, W2, W3 ... W7) = (2, 3, 5, 7, 1, 4, 1)
    b) Explain Floyd-Warshall algorithm with an example of
    your choice.
    AnZr ng§X Ho$ CXmhaU Ho$ gmW âbmo¶S>-dmem©b EëJmo[aÏ‘ H$s
    ì¶m»¶m H$a|&

    5. a) Explain how to solve travelling salesman problem by the


    method of branch and bound and analyze complexity of
    the algorithm.
    ~VmBE {H$ branch and bound VarHo$ go Q´>¡dqbJ goëg‘¡Z H$s
    g‘ñ¶m H$mo H¡$go hb {H$¶m OmE Am¡a EëJmo[aÏ‘ H$s O{Q>bVm H$mo
    ~mܶ Am¡a {díbofU {H$¶m OmE&
    b) Construct state space tree for solving four queen’s
    problem using backtracking.
    ~¡H$Q´>q¡ H$J H$m Cn¶moJ H$aHo$ four queen’s g‘ñ¶m H$mo hb H$aZo Ho$
    {bE state space tree H$m {Z‘m©U H$a|&

    CS-402-CBGS PTO

    https://www.rgpvonline.com
    https://www.rgpvonline.com

    [4]

    6. a) Give a brief note on :


    g§{já ZmoQ> X| …
    i) Parallel algorithms
    ii) Graph coloring
    b) What is Backtracking? Discuss any one problem solved
    by backtracking. Also give its advantages and
    disadvantages.
    ~¡H$Q´>q¡ H$J ³¶m h¡? {H$gr ^r EH$ g‘ñ¶m Ho$ ~mao ‘| MMm© H$a| {OgH$m
    ~¡H$Q´>¡qH$J Ûmam hb {H$¶m J¶m h¡& BgHo$ ’$m¶Xo Am¡a ZwH$gmZ ^r
    ~VmBE&
    7. a) Differentiate between DFS and BFS algorithms by an
    example.
    EH$ CXmhaU Ûmam DFS Am¡a BFS EëJmo[aÏ‘ Ho$ ~rM A§Va ~VmBE&
    b) What are B-trees? How are they created? Give its
    advantages.
    B-trees ³¶m h¢? do H¡$go ~ZmE OmVo h¢? BgHo$ ’$m¶Xo ~VmBE&
    8. Write short notes :
    g§{já ZmoQ> {bI| …
    i) Binary Search Trees
    ii) Tree Traversals
    iii) NP-Completeness
    iv) Reliability design

    ******

    CS-402-CBGS PTO

    https://www.rgpvonline.com

    You might also like