Download PTU B.Tech 2020 March CSE-IT 5th Sem BTCS 503 Design & Analysis Of Algorithms Question Paper

FirstRanker.com

Roll No. [ ] [T T T TT] 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 ---

INSTRUCTION TO CANDIDATES :

1. SECTION-A is COMPULSORY consisting of TEN questions carrying TWO marks each.
2. SECTION-B contains FIVE questions carrying FIVE marks each and students have to attempt any FOUR questions.
3. 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 :

1. What is closest pair problem?
2. How dynamic programming is used to solve knapsack problem?
3. How time complexity of an algorithm is different from space complexity?
4. Difference between NP, NP-complete and NP-hard Problem?

--- Content provided by‌ FirstRanker.com ---

5. Write any two applications of Fast Fourier Transform.
6. Write a short note on : Strassen’s algorithm.
7. What is 3 SAT problem?
8. What are the applications of BFS?
9. Differentiate between Polynomial and Exponential running time.

--- Content provided by FirstRanker.com ---

10. What is an algorithm?

SECTION-B

11. Bring out the differences between Prim’s and Kruskal’s algorithm. Also compare with respect to efficiency analysis.
12. Use the substitution method to prove a tight asymptotic lower bound (O-notation) on the solution to the recurrence T(n) = 4T(n/2) + n²
13. Suppose that H[1, .... , n] is an array containing a Min-Heap. Give pseudocode for an algorithm Extract-Min(H, n) that removes the smallest element from the heap H of size n and returns its value. Analyze the time complexity of your algorithm. Explain your algorithm.

--- Content provided by⁠ FirstRanker.com ---

14. Suppose we use Dijkstra’s greedy, single source shortest path algorithm on an undirected graph. What constraint must we have for the algorithm to work and why?
15. Suppose you were to drive from Delhi to Mumbai. Your gas tank, when full, holds enough gas to travel m miles, and you have a map that gives distances between gas stations along the route. Let d₁<d₂<...... <d_n be the locations of all the gas stations along the route where d_i is the distance from Delhi to the gas station. You can assume that the distance between neighboring gas stations is at most m miles. Your goal is to make as few gas stops as possible along the way. Give the most efficient algorithm you can find to determine at which gas stations you should stop and prove that your strategy yields an optimal solution. Be sure to give the time complexity of your algorithm as a function of n.

SECTION-C

16. A max heap is given with n elements and its height is log (n). Write an efficient algorithm to find minimum element in heap. Also calculate the time and space complexity.
17. Give the solution for Knapsack with Branch and Bound. The capacity of Knapsack is m = 12. There are 5 objects with profit (p₁,p₂,p₃,p₄,p₅) = (10,15,6,8,4) and weights (W₁,W₂,W₃,W₄,W₅) = (4,6,3,4,2).

--- Content provided by‌ FirstRanker.com ---

18. Write a program for recursive binary search to find the given element within array. For What data binary search is not applicable?

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.

FirstRanker.com