Download PTU (I.K. Gujral Punjab Technical University Jalandhar (IKGPTU) ) BE/BTech CSE/IT (Computer Science And Engineering/ Information Technology) 2020 March 5th Sem CS 307 Design And Analysis Of Algorithms Previous Question Paper
Roll No. Total No. of Pages : 02
Total No. of Questions : 18
B.Tech. (CSE) (Sem.?5)
DESIGN AND ANALYSIS OF ALGORITHMS
Subject Code : CS-307
M.Code : 56526
Time : 3 Hrs. Max. Marks : 60
INSTRUCTIONS TO CANDIDATES :
1. SECTION-A is COMPULSORY consisting of TEN questions carrying TWO marks
each.
2. SECTION-B contains FIVE questions carrying FIVE marks each and students
have to attempt any FOUR questions.
3. SECTION-C contains THREE questions carrying TEN marks each and students
have to attempt any TWO questions.
SECTION-A
Write briefly :
1) How is the time complexity measured?
2) What is dynamic programming?
3) What is a deterministic algorithm?
4) What do you mean by the running time of an algorithm?
5) What are P and NP problems?
6) What is the working principle of quicksort?
7) What are NP-complete algorithms?
8) What do you understand by Divide and Conquer strategy?
9) Are the sub solutions overlapping in dynamic programming approach?
10) What is the branch and bound technique?
FirstRanker.com - FirstRanker's Choice
1 | M-56526 (S2)-2725
Roll No. Total No. of Pages : 02
Total No. of Questions : 18
B.Tech. (CSE) (Sem.?5)
DESIGN AND ANALYSIS OF ALGORITHMS
Subject Code : CS-307
M.Code : 56526
Time : 3 Hrs. Max. Marks : 60
INSTRUCTIONS TO CANDIDATES :
1. SECTION-A is COMPULSORY consisting of TEN questions carrying TWO marks
each.
2. SECTION-B contains FIVE questions carrying FIVE marks each and students
have to attempt any FOUR questions.
3. SECTION-C contains THREE questions carrying TEN marks each and students
have to attempt any TWO questions.
SECTION-A
Write briefly :
1) How is the time complexity measured?
2) What is dynamic programming?
3) What is a deterministic algorithm?
4) What do you mean by the running time of an algorithm?
5) What are P and NP problems?
6) What is the working principle of quicksort?
7) What are NP-complete algorithms?
8) What do you understand by Divide and Conquer strategy?
9) Are the sub solutions overlapping in dynamic programming approach?
10) What is the branch and bound technique?
2 | M-56526 (S2)-2725
SECTION-B
11) Find the Big-OH notations for the following functions :
a) f(n) - 78889
b) f(n) = 6 n
2
+ 135
c) f(n) = 7 n
2
+ 8n + 56
d) f(n) = n
4
+ 35n
2
+ 84
12) What do you analyze in an algorithm? What is the basis of analysis? Explain
13) What are greedy algorithms? What are their characteristics? Explain any greedy
algorithm with example.
14) Explain the KMP algorithm in detail with an illustrative example.
15) Write an algorithm to solve APSP problem.
SECTION-C
16) Consider five items along with their respective weights and values :
I =
w = <5,10,20,30,40>
v = <30,20,100,90,160>
The capacity of the knapsack W = 60.Find the solution for the fractional knapsack
problem.
17) What is the relationship among P, NP and NP complete problems? Show with the help of
a diagram.
18) Compare the various programming paradigms such as divide-and-conquer, dynamic
programming and greedy approach.
NOTE : Disclosure of Identity by writing Mobile No. or Making of passing request on any
page of Answer Sheet will lead to UMC against the Student.
FirstRanker.com - FirstRanker's Choice
This post was last modified on 21 March 2020