[go: up one dir, main page]
Scribd
Upload
117 views4 pages

Cs 402 Analysis

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.

Uploaded by

Sandeep Kumar mehta
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
117 views4 pages

Cs 402 Analysis

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.

Uploaded by

Sandeep Kumar mehta
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 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