Design And Analysis Of Algorithms

Course: B.Tech Code: 502 Branch: CY Date: December 2024

Save as PDF

Opens your browser print dialog — select "Save as PDF" to download.

Total No. of Questions: 8
Total No. of Printed Pages: 3
[2]
Roll No. .....................................

CY-502 (GS)

B.Tech., V Semester

Examination, December 2024

Grading System (GS)

Design And Analysis of Algorithms

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.

किसी भी प्रकार के संदेह अथवा विवाद की स्थिति में अंग्रेजी भाषा के प्रश्न को अंतिम माना जायेगा।

1.
a) Show that the average case time complexity of binary search is O(log n).

दिखाएँ कि बाइनरी सर्च की औसत केस टाइम काम्प्लेक्सिटी O(log n) है।

b) Define time Complexity. Describe different notations used to represent these complexities.

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

2.
a) Explain quick sort algorithm and sort the following list of number using quick sort algorithm. A = (6, 15, 3, 14, 25, 36, 18).

क्विक शार्ट एल्गोरिथम की व्याख्या करें और क्विक शार्ट एल्गोरिथम का उपयोग करके निम्नलिखित संख्याओं की सूची को शार्ट करें। A = (6, 15, 3, 14, 25, 36, 18)।

b) Write and solve recurrence relation for Strassen's matrix multiplication.

स्ट्रेसन के मैट्रिक्स गुणन के लिए पुनरावृत्ति संबंध लिखें और हल करें।

3.
a) Compute the optimal solution for knapsack problem using greedy method n = 4, m = 15, (p1,p2,p3,p4) = (10, 10, 12, 18), (w1,w2,w3,w4) = (2, 4, 6, 9).

ग्रेडी मेथड का उपयोग करके नैपसेक समस्या के लिए आप्टीमल सोल्यूशन लिखें। n = 4, m = 15, (p1,p2,p3,p4) = (10, 10, 12, 18), (w1,w2,w3,w4) = (2, 4, 6, 9)

b) Explain prism algorithm. Find its complexity.

प्रिज्म एल्गोरिथम को समझाइए। इसकी काम्प्लेक्सिटी क्या है।

4.
a) Describe in detail job sequencing with deadlines problem. Let n = 6, p = (200, 180, 190, 300, 120, 100), d = (5, 3, 3, 2, 4, 2). Find the optimal solution for the given values.

समय सीमा की समस्या के साथ कार्यक्रम का विस्तार से वर्णन करें। मान लीजिए n = 6, p = (200, 180, 190, 300, 120, 100), d = (5, 3, 3, 2, 4, 2) दिए गए मानों के लिए आप्टीमल समाधान खोजें।

b) Differentiate between dynamic programming and divide and conquer.

डिवाइड एंड कानकर एवं डायनामिक प्रोग्रामिंग के अंतर सुझाएं।

CY-502 (GS)
PTO
[3]
5.
a) What is multistage graph problem. Discuss its solution based on dynamic programming approach.

मल्टीस्टेज ग्राफ समस्या क्या है? डायनामिक प्रोग्रामिंग दृष्टिकोण के आधार पर इसके समाधान पर चर्चा करें।

b) Explain optimal merge (pattern) in brief.

संक्षेप में आप्टीमल मर्ज पैटर्न को समझाएं।

6.
a) Explain 8 queen problem and write an algorithm using backtracking to solve this problem.

8 क्वीन समस्या की व्याख्या करें एवं इस समस्या को हल करने के लिए बैक ट्रैकिंग का उपयोग करके एक एल्गोरिथम लिखें।

b) Explain the general method of branch and bound.

ब्रांच एंड बाउन्ड के लिए सामान्य मेथड की व्याख्या करें।

7.
a) Compare NP-hard and NP-completeness.

NP-हार्ड एवं NP-कम्प्लीटनेस में अंतर समझाए।

b) Design Horner's algorithm to evaluate a polynomial.

पालीनोमीयल को इवेल्यूट करने के लिए हार्नर एल्गोरिथम बनाइए।

8.
Write short notes on any two of the following:

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

a) Parallel Algorithm

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

b) Huffman Coding

ब) हफमैन कोडिंग

c) Space Complexity

स) स्पेस काम्प्लेक्सिटी

d) Traveling Sales Person Problem

द) ट्रेवलिंग सेल्स पर्सन प्राब्लम

CY-502 (GS)
end...