Analysis And Design Of Algorithm

a) With the help of a flow chart, explain the various steps of algorithm design and analysis process. 7

फ्लो चार्ट की सहायता से एल्गोरिथम डिजाइन और विश्लेषण प्रक्रिया के विभिन्न चरणों को समझाइए।

b) What are the significance of various asymptotic notations? Express the following assertions using three asymptotic notations with proof from its definition

i) n(n-1)/2

ii) 6*2ⁿ + n²

iii) 100n + 7

a) Write an algorithm to sort n numbers using Quick Sort. Trace the algorithm to sort the following list in an ascending order: 7

65 70 75 80 85 60 55 50

क्विक सॉर्ट का उपयोग करके n संख्याओं को सॉर्ट करने के लिए एक एल्गोरिथम लिखें। निम्नलिखित सूची को आरोही क्रम में क्रमबद्ध करने के लिए एल्गोरिथम को ट्रेस करें।

65 70 75 80 85 60 55 50

b) Discuss the General Divide and Conquer technique with control abstraction and recurrence relation. 7

नियंत्रण अमूर्तन और पुनरावृत्ति संबंध के साथ सामान्य Divide और Conquer तकनीक पर चर्चा करें।

a) Discuss how to find maximum and minimum element in an array recursively? Trace the same for the following data set 65, 70, 75, 80, 85, 60, 55, 50. Also derive the worst case complexity. 7

चर्चा करें कि किसी सरणी में अधिकतम और न्यूनतम तत्व क��� पुनरावर्ती का से कैसे खोजा जाए? निम्नलिखित डाटा सेट 65, 70, 75, 80, 85, 60, 55, 50 के लिए इसे ट्रेस करें। सबसे खराब स्थिति जटिलता भी प्राप्त करें।

b) Briefly explain the Strassen's matrix multiplication. Apply it to multiply the following matrices. Explain how this method is better than direct multiplication method. 7

स्ट्रैसेन के मैट्रिक्स गुणन को संक्षेप में समझाइए। निम्नलिखित मैट्रिक्स को गुणा करने के लिए इसे लागू करें। यह विधि प्रत्यक्ष गुणन विधि से किस प्रकार बेहतर है, समझाइए।

a) Recall the concept of greedy techniques. Find the optimal solution to the Knapsack instance n = 7, m = 15. 7

लालची तकनीकों की अवधारणा को प्रत्याह्वान करें। Knapsack उदाहरण n = 7, m = 15 के लिए इष्टतम समाधान निकालिए।

(P₁, P₂, ....... P₇) = (10, 5, 15, 7, 6, 18, 3)

(W₁, W₂, ....... W₇) = (2, 3, 5, 7, 1, 4, 1)

b) Using the Prim's Algorithm, determine the minimum cost spanning tree of the graph of figure: 7

प्राइम के एल्गोरिथम का उपयोग करते हुए, आकृति के ग्राफ की न्यूनतम लागत वाले हेटु पेड़ का निर्धारण करें।

a) Explain the dynamic programming. Generate transitive closure of the graph given in the figure give below: 7

डायनेमिक प्रोग्रामिंग को समझाइए। नीचे दिए गए चित्र में दिए गए ग्राफ का सकर्मक क्लोजर जनरेट करें।

b) Using Floyd's Algorithm, find all pairs of shortest path for the graph in the figure given below: 7

फ्लॉइड के एल्गोरिथम क��� उपयोग करते हुए, नीचे दिए गए चित्र में ग्राफ के लिए सबसे छोटे पथ के सभी जोड़े खोजें।

a) Explain Backtracking Concept. Construct the state-space tree for solving 4-Queen's problem using backtracking. 7

बैकट्रैकिंग कॉन्सेप्ट को समझाइए। बैकट्रैकिंग का उपयोग करके 4-Queen की समस्या को हल करने के लिए राज्य-अंतरिक्ष वृक्ष का निर्माण करें।

b) What is Branch and Bound algorithm? Write the steps and apply nearest neighbour approximation algorithm on the Travelling Salesperson Problem with the starting vertex a. and calculate the accuracy ratio of approximation. 7

ब्रांच और बाउंड एल्गोरिथम क्या है? चरणों को लिखें और शुरुआती शीर्ष 'a' के साथ यात्रा विक्रेता समस्या पर निकटतम पड़ोसी सन्निकटन एल्गोरिथम लागू करें, और अनुमान के सटीकता अनुपात की गणना करें।

a) What is a Decision Tree? Give a decision tree for 3 elements selection sort for arranging the items in ascending order and estimate its lower bound. 7

डिसीजन ट्री क्या है? वस्तुओं को आरोही क्रम में व्यवस्थित करने के लिए 3 तत्वों के चयन प्रकार के लिए एक निर्णय वृक्ष दें और इसकी निचली सीमा का अनुमान लगाएं।

b) Apply DFS algorithm to solve the topological sorting problem for the graph in the figure given below: 7

नीचे दिए गए ग्राफ में ग्राफ के लिए टोपोलॉजिकल सॉर्टिंग समस्या को हल करने के लिए DFS एल्गोरिथम लागू करें।