Save as PDF
Opens your browser print dialog — select "Save as PDF" to download.
Total No. of Questions : 8
[2]
Total No. of Printed Pages : 6
Roll No. ........................
CS/SD-402
B.Tech./B.Tech. (Working Professional) IV Semester
Examination, June 2025
Grading System (GS) / Working Professional
Analysis Design of Algorithm
B.Tech./B.Tech. (Working Professional) IV Semester
Examination, June 2025
Grading System (GS) / Working Professional
Analysis Design 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.
किसी भी प्रकार के संदेह अथवा विवाद की स्थिति में अंग्रेजी भाषा के प्रश्न को अंतिम माना जायेगा।
b)
The worst case time of procedure merge sort is O (nlogn). What is its best case time? Can we say that the time for merge sort is O (nlogn)?
मर्ज सॉर्ट प्रक्रिया का सबसे खराब स्थिति समय O (nlogn) है। इसका सबसे अच्छा समय क्या है? क्या हम कह सकते हैं कि मर्ज सॉर्ट का समय O (nlogn) है?
2. a)
Obtain a set of optimal Huffman codes for message (M1, ... M7) with relative frequencies (q1, q2 ......q7) = (4, 5, 7, 8, 10, 12, 20). Draw the decode tree for this set of codes.
सापेक्ष आवृत्तियों (q1, q2 ......q7) = (4, 5, 7, 8, 10, 12, 20) के साथ संदेश (M1, ... M7) के लिए इष्टतम हफमैन कोड का एक सेट प्राप्त करें। कोड के इस सेट के लिए डिकोड ट्री बनाएं।
b)
Use algorithm shortest paths to obtain in non-decreasing order the lengths of the shortest paths from vertex 1 to all remaining vertices in the di-graph.
दिए गए ग्राफ में शीर्ष 1 से शेष सभी शीर्षों तक सबसे छोटे पथों की लंबाई को गैर-घटते क्रम में प्राप्त करने के लिए सब���े छोटे पथ एल्गोरिदम का उपयोग करें।
1. a)
Solve the following recurrence relations using the substitution method.
प्रतिस्थापन विधि का उपयोग करके निम्नलिखित पुनरावृत्ति संबंधों को हल करें।
T(n) = { 1
2T(√n) + logn } if n ≤ 4
if n > 4
2T(√n) + logn } if n ≤ 4
if n > 4
3. a)
Give an example of a set of knapsack instances for which
for each n.
|S'| = 20.1S|n
The set should include one instance for each n.
नैपसैक उदाहरणों के एक सेट का उदाहरण दें जिसके लिए
होना चाहिए।
|S'| = 20.1S|n
सेट में प्रत्येक n के लिए एक उदाहरण शामिल होना चाहिए।
b)
Explain Floyd Warshall algorithm with suitable example.
फ्लॉइड वॉर्शल एल्गोरिथम को उपयुक्त उदाहरण के साथ समझाइए।
4. a)
Given an n × n chessboard, a knight is placed on an arbitrary square with coordinates (x, y). The problem is to determine n2-1 Knight moves such that every square of the board is visited once if such a sequence of moves exists. Present an algorithm to solve this problem.
एक n × n शतरंज की बिसात को देखते हुए, एक शूरव���र को निर्देशांक (x, y) के साथ एक मनमाने वर्ग पर रखा जाता है। समस्या n2-1 नाइट चालों को इस प्रकार निर्धारित करने की है कि यदि चालों का ऐसा क्रम मौजूद है तो बोर्ड के प्रत्येक वर्ग का एक बार दौरा किया जाए। इस समस्या को हल करने के लिए एल्गोरिथम प्रस्तुत करें।
b)
Consider the traveling salesperson instance defined by the cost matrix.
लागत मैट्रिक्स द्वारा परिभाषित यात्रा विक्रेता उदाहरण पर विचार करें।
5. a)
Show that DFS visits all vertices in G reachable from V. Discuss what DFS, G & V are.
दिखाएँ कि DFS, G में V से पहुँच योग्य सभी शीर्षों पर जाता है। DFS, G & V से पहुँचा योग्य सभी शीर्षों पर जाता है।
Obtain a nondeterministic algorithm of complexity O(n) to determine whether there is a subset of n numbers a1, s1 ≤ 1sn, that sums, m.
यह निर्धार���त करने के लिए कि क्या n संख्याओं a1, S1 ≤ 1Sn का एक उपसमुच्चय है, 'जो m का योग है, जटिलता O(n) का एक गैर-नियतात्मक एल्गोरिथम प्राप्त करें।
6. a)
Write an algorithm to delete an element x from a binary search tree t. What is the time complexity of your algorithm?
बाइनरी सर्च ट्री t से तत्व x को हटाने के लिए एक एल्गोरिथम लिखें। आपके एल्गोरिथम की समय जटिलता क्या है?
7. a)
What do you mean by balance factor in AVL tree? Give a suitable example to balance a AVL tree.
AVL ट्री में बैलेंस फैक्टर से आपका क्या अभिप्राय है? AVL ट्री को संतुलित करने के लिए एक उपयुक्त उदाहरण दीजिए।
b)
Suppose there are n jobs to be executed but only k processors that can work in parallel. The time required by jobs i to ti, write an algorithm that determines which jobs are to be run on which processors and the order in which they should be run so that the finish time of the last job is minimized.
मान लीजिए कि निष्पादित करने के लिए n जॉब्स हैं लेकिन केवल k प्रोसेसर हैं जो समानांतर में काम कर सकते हैं। जॉब्स के लिए आवश्यक समय i से ti है, एक एल्गोरिथम लिखें जो निर्धारित करता है कि कौन से जॉब्स किस प्रोसेसर पर चलाए जाने हैं और उन्हें किस क्रम में चलाया जाना चाहिए ताकि अंतिम कार्य का समापन समय कम से कम हो।
b)
Find optimal solution for 0/1 knapsack problem (W1, W2, W3, W4) = (10, 15, 6, 9), (P1, P2, P3, P4) = (2, 5, 8, 1) and M = 30.
0/1 नैपसैक समस्या के लिए इष्टतम समाधान खोजें (W1, W2, W3, W4) = (10, 15, 6, 9), (P1, P2, P3, P4) = (2, 5, 8, 1) और M = 30।
Write short notes on following. (any two)
निम्नलिखित पर संक्षिप्त नोट्स लिखें। (कोई दो)
a)
B-Trees
B-पेड़
b)
Tree Traversal
ट्री ट्रैवर्सल
c)
Reliability Design
विश्वसनीयता डिजाइन