a) Define time complexity. Describe different notations used to represent time complexity.

समय जटिलता को परिभाषित कीजिए। समय जटिलता का प्रतिनिधित्व करने के लिए उपयोग किए जाने वाले विभिन्न नोटेशन का वर्णन करें।

b) Discuss Strassen's matrix multiplication as well as classical O (n³) one. Determine when Strassen's method outperforms the classical one.

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

a) Explain partition exchange sort algorithm and trace this algorithm for n = 8 elements: 24, 12, 35, 23, 45, 34, 20, 48.

पार्टीशन एक्सचेंज सॉर्ट एल्गोरिथम की व्याख्या करें और n = 8 तत्वों के लिए इस एल्गोरिथम को ट्रेस करें: 24, 12, 35, 23, 45, 34, 20, 48

b) State the Job - Sequencing with deadlines problem. Find an optimal sequence to the n = 5 jobs where profits (P₁, P₂, P₃, P₄, P₅) = (20, 15, 10, 5, 1) and deadlines (d₁, d₂, d₃, d₄, d₅) = (2, 1, 3, 3).

कार्य बताए। समय सीमा समस्या के साथ अनुकूल। n = 5 नौकरियों के लिए एक इष्टतम अनुक्रम खोजें जहाँ लाभ (P₁, P₂, P₃, P₄, P₅) = (20, 15, 10, 5, 1) और समय सीमा (d₁, d₂, d₃, d₄, d₅) = (2, 2, 1, 3, 3)

a) A thief enters a house for robbing. Thief can carry a maximum weight of 6kg into his bag. There are 3 items in the house with weights (w₁, w₂, w₃) = (2, 3, 4) and profits (P₁, P₂, P₃) = (1, 2, 5) what items should thief can take will get the maximum profit? He either takes or leaves the item.

एक चोर चोरी करने के लिए एक घर में प्रवेश करता है। चोर अपने बैग में अधिकतम 6 किलोग्राम वजन ले जा सकता है। घर में 3 वस्तुएँ हैं जिनका भार (w₁, w₂, w₃) = (2, 3, 4) तथा लाभ (P₁, P₂, P₃) = (1, 2, 5) है, चोर कौन-सी वस्तु ले जा सकता है जिससे अधिकतम लाभ मिलेगा? वह या तो आइटम लेता है या छोड़ देता है।

b) Explain Prim's and Kruskal's algorithm shown in figure with the following example.

निम्नलिखित उदाहरण के साथ चि���्र में दिखाए गए प्रिम और क्रुस्कल के एल्गोरिथम को समझाइए।

a) Solve the following instance of 0/1 Knapsack problem using Dynamic programming. n = 3; (W₁, W₂, W₃) = (3, 5, 7); (P₁, P₂, P₃) = (3, 7, 12); M = 4.

डायनामिक प्रोग्रामिंग का उपयोग करके 0/1 नैपसैक समस्या के निम्नलिखित उदाहरण को हल करें। n = 3; (W₁, W₂, W₃) = (3, 5, 7); (P₁, P₂, P₃) = (3, 7, 12); M = 4

b) Design a three stage system with device types D₁, D₂ and D₃. The costs are $30, $15 and $20 respectively. The Cost of the system is to be no more than $105. The reliability of each device is 0.9, 0.8 and 0.5 respectively.

डिवाइस प्रकार D₁, D₂ और D₃ के साथ एक तीन चरण प्रणाली डिज़ाइन करें। लागत क्रमशः $30, $15 और $20 है। सिस्टम की लागत $105 से अधिक नहीं होनी चाहिए। प्रत्येक डिवाइस की विश्वसनीयता क्रमशः 0.9, 0.8 और 0.5 है।

a) Discuss about Multistage graph problem. Also give a suitable algorithm and find its computing time.

मल्टीस्टेज ग्राफ प्रॉब्लम के बारे में चर्चा करें। एक उपयुक्त एल्गोरिथम भी दीजिए तथा इसका संगणन समय ज्ञात कीजिए।

b) Write an algorithm to determine the Hamiltonian cycle in a given graph using backtracking.

बैकट्रैकिंग का उपयोग करके दिए गए ग्राफ में हैमिल्टोनियन चक्र को निर्धारित करने के लिए एक एल्गोरिथम लिखें।

a) Solve the following instance of travelling sales person problem using Least Cost Branch Bound.

न्यूनतम लागत वाली शाखा बाउंड का उपयोग करते हुए ट्रैवलिंग सेल्स पर्सन की समस्या के निम्नलिखित उदाहरण को हल करें।

b) Construct state space tree for solving four queen's problem using backtracking.

बैकट्रैकिंग का उपयोग करके चार रानी की समस्या को हल करने के लिए स्टेट स्पेस ट्री का निर्माण करें।

a) Explain the P, NP-Hard and NP-complete classes? Give the relation between them.

P, NP-हार्ड और NP-पूर्ण वर्गों की व्याख्या करें। उनके बीच संबंध दें।

b) Show the inorder, preorder and postorder for the following tree

निम्नलिखित ट्री के लिए इनऑर्डर, प्रीऑर्डर और पोस्टऑर्डर दिखाएं।