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) (2018 Batch) (Sem.-4)
DESIGN & ANALYSIS OF ALGORITHMS
Subject Code : BTCS-403-18
M.Code : 77629
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 briefly :
- “Asympotic notation Q is transitive”. Justify.
- Define P and NP class problem.
- Give recurrence relation in general for computing complexity of divide and conquer algorithm.
- Define live node and dead node.
- Solve the recurrence equation T(n)=9 T(n/3)+n.
- What is flow network?
- What is time and space complexity?
- Define dynamic programming approach.
- Write any algorithm to find shortest path.
- What is Cook’s theorem?
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
SECTION-B
- Explain the term Algorithm with its characteristics.
- What is Knapsack problem? Justify that “All optimal solutions will fill the knapsack exactly”.
- Explain the general method of Branch and Bound.
- Give a set S=<1, 4, 5, 6, 7, 3> and W=12. Obtain the sum of subset using backtracking approach.
- Define flow network and write an iterative Ford-Fulkerson’s method for solving Max-Flow problem.
--- Content provided by FirstRanker.com ---
SECTION-C
- Explain Depth First Search and Breadth First Search method with example.
- Explain Greedy method with suitable example.
- Find the minimum spanning tree for the graph given below :
--- Content provided by FirstRanker.com ---
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)