This download link is referred from the post: PTU B.Tech Question Papers 2020 December (All Branches)
Total No. of Pages : 02
Total No. of Questions : 18
--- Content provided by FirstRanker.com ---
B.Tech. (CSE) (2012 to 2017) (Sem.-5)
DESIGN & ANALYSIS OF ALGORITHMS
Subject Code : BTCS-503
M.Code : 70536
Time : 3 Hrs. Max. Marks : 60
--- Content provided by FirstRanker.com ---
INSTRUCTIONS TO CANDIDATES :
- SECTION-A is COMPULSORY consisting of TEN questions carrying TWO marks each.
- SECTION-B contains FIVE questions carrying FIVE marks each and students have to attempt any FOUR questions.
- SECTION-C contains THREE questions carrying TEN marks each and students have to attempt any TWO questions.
SECTION-A
--- Content provided by FirstRanker.com ---
Answer the following briefly :
- What is asymptotic notation?
- Define Big Oh.
- What are the steps involved in proving a problem to be NP complete?
- What are the applications of Fast Fourier transform?
- How the Prim’s algorithm is better in finding the Minimal spanning tree in comparison to the Kruskal’s method?
- What is the time complexity of the algorithm for finding all-pairs-shortest-path problem?
- What are NP class problems?
- What is the minimal spanning tree? What are its advantages?
- What is a deterministic algorithm?
- Distinguish between deterministic and non-deterministic algorithms.
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
SECTION-B
- What is the relationship between the classes P and NP? Explain. (5)
- Explain the Big -Oh computation for each of the following control structures : (5)
a) Sequencing b) If-then-else c) “for” loop--- Content provided by FirstRanker.com ---
d) “While” loop e) Recursion - What do you analyze in an algorithm? What is the basis of analysis? Explain. (5)
- Explain topological sort with an example. (5)
- What are greedy algorithms? What are their characteristics? Explain any greedy algorithm with example. (5)
SECTION-C
--- Content provided by FirstRanker.com ---
- Explain the KMP algorithm in detail with an illustrative example. (10)
- Explain in detail quick sorting method. Provide a complete analysis of quick sort. (10)
- Order the following functions by growth rate: N, N1.5, N log log N, N log2 N, N log (N2), 2/N, 2N, 2√N, N2 log N, N4. Indicate which functions grow at the same rate. (10)
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.
--- Content provided by FirstRanker.com ---
This download link is referred from the post: PTU B.Tech Question Papers 2020 December (All Branches)
--- Content provided by FirstRanker.com ---