Download PTU (I.K.Gujral Punjab Technical University (IKGPTU)) B-Tech (Bachelor of Technology) (CSE-IT)- Computer Science Engineering -Information Technology 2020 December 4th Sem 77629 Design And Analysis Of Algorithms Previous Question Paper
Roll No.
Total No. of Pages : 02
Total No. of Questions : 18
B.Tech. (CSE) (2018 Batch) (Sem.?4)
DESIGN & ANALYSIS OF ALGORITHMS
Subject Code : BTCS-403-18
M.Code : 77629
Time : 3 Hrs. Max. Marks : 60
INST RUCT IONS T O CANDIDAT ES :
1 .
SECT ION-A is COMPULSORY cons is ting of TEN questions carrying TWO marks
each.
2 .
SECT ION-B c ontains F IVE questions c arrying FIVE marks eac h and s tud ents
have to atte mpt any FOUR q ues tions.
3 .
SECT ION-C contains THREE questions carrying T EN marks e ach and s tudents
have to atte mpt any T WO questio ns.
SECTION-A
Answer briefly :
1.
"Asympotic notation is transitive". Justify.
2.
Define P and NP class problem.
3.
Give recurrence relation in general for computing complexity of divide and conquer
algorithm.
4.
Define live node and dead node.
5.
Solve the recurrence equation T(n)=9 T(n/3)+n.
6.
What is flow network?
7.
What is time and space complexity?
8.
Define dynamic programming approach.
9.
Write any algorithm to find shortest path.
10. What is Cook's theorem?
1 | M-77629
(S2)-551
SECTION-B
11. Explain the term Algorithm with its characterstics.
12. What is Knapsack problem? Justify that "All optimal solutions will fill the knapsack
exactly".
13. Explain the general method of Branch and Bound.
14. Give a set S=<1, 4, 5, 6, 7, 3> and W=12. Obtain the sum of subset using backtracking
approach.
15. Define flow network and write an iterative Ford-Fulkerson's method for solving
Max- Flow problem.
SECTION-C
16. Explain Depth First Search and Breadth First Search method with example.
17. Explain Greedy method with suitable example.
18. Find the minimum spanning tree for the graph given below :
10
6
5
10
4
2
4
2
4
1
0
30
1
15
2
3
10
FIG.1
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.
2 | M-77629
(S2)-551
This post was last modified on 13 February 2021