Save as PDF
Opens your browser print dialog — select "Save as PDF" to download.
Total No. of Questions : 8
[Total No. of Printed Pages : 4
[2]
Roll No.......................................
CY-502 (GS)
B.Tech., V Semester
Examination, November 2022
Grading System (GS)
Design And Analysis of Algorithms
Time : Three Hours
Maximum Marks : 70
Note: i)
Answer any five questions.
हिन्दी पाँच प्रश्नों को हल कीजिए।
ii)
All questions carry equal marks.
सभी प्रश्नों के समान अंक हैं।
iii)
In case of any doubt or dispute the English version question should be treated as final.
किसी भी प्रकार के संदेह अथवा विवाद की स्थिति में अंग्रेजी भाषा के प्रश्न को अंतिम माना जायेगा।
1. a)
Show that the average case time complexity of quick sort is O(n log n)
दिखाइए कि त्वरित सॉर्ट ��ी औसत केस समय जटिलता O(n log n) है।
b)
Write and solve recurrence relation for Strassen's matrix multiplication
स्ट्रॉसेन के मैट्रिक्स गुणन के लिए पुनरावृत्ति संबंध लिखें और हल करें।
2. a)
Compute the optimal solution for knapsack problem using greedy method N=3, M=20, (p1, p2, p3) = (25, 24, 15), (w1, w2, w3) =(18, 15, 10)
लालची विधि का उपयोग करके नैपसैक समस्या के लिए इष्टतम समाधान की गणना करें। N=3, M=20, (p1, p2, p3) = (25, 24, 15), (w1, w2, w3) =(18, 15, 10)
b)
Construct minimum cost spanning tree using:
न्यूनतम लागत वाले ट्री का उपयोग करके निर्माण करें।
- Prim's algorithmप्रिस्म एल्गोरिथम
- Kruskal algorithmक्रुस्कल एल्गोरिथम
3. a)
Solve the solution for 0/1 knapsack problem using dynamic programming N=3, m=6 profits (p1, p2, p3) = (1, 2, 5) weights (w1, w2, w3) = (2, 3, 4).
गतिशील प्रोग्रामिंग N=3, m=6 लाभ (p1, p2, p3) = (1, 2, 5) वजन (w1, w2, w3) = (2, 3, 4) का उपयोग करके 0/1 knapsack समस्या का समाधान हल करें।
b)
What is a Graph, a Multistage graph? What is the application of a multistage graph?
एक ग्राफ, एक मल्टीस्टेज ग्राफ क्या है? मल्टीस्टेज ग्राफ का अनुप्रयोग क्या है?
4. a)
Write an algorithm for Hamiltonian cycle with an example.
एक उदाहरण के साथ हैमिल्टनियन चक्र के लिए एक एल्गोरिथम लिखें।
b)
What an algorithm for graph coloring and solve the following graph?
ग्राफ रंग भरने के लिए एक एल्गोरिथम क्या है? और निम्न ग्राफ को हल करें।
5. a)
Explain the method of reduction to solve traveling sales person problem using branch and bound.
ब्रांच और बाउंड का उपयोग करके ट्रैवलिंग सेल्सपर्सन की समस्या को हल करने के लिए कमी की विधि की व्याख्या करें।
b)
Sketch the state space tree degenerated by 4-queens problem.
4 रानियों की समस्या से पतित स्टेट स्पेस ट्री क��� स्केच करें।
6. a)
Distinguish NP- hard and NP-complete problems.
एनपी-हार्ड और एनपी-पूर्ण समस्याओं में अंतर करें।
b)
What is a data stream algorithm? How are algorithms used in streaming services? Explain with an example.
डेटा स्ट्रीम एल्गोरिथम क्या है? स्ट्रीमिंग सेवाओं में एल्गोरिथम का उपयोग कैसे किया जाता है? एक उदाहरण के साथ समझाइए।
7. a)
How do you prove the Correctness proof of Greedy algorithm? Explain.
आप लालची एल्गोरिथम के शुद्धता प्रमाण को कैसे सिद्ध करते हैं? समझाइए।
b)
For the following matrix, Describe Strassen's matrix multiplication
निम्नलिखित मैट्रिक्स के लिए स्ट्रैसेन के मैट्रिक्स गुणन का वर्णन करें।
8.
Write short notes on any two:
किन्हीं दो पर संक्षिप्त टिप्पणी लिखिए।
a)
Logic Optimization
तर्क अभिष्टतम
b)
Optimal merge patterns
इष्टतम मर्ज पैटर्न
c)
If f(n)=5n2 + 6n + 4, then prove that f(n) is O(n2)
यदि f(n)=5n2 + 6n + 4 तो सिद्ध कीजिए कि f(n) O(n2) है
d)
Parallel Algorithm
समानांतर एल्गोरिथम