डेटा संरचना और एल्गोरिदम: क्रैम पैक

सूत्र-पत्रक, हर विषय के मुख्य विधि-चरण और 6 अभ्यास प्रश्न, पूरे हल पीछे दिए गए हैं।

नए प्रश्नकोर्स पर वापस जाएँ

प्रिंट विंडो में “PDF के रूप में सहेजें” चुनें, ताकि एक प्रति आपके डिवाइस पर रहे।

1सूत्र और विधियाँ

ग्राफ़ सिद्धांत

हैंडशेक लेमा
Σ deg(v) = 2|E|
पूर्ण ग्राफ़
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
नियमित ग्राफ़
|E| = n·k/2
वृक्ष और वन
|E| = n − 1, |E| = n − c
वृक्ष के पत्ते
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
यूलर
परिपथ: सभी घात सम; पथ: ठीक 2 घात विषम
Kn में हैमिल्टन परिपथ
(n − 1)!/2
डाइक्स्ट्रा अद्यतन
d(v) = min(d(v), d(u) + w(u, v))
लंबाई L की वॉक
(Mᴸ)ij

विधि

  1. हर शीर्ष की घात लिखें; घातों का योग कोरों की संख्या का दोगुना होता है।
  2. यूलर के प्रश्नों में जाँचें कि ग्राफ़ संबद्ध है और विषम घात वाले शीर्षों को गिनें।
  3. वृक्षों के लिए n − 1 कोरों और हैंडशेक लेमा का उपयोग करें।
  4. डाइक्स्ट्रा के लिए अस्थायी दूरियों की सारणी रखें और हर चक्र में सबसे छोटी दूरी वाले अनिर्धारित शीर्ष को निर्धारित करें।
  5. न्यूनतम स्पैनिंग ट्री के लिए कोरों को भार के अनुसार क्रमबद्ध करें और चक्र बनाने वाली हर कोर छोड़ दें (क्रुस्कल), या किसी प्रारंभिक शीर्ष से एक वृक्ष बढ़ाएँ (प्रिम)।

2अभ्यास प्रश्न

1.एल्गोरिदम और जटिलतामध्यम

डायनेमिक प्रोग्रामिंग (dynamic programming) तब उपयोगी है जब किसी समस्या में हों:

  1. Aकेवल यादृच्छिक इनपुट
  2. Bकोई उप-समस्या बिल्कुल न हो, ताकि उसे एक ही चरण में हल किया जा सके
  3. Cकेवल एक लूप
  4. Dओवरलैपिंग उप-समस्याएँ और इष्टतम उप-संरचना (optimal substructure)
2.एल्गोरिदम और जटिलताकठिन

यह दिखाने के लिए कि कोई नई समस्या X NP-hard है, आपको क्या करना होगा?

  1. Aकिसी ज्ञात NP-hard समस्या को बहुपदी समय में X में रिड्यूस करना
  2. BX को बहुपदी समय में किसी ज्ञात NP-hard समस्या में रिड्यूस करना
  3. Cदिखाना कि छोटे इनपुट के लिए X का कोई बहुपदी एल्गोरिदम नहीं है
  4. Dदिखाना कि X बहुपदी समय में सत्यापित हो सकती है
3.डेटा संरचनाएँमध्यम

सर्कुलर बफ़र (रिंग बफ़र) का उपयोग आमतौर पर किसे लागू करने के लिए किया जाता है?

  1. Aबाइनरी सर्च ट्री
  2. Bनिश्चित आकार की क्यू
  3. Cग्राफ़ ट्रैवर्सल
  4. Dहैश फ़ंक्शन
4.डेटा संरचनाएँकठिन

कौन-सी डेटा संरचना O(1) get और put के साथ LRU (least recently used) कैश को सपोर्ट करती है?

  1. Aएक अकेला क्रमबद्ध ऐरे
  2. Bडबली लिंक्ड लिस्ट के साथ संयुक्त हैश मैप
  3. Cकेवल बाइनरी सर्च ट्री
  4. Dकेवल स्टैक
5.ग्राफ़ सिद्धांतमध्यम

एक वृक्ष में घात 3 वाले 2 शीर्ष, घात 4 वाले 4 शीर्ष, घात 2 वाले 2 शीर्ष है, और उसके बाकी सभी शीर्ष पत्ते (घात 1) हैं। उसमें कितने पत्ते L हैं?

2 × deg 34 × deg 42 × deg 2
L =
6.ग्राफ़ सिद्धांतकठिन
ABCDE

लंबाई 2 की कितनी बंद वॉक E से शुरू और समाप्त होती हैं? वॉक में शीर्ष और कोरें दोहराई जा सकती हैं। संख्या को N कहें।

M = संलग्नता आव्यूहL = 2
N =

3विलयन

1.एल्गोरिदम और जटिलता

उत्तर: D · ओवरलैपिंग उप-समस्याएँ और इष्टतम उप-संरचना (optimal substructure)

यह उत्तर क्यों है

ओवरलैपिंग उप-समस्याओं के परिणाम संग्रहीत करने (मेमोइज़ेशन या टैबुलेशन) से दोहराया गया काम बचता है, जिससे घातांकी एल्गोरिदम बहुपद एल्गोरिदम में बदल जाते हैं।

उत्तर

D · ओवरलैपिंग उप-समस्याएँ और इष्टतम उप-संरचना (optimal substructure)
2.एल्गोरिदम और जटिलता

उत्तर: A · किसी ज्ञात NP-hard समस्या को बहुपदी समय में X में रिड्यूस करना

यह उत्तर क्यों है

यदि किसी ज्ञात कठिन समस्या को कुशलता से X में बदला जा सके, तो X का तेज़ एल्गोरिदम ज्ञात समस्या को भी हल कर देगा।

उत्तर

A · किसी ज्ञात NP-hard समस्या को बहुपदी समय में X में रिड्यूस करना
3.डेटा संरचनाएँ

उत्तर: B · निश्चित आकार की क्यू

यह उत्तर क्यों है

रिंग बफ़र head और tail इंडेक्स का उपयोग करता है जो घूमकर वापस आते हैं, जिससे निश्चित मेमोरी में O(1) enqueue और dequeue मिलते हैं।

उत्तर

B · निश्चित आकार की क्यू
4.डेटा संरचनाएँ

उत्तर: B · डबली लिंक्ड लिस्ट के साथ संयुक्त हैश मैप

यह उत्तर क्यों है

हैश मैप नोड्स को O(1) में खोजता है और डबली लिंक्ड लिस्ट उपयोग किए गए तत्वों को आगे ले जाती है तथा पीछे से O(1) में हटाती है।

उत्तर

B · डबली लिंक्ड लिस्ट के साथ संयुक्त हैश मैप
5.ग्राफ़ सिद्धांत

उत्तर: L = 12

यूलर, हैमिल्टन और वृक्ष: संबद्ध ग्राफ़ में यूलर परिपथ (हर कोर एक बार, शुरुआत पर वापसी) तब होता है जब हर शीर्ष की घात सम हो, और परिपथ न होने वाला यूलर पथ तब जब ठीक दो शीर्षों की घात विषम हो; तब पथ एक विषम शीर्ष से दूसरे तक चलता है। हैमिल्टन परिपथ हर शीर्ष पर एक बार जाता है; Kn में ऐसे (n − 1)!/2 होते हैं। n शीर्षों वाले वृक्ष में n − 1 कोरें होती हैं, और m कोरों वाला संबद्ध ग्राफ़ m − n + 1 कोरें हटाने के बाद स्पैनिंग ट्री रखता है।

वृक्ष के लिए हैंडशेक लेमा

L + 26 = 2(L + 8) − 2
L = 12

उत्तर

L = 12

शॉर्टकट: L = 2 + Σ (d − 2), घात d ≥ 3 वाले शीर्षों पर।

6.ग्राफ़ सिद्धांत

उत्तर: N = 2

घात: किसी शीर्ष की घात उससे मिलने वाली कोरों की संख्या है। हर कोर के दो सिरे होते हैं, इसलिए घातों का योग कोरों की संख्या का दोगुना होता है: Σ deg(v) = 2|E| (हैंडशेक लेमा)। अतः विषम घात वाले शीर्षों की संख्या सम होती है। Kn में n(n − 1)/2 कोरें होती हैं, n शीर्षों पर k-नियमित ग्राफ़ में nk/2, और n शीर्षों वाले वृक्ष में n − 1 कोरें।

संलग्नता आव्यूह

A: 0 1 1 0 0
B: 1 0 1 1 1
C: 1 1 0 0 0
D: 0 1 0 0 1
E: 0 1 0 1 0

उभयनिष्ठ पड़ोसी

(M²)EE = 0·0 + 1·1 + 0·0 + 1·1 + 0·0 = 2

उत्तर

N = 2

ExamProblems · examproblems.com/courses/data-structures-and-algorithms