This download link is referred from the post: PTU B.Tech Question Papers 2020 March (All Branches)
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 :
- 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 closest pair problem?
- How dynamic programming is used to solve knapsack problem?
- How time complexity of an algorithm is different from space complexity?
- Difference between NP, NP-complete and NP-hard Problem?
- Write any two applications of Fast Fourier Transform.
- Write a short note on : Strassen’s algorithm.
- What is 3 SAT problem?
- What are the applications of BFS?
- Differentiate between Polynomial and Exponential running time.
- What is an algorithm?
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
SECTION-B
- Bring out the differences between Prim’s and Kruskal’s algorithm. Also compare with respect to efficiency analysis.
- Use the substitution method to prove a tight asymptotic lower bound (Ω-notation) on the solution to the recurrence T(n) = 4T(n/2) + n2
- 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.
- 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?
- 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 d1<d2<...... <dn be the locations of all the gas stations along the route where di 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.
--- Content provided by FirstRanker.com ---
SECTION-C
- 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.
- Give the solution for Knapsack with Branch and Bound. The capacity of Knapsack is m = 12. There are 5 objects with profit (p1,p2,p3,p4,p5) = (10,15,6,8,4) and weights (W1,W2,W3,W4,W5) = (4,6,3,4,2).
- Write a program for recursive binary search to find the given element within array. For What data binary search is not applicable?
--- 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 March (All Branches)