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
Roll No
CY-502 (GS)
B. Tech. V Semester
Examination, December 2025
Grading System (GS)
Design and Analysis of Algorithm
Time: Three Hours
Maximum Marks: 70
Note: (i) Attempt 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) Define an algorithm. Explain time and space complexity and the concept of time-space tradeoff.
एल्गोरिथम को परिभाषित करें। समय तथा स्थान जटिलता और समय-स्थान ट्रेड ऑफ की अवधारणा समझाइए।
एल्गोरिथम को परिभाषित करें। समय तथा स्थान जटिलता और समय-स्थान ट्रेड ऑफ की अवधारणा समझाइए।
(b) Explain asymptotic notations O, Ω and θ with suitable examples.
उपयुक्त उदाहरणों सहित एसिम्प्टोटिक नोटेशन O, Ω तथा θ की व्याख्या करें।
उपयुक्त उदाहरणों सहित एसिम्प्टोटिक नोटेशन O, Ω तथा θ की व्याख्या करें।
2.
(a) Explain recurrence relations and methods to solve them.
रिकरेंस रिलेशन तथा इन्हें हल करने की विधियों की व्याख्या करें।
रिकरेंस रिलेशन तथा इन्हें हल करने की विधियों की व्याख्या करें।
(b) Solve the recurrence T(n)=2T(n/2) + n using Master's methods.
मास्टर विधि का उपयोग करते हुए रिकरेंस हल करें: T(n)=2T(n/2)+n
मास्टर विधि का उपयोग करते हुए रिकरेंस हल करें: T(n)=2T(n/2)+n
3.
(a) Explain the divide and conquer technique with reference to merge sort.
मर्ज सॉर्ट के संदर्भ में डिवाइड एंड कॉन्कर तकनीक की व्याख्या करें।
मर्ज सॉर्ट के संदर्भ में डिवाइड एंड कॉन्कर तकनीक की व्याख्या करें।
(b) Apply binary search to find 25 in the sorted array [5, 10, 15, 20, 25, 30, 35]. Show the steps.
सॉर्टेड एरे [5, 10, 15, 20, 25, 30, 35] में 25 को खोजने हेतु बाइनरी सर्च लागू करें और चरण दर्शाइए।
सॉर्टेड एरे [5, 10, 15, 20, 25, 30, 35] में 25 को खोजने हेतु बाइनरी सर्च लागू करें और चरण दर्शाइए।
4.
(a) Explain the greedy method. Discuss its strategy and characteristics.
ग्रीडी विधि की व्याख्या करें। इसकी रणनीति और विशेषताओं पर चर्चा करें।
ग्रीडी विधि की व्याख्या करें। इसकी रणनीति और विशेषताओं पर चर्चा करें।
(b) Construct a minimum spanning tree using Kruskal's algorithm for the given graph as shown in FIGURE (A) as mentioned below.
5.
(a) Explain dynamic programming and its characteristics.
डायनामिक प्रोग्रामिंग तथा इसकी विशेषताओं की व्याख्या करें।
डायनामिक प्रोग्रामिंग तथा इसकी विशेषताओं की व्याख्या करें।
(b) Solve the 0/1 knapsack problem for weights {2, 3, 4}, values {1, 2, 5} and capacity = 5.
वजन {2, 3, 4}, मूल्य {1, 2, 5} तथा क्षमता = 5 के लिए 0/1 नेपसैक समस्या हल करें।
वजन {2, 3, 4}, मूल्य {1, 2, 5} तथा क्षमता = 5 के लिए 0/1 नेपसैक समस्या हल करें।
6.
(a) Explain the concept of backtracking with reference to the 8-queens problem.
8 क्वीन समस्या के संदर्भ में बैकट्रैकिंग की अवधारणा की व्याख्या करें।
8 क्वीन समस्या के संदर्भ में बैकट्रैकिंग की अवधारणा की व्याख्या करें।
(b) Apply the Branch and Bound algorithm to solve the travelling salesperson problem for the given graph as shown in FIGURE (B).
7.
(a) Explain NP-hard and NP-complete problems with suitable examples.
उपयुक्त उदाहरणों सहित NP-hard तथा NP-complete समस्याओं की व्याख्या करें।
उपयुक्त उदाहरणों सहित NP-hard तथा NP-complete समस्याओं की व्याख्या करें।
8.
(a) What are approximation algorithms? Explain their need and applications.
एप्रोक्सीमेशन एल्गोरिथम क्या हैं? उनकी आवश्यकता और अनुप्रयोगों की व्याख्या करें।
एप्रोक्सीमेशन एल्गोरिथम क्या हैं? उनकी आवश्यकता और अनुप्रयोगों की व्याख्या करें।
(b) Write short notes on data stream algorithms and parallel algorithms.
डेटा स्ट्रीम एल्गोरिथम तथा पैरलल एल्गोरिथम पर संक्षिप्त टिप्पणी लिखिए।
डेटा स्ट्रीम एल्गोरिथम तथा पैरलल एल्गोरिथम पर संक्षिप्त टिप्पणी लिखिए।