Roll No. [ TTTTTT] [ ] Total No. of Pages : 02
Total No. of Questions : 18
--- Content provided by FirstRanker.com ---
B.Tech. (CSE) (Sem.=5)DESIGN AND ANALYSIS OF ALGORITHMS
Subject Code : CS-307
M.Code : 56526
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 ---
Write briefly :
- How is the time complexity measured?
- What is dynamic programming?
- What is a deterministic algorithm?
- What do you mean by the running time of an algorithm?
- What are P and NP problems?
- What is the working principle of quicksort?
- What are NP-complete algorithms?
- What do you understand by Divide and Conquer strategy?
- Are the sub solutions overlapping in dynamic programming approach?
- What is the branch and bound technique?
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
SECTION-B
Find the Big-OH notations for the following functions :
- a) f(n) - 78889
- b) f(n)=6n"+135
- c) f(n)=7n"+8n+56
- d) f(n)=n*+35n"+84
--- Content provided by FirstRanker.com ---
- What do you analyze in an algorithm? What is the basis of analysis? Explain
- What are greedy algorithms? What are their characteristics? Explain any greedy algorithm with example.
- Explain the KMP algorithm in detail with an illustrative example.
- Write an algorithm to solve APSP problem.
--- Content provided by FirstRanker.com ---
SECTION-C
- Consider five items along with their respective weights and values :
I=<il, 12, i3, i4, i5>
w =<5,10,20,30,40>--- Content provided by FirstRanker.com ---
v =<30,20,100,90,160>
The capacity of the knapsack W = 60.Find the solution for the fractional knapsack problem. - What is the relationship among P, NP and NP complete problems? Show with the help of a diagram.
- 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.
--- Content provided by FirstRanker.com ---
This download link is referred from the post: PTU B.Tech Question Papers 2020 March (All Branches)
--- Content provided by FirstRanker.com ---