a) Obtain the asymptotic bound using the substitution method for the recurrence relation T(n) = 3T(n/3) + n and represent it in terms of θ notation.

पुनरावृत्ति संबंध T(n) = 3T(n/3) + n के लिए प्रतिस्थापन विधि का उपयोग करके एसिम्पटोटिक बाउंड प्राप्त करने और इसे θ अंकन के संदर्भ में प्रस्तुत करें।

b) What is Merge sort? Sort the elements 20.30.15.11.35.19.12.11.55 using Merge sort.

मर्ज सॉर्ट क्या है? मर्ज सॉर्ट का उपयोग करके तत्वों को 20.30.15.11.35.19.12.11.55 क्रमबद्ध करें।

a) Discuss Strassen's matrix multiplication and Classical O(n³) methods. Determine when Strassen's method outperforms classical method.

स्ट्रासेन के मैट्रिक्स गुणन और शास्त्रीय O(n³) विधियों पर चर्चा करें। निर्धारित करें कि स्ट्रासेन की विधि शास्त्रीय विधि से कब बेहतर प्रदर्शन करती है।

b) Define spanning tree? Construct a minimum spanning tree for the given graph using Prim's algorithm.

पहले हुए वृक्ष को परिभाषित करें। प्राइम के एल्गोरिथम का उपयोग करके दिए गए ग्राफ के लिए न्यूनतम स्पैनिंग ट्री का निर्माण करें।

Solve the following problem of job sequencing with deadlines using the Greedy method.

n = 4, (p₁, p₂, p₃, p₄) = (100, 10, 15, 27) and (d₁, d₂, d₃, d₄) = (2, 1, 2, 1).

ग्रेडी विधि का उपयोग करके समय सीमा के साथ नौकरी अनुक्रमण की निम्नलिखित समस्या को हल करें।

n = 4, (p₁, p₂, p₃, p₄) = (100, 10, 15, 27) और (d₁, d₂, d₃, d₄) = (2, 1, 2, 1)

a) Apply the greedy method to solve the 0/1 Knapsack problem for n = 3, m = 20, (w₁, w₂, w₃) = (18, 15, 10) and (p₁, p₂, p₃) = (25, 24, 15).

n = 3, m = 20, (w₁, w₂, w₃) = (18, 15, 10) और (p₁, p₂, p₃) = (25, 24, 15) के लिए 0/1 नैपसैक समस्या को हल करने के लिए ग्रेडी विधि लागू करें।

b) Construct a multistage graph for the given graph using the greedy method.

ग्रेडी विधि का उपयोग करके दिए गए ग्राफ के लिए एक मल्टीस्टेज ग्राफ बनाएँ।

a) Explain the Floyd Warshall algorithm for the given graph.

दिए गए ग्राफ के लिए फ्लॉयड वॉरशॉल एल्गोरिथम की व्याख्या करें।

b) Using branch and bound technique explain the 0/1 knapsack problem.

ब्रांच और बाउंड तकनीक का उपयोग करके 0/1 नैपसैक समस्या की व्याख्या करें।

a) Give the solution to the 8-queens problem using backtracking.

बैकट्रैकिंग का उपयोग करके 8-क्वींस स���स्या का समाधान बताएँ।

b) What is graph coloring? Explain graph coloring for the given graph.

ग्राफ रंग क्या है? दिए गए ग्राफ के लिए ग्राफ रंग की व्याख्या करें।

a) Use the function OBST to compute w(i, j), r(i, j) and c(i, j), 0 ≤ i ≤ j ≤ 4 for the identifier set {a₁, a₂, a₃, a₄} = (char, float, while, else) with p(1) = 1/20, p(2) = 1/5, p(3) = 1/10, p(4) = 1/20, q(0) = 1/5, q(1) = 1/10, q(2) = 1/5, q(3) = 1/20, q(4) = 1/20.

Using r(i, j)s construct the optimal binary search tree.

पहचानकर्ता सेट {a₁, a₂, a₃, a₄} = (char, float, while, else) के लिए w(i, j), r(i, j) और c(i, j), 0 ≤ i ≤ j ≤ 4 की गणना करने के लिए फंक्शन OBST का उपयोग करें। p(1) = 1/20, p(2) = 1/5, p(3) = 1/10, p(4) = 1/20, q(0) = 1/5, q(1) = 1/10, q(2) = 1/5, q(3) = 1/20, q(4) = 1/20.

r(i, j) का उपयोग करके इ��्टतम बाइनरी सर्च ट्री का निर्माण करें।

b) Explain in detail about 2-3 Trees with an example.

2-3 ट्री के बारे में उदाहरण सहित विस्तार से समझाइये।

Write short notes on any two of the following:

a) Binary search algorithm and its time complexity

b) Single source shortest path algorithm

c) Parallel algorithms

d) NP Completeness

निम्नलिखित में से किन्हीं दो पर संक्षिप्त टिप्पणियाँ लिखिए।

अ) बाइनरी खोज एल्गोरिथम और इसकी समय जटिलता

ब) एकल स्रोत सबसे छोटा पथ एल्गोरिथम

स) समानांतर एल्गोरिथम

द) NP पूर्णता