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 77540 Design And Analysis Of Algorithms Previous Question Paper
Roll No.
Total No. of Pages : 02
Total No. of Questions : 18
B.Tech. (IT) (2018 Batch) (Sem.?4)
DESIGN & ANALYSIS OF ALGORITHMS
Subject Code : BTIT-403-18
M.Code : 77540
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.
How to measure an algorithm's running time?
2.
What do you mean by "worst case efficiency of an algorithm"?
3.
Differentiate between graph and tree.
4.
What is minimal spanning tree?
5.
Give an example of dynamic programming approach.
6.
What are the graph traversal techniques?
7.
State approximation technique.
8.
Give an example of dynamic programming approach.
9.
Differentiate between time efficiency and space efficiency.
10. What is flow network?
1 | M-77540
(S2)-330
SECTION-B
11. Write a short note on greedy strategy to solve a problem.
12. Solve the following problem by using least cost branch and bound method :
Knapsack instance n = 4, p(1:4) = {1,1,12,18} and
Weight w (1:4) = (2,4,6,9) & max capacity m =15
13. What is the relationship among P, NP and NP complete problems? Show with the help of a
diagram.
B
D
A
C
E
S
F
G
H
FIG.1
14. Traverse all the vertices of above figure using breadth first search.
15. Find the adjacency list and adjacency matrix of below figure.
1
3
4
0
2
5
FIG.2
SECTION-C
16. Explain the advantages of using dynamic programming. Introduce travelling salesman
problem. Explain the technique to solve travelling salesman problem using this technique.
17. Why do we perform topological sorts only on directed acyclic graph? Explain
18. Discuss Heuristics and its characteristic.
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-77540
(S2)-330
This post was last modified on 13 February 2021