Save as PDF
Opens your browser print dialog — select "Save as PDF" to download.
CS/SD-402 (GS)
B.Tech., IV Semester
Examination, December 2024
Grading System (GS)
Analysis Design of Algorithm
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. किसी भी प्रकार के संदेह अथवा विवाद की स्थिति में अंग्रेजी भाषा के प्रश्न को अंतिम माना जायेगा।
Give the asymptotic bounds for the equation $f(n)=2n^2-4n+20$ and represent it in terms of θ notation. समीकरण $f(n)=2n^2-4n+20$ के लिए एप्रोसीटोटिक सीमएँ दीजिए और इसे θ संकलन के रूप में निरूपित करें।
Define Quicksort? Sort the elements 22, 12, 30, 46, 28, 14, 8, 10, 56, 18, 3 using Merge sort. क्विकसॉर्ट को परिभाषित करें? मर्ज सॉर्ट का उपयोग करके तत्वों को 22, 12, 30, 46, 28, 14, 8, 10, 56, 18, 3 क्रम���द्ध करें।
Write an algorithm to find the matrix multiplication using Strassen's method. स्ट्रेसेन की विधि का उपयोग करके मैट्रिक्स गुणन खोजने के लिए एक एल्गोरिथम लिखें।
Construct a Huffman coding for the given data? Write the applications of huffman coding. दिए गए डाटा के लिए हफमैन कोडिंग का निर्माण करें? हफमैन कोडिंग के अनुप्रयोग लिखिए।
| Character | a | b | c | d | e | f |
| Frequency | 3 | 8 | 15 | 22 | 33 | 46 |
Solve the following problem of job sequencing with deadlines using the Greedy method. $n=5$ with profits $(P_1, P_2, P_3, P_4, P_5) = (5, 20, 10, 15, 1)$ and deadlines $(d_1, d_2, d_3, d_4, d_5) = (3, 2, 1, 2, 3)$. लालची विधि का उपयोग करके समय सीमा के साथ नौकरी अनुक्रमण की निम्नलिखित समस्या को हल करें, $n=5$ लाभ के साथ $(P_1, P_2, P_3, P_4, P_5) = (5, 20, 10, 15, 1)$ और समय सीमा $(d_1, d_2, d_3, d_4, d_5) = (3, 2, 1, 2, 3)$
Solve the following 0/1 Knapsack problem using dynamic programming where $n=4, M=40, (w_1, w_2, w_3, w_4) = (2, 11, 22, 15)$ and $(p_1, p_2, p_3, p_4) = (11, 21, 31, 33)$. डायनेमिक प्रोग्रामिंग का उपयोग करके निम्नलिखित 0/1 नैपसेक समस्या को हल करें जहाँ $n=4, M=40, (w_1, w_2, w_3, w_4) = (2, 11, 22, 15)$ और $(p_1, p_2, p_3, p_4) = (11, 21, 31, 33)$
Construct a multistage graph for the given graph using the Greedy method. लालची विधि का उपयोग करके दिए गए ग्राफ के लिए एक मल्टीस्टेज ग्राफ बनाइए।
Explain the Floyd Warshall algorithm for the given graph. दिए गए ग्राफ के लिए फ्लॉयड वारशल एल्गोरिथम की व्याख्या करें।
Explain in detail about the FIFO branch and bound. FIFO शाखा और बाउंड के बारे में विस्तार से बताइए।
Write an algorithm for the 8-queens problem using backtracking. बैकट्रैकिंग का उपयोग करके 8-क्वींस समस्या के लिए एक एल्गोरिथम लिखें।
Draw the state space tree for 'm' coloring when $n=3$ and $m=3$. जब $n=3$ और $m=3$ हो तो 'm' रंग के लिए स्टेट स्पेस ट्री बनाइए।
Use the function OBST to compute $w(i,j)$, $r(i,j)$ and $e(i,j)$, $0 \le i \le j \le 4$ for the identifier set $(a_1, a_2, a_3, a_4) = (\text{double, int, for, if})$ with $p(1:4) = (3,3,1,1)$ and $q(0:4) = (2,3,1,1)$. Using $r(i,j)$'s construct the optimal binary search tree. पहचानकर्ताओं के लिए $w(i,j)$, $r(i,j)$ और $e(i,j)$, $0 \le i \le j \le 4$ की गणना करने के लिए फ़ंक्शन OBST का उपयोग करें $(a_1, a_2, a_3, a_4) = (\text{double, int, for, if})$ को $p(1:4) = (3,3,1,1)$ के साथ सेट करें $q(0:4) = (2,3,1,1)$ का उपयोग करके इष्टतम बाइनरी सर्च ट्री का निर्माण कीजिए।
Explain in detail Height balanced tree with an example. ऊँचाई संतुलित वृक्ष को उदाहरण सहित विस्तार से समझाइये।
Write short notes on any two of the following.
निम्नलिखित में से किन्हीं दो पर संक्षेप टिप्पणियाँ लिखिए :
Binary search algorithm and its time complexity. बाइनरी खोज एल्गोरिथम और इसकी समय जटिलता
Single source shortest path algorithm. एकल स्रोत सबसे छोटा पथ एल्गोरिथम
Hamiltonian graph and cycle. हैमिल्टोनियन ग्राफ और चक्र
Breadth First Search. चौड़ाई पहली खोज