GKPAD.COM

ONLINE HINDI EDUCATION PORTAL

IGNOU MCS-211 Solved Question Paper PDF Download

The IGNOU MCS-211 Solved Question Paper PDF Download page is designed to help students access high-quality exam resources in one place. Here, you can find ignou solved question paper IGNOU Previous Year Question paper solved PDF that covers all important questions with detailed answers. This page provides IGNOU all Previous year Question Papers in one PDF format, making it easier for students to prepare effectively.

Whether you are looking for IGNOU Previous Year Question paper solved in English or ignou previous year question paper solved in hindi, this page offers both options to suit your learning needs. These solved papers help you understand exam patterns, improve answer writing skills, and boost confidence for upcoming exams.

IGNOU MCS-211 Solved Question Paper PDF

IGNOU Previous Year Solved Question Papers

This section provides IGNOU MCS-211 Solved Question Paper PDF in both Hindi and English. These ignou solved question paper IGNOU Previous Year Question paper solved PDF include detailed answers to help you understand exam patterns and improve your preparation. You can also access IGNOU all Previous year Question Papers in one PDF for quick and effective revision before exams.

IGNOU MCS-211 Previous Year Solved Question Paper in Hindi

Q1. (a) निम्नलिखित ऐरे एलीमेंट्स को सॉर्ट करने के लिए मर्ज सॉर्ट एल्गोरिथ्म लागू करें : 5 4, 6, 2, 3, 8, 5, 7, 1 (b) एक उदाहरण की सहायता से बहुपद मूल्यांकन की हॉर्नर की विधि की व्याख्या करें। इस विधि की टाइम कॉम्प्लेक्सिटी क्या है ? 5 (c) निम्नलिखित डेटा के लिए हफमैन ट्री का निर्माण करें : 5 कैरेक्टर फ्रीक्वेंसी a 70 b 2 c 5 d 3 e 3 f 7 (d) तीन कीज 0 50 90 से मिलकर बनने वाले सभी संभावित बाइनरी सर्च ट्री बनाएं। 5 (e) निम्नलिखित ग्राफ पर विचार करें : 5 @ (B) (c) इस ग्राफ को एडजेसेंसी लिस्ट का उपयोग करके प्रस्तुत करें। (f) मिनिमम स्पैनिंग ट्री (MST) निर्माण के लिए क्रुस्कल के एल्गोरिथ्म की व्याख्या करें। 5 (g) बूलियन सैटिसफाइअबिलिटी (SAT) समस्या क्या है ? विस्तार से बताएं। 5 (h) ‘a’ को शुरुआती नोड के रूप में उपयोग करके निम्नलिखित ग्राफ को ब्रेथ फर्स्ट सर्च (BFS) का उपयोग करके ट्रैवर्स करें : 5 | () ee a

Ans. (a) मर्ज सॉर्ट एल्गोरिथ्म:

मर्ज सॉर्ट एक डिवाइड और कॉन्कर एल्गोरिथ्म है। यह इनपुट ऐरे को दो हिस्सों में विभाजित करता है, दोनों हिस्सों को रिकर्सिव रूप से सॉर्ट करता है, और फिर दो सॉर्ट किए गए हिस्सों को मर्ज करता है।

दिया गया ऐरे: [4, 6, 2, 3, 8, 5, 7, 1]

  1. विभाजन (Divide):
    • [4, 6, 2, 3] और [8, 5, 7, 1]
    • [4, 6], [2, 3] और [8, 5], [7, 1]
    • [4], [6] | [2], [3] | [8], [5] | [7], [1]
  2. मर्ज और सॉर्ट (Merge and Sort):
    • [4] और [6] को मर्ज करें -> [4, 6]
    • [2] और [3] को मर्ज करें -> [2, 3]
    • [8] और [5] को मर्ज करें -> [5, 8]
    • [7] और [1] को मर्ज करें -> [1, 7]
  3. आगे मर्ज करें:
    • [4, 6] और [2, 3] को मर्ज करें -> [2, 3, 4, 6]
    • [5, 8] और [1, 7] को मर्ज करें -> [1, 5, 7, 8]
  4. अंतिम मर्ज:
    • [2, 3, 4, 6] और [1, 5, 7, 8] को मर्ज करें -> [1, 2, 3, 4, 5, 6, 7, 8]

अंतिम सॉर्ट किया गया ऐरे है: 1, 2, 3, 4, 5, 6, 7, 8 ।

(b) हॉर्नर की विधि (Horner’s Method):

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

एक बहुपद P(x) = a n x n + a n-1 x n-1 + … + a 1 x + a 0 को इस प्रकार लिखा जा सकता है:

P(x) = a 0 + x(a 1 + x(a 2 + … + x(a n-1 + x * a n )…))

उदाहरण: P(x) = 2x 3 – 6x 2 + 2x – 1 का x = 3 पर मूल्यांकन करें।

गुणांक हैं: a 3 =2, a 2 =-6, a 1 =2, a 0 =-1.

हॉर्नर के रूप में: P(x) = -1 + x(2 + x(-6 + x(2)))

गणना चरण-दर-चरण:

  1. प्रारंभिक परिणाम = a 3 = 2
  2. अगला परिणाम = a 2 + (पिछला परिणाम × x) = -6 + (2 × 3) = 0
  3. अगला परिणाम = a 1 + (पिछला परिणाम × x) = 2 + (0 × 3) = 2
  4. अंतिम परिणाम = a 0 + (पिछला परिणाम × x) = -1 + (2 × 3) = 5

तो, P(3) = 5।

टाइम कॉम्प्लेक्सिटी: इस विधि में n डिग्री के बहुपद के लिए केवल n गुणन और n जोड़ की आवश्यकता होती है। इसलिए, इसकी टाइम कॉम्प्लेक्सिटी O(n) है, जो सीधे मूल्यांकन (जिसमें O(n 2 ) गुणन लगते हैं) की तुलना में बहुत बेहतर है।

(c) हफमैन ट्री निर्माण:

हफमैन कोडिंग एक दोषरहित डेटा संपीड़न एल्गोरिथ्म है। यह एक ग्रीडी दृष्टिकोण का उपयोग करता है, जिसमें सबसे कम फ्रीक्वेंसी वाले दो नोड्स को बार-बार मिलाकर एक ट्री बनाया जाता है।

दिए गए कैरेक्टर और फ्रीक्वेंसी:

a: 70, b: 2, c: 5, d: 3, e: 3, f: 7

चरण:

  1. सबसे कम फ्रीक्वेंसी वाले दो नोड्स चुनें: ‘b’ (2) और ‘d’ (3)। इन्हें एक नए आंतरिक नोड (N1) के तहत मिलाएं जिसकी फ्रीक्वेंसी 2+3=5 हो।
  2. अब फ्रीक्वेंसी हैं: e(3), N1(5), c(5), f(7), a(70)। ‘e’ (3) और N1 (5) चुनें। इन्हें एक नए आंतरिक नोड (N2) के तहत मिलाएं जिसकी फ्रीक्वेंसी 3+5=8 हो।
  3. अब फ्रीक्वेंसी हैं: c(5), f(7), N2(8), a(70)। ‘c’ (5) और ‘f’ (7) चुनें। इन्हें एक नए आंतरिक नोड (N3) के तहत मिलाएं जिसकी फ्रीक्वेंसी 5+7=12 हो।
  4. अब फ्रीक्वेंसी हैं: N2(8), N3(12), a(70)। N2 (8) और N3 (12) चुनें। इन्हें एक नए आंतरिक नोड (N4) के तहत मिलाएं जिसकी फ्रीक्वेंसी 8+12=20 हो।
  5. अब फ्रीक्वेंसी हैं: N4(20), a(70)। N4 (20) और ‘a’ (70) चुनें। इन्हें रूट नोड (N5) के तहत मिलाएं जिसकी फ्रीक्वेंसी 20+70=90 हो।

अंतिम ट्री और कोड (बाएं किनारे के लिए 0, दाएं किनारे के लिए 1 का उपयोग करके):

  • a: 1
  • f: 011
  • c: 010
  • e: 001
  • d: 0001
  • b: 0000

(d) तीन कीज (0, 50, 90) के लिए संभावित बाइनरी सर्च ट्री (BST):

BST की प्रॉपर्टी यह है कि किसी भी नोड के लिए, उसके बाएं सबट्री के सभी मान नोड के मान से कम होते हैं, और उसके दाएं सबट्री के सभी मान नोड के मान से अधिक होते हैं। तीन अलग-अलग कीज के लिए, 5 संभावित BST हैं (कैटलन संख्या C(3) = 5)।

कीज: {0, 50, 90}

संभावित ट्री:

  1. रूट 50 है: 
     50 / \ 0 90
  2. रूट 0 है: 
     0 \ 50 \ 90
  3. रूट 90 है: 
     90 / 50 / 0
  4. रूट 0 है (अलग संरचना): 
     0 \ 90 / 50
  5. रूट 90 है (अलग संरचना): 
     90 / 0 \ 50

(e) एडजेसेंसी लिस्ट का उपयोग करके ग्राफ का प्रतिनिधित्व:

दिए गए ग्राफ में तीन नोड हैं: A, B, C। इसमें A और B के बीच एक किनारा है, और A और C के बीच एक किनारा है।

एक एडजेसेंसी लिस्ट प्रत्येक वर्टेक्स के लिए उसके आसन्न वर्टेक्स की एक सूची बनाए रखती है।

इस ग्राफ के लिए एडजेसेंसी लिस्ट इस प्रकार होगी:

  • A: -> [ B, C ]
  • B: -> [ A ]
  • C: -> [ A ]

यह प्रतिनिधित्व मेमोरी कुशल होता है, विशेष रूप से स्पार्स ग्राफ (कम किनारों वाले ग्राफ) के लिए।

(f) क्रुस्कल का एल्गोरिथ्म:

क्रुस्कल का एल्गोरिथ्म एक दिए गए, जुड़े हुए, भारित और अप्रत्यक्ष ग्राफ में मिनिमम स्पैनिंग ट्री (MST) खोजने के लिए एक ग्रीडी एल्गोरिथ्म है। एक MST एक सबग्राफ है जो सभी वर्टिस को जोड़ता है, जिसमें कोई साइकिल नहीं होती है और किनारों का कुल भार न्यूनतम होता है।

एल्गोरिथ्म के चरण:

  1. ग्राफ के सभी किनारों को उनके भार के अनुसार गैर-घटते क्रम (non-decreasing order) में सॉर्ट करें।
  2. एक खाली सेट MST बनाएं।
  3. सॉर्ट किए गए किनारों के माध्यम से पुनरावृति करें। प्रत्येक किनारे (u, v) के लिए:
  4. यदि MST में किनारे (u, v) को जोड़ने से साइकिल नहीं बनती है, तो इसे MST में जोड़ें।
  5. यदि यह एक साइकिल बनाता है, तो इसे छोड़ दें।
  6. यह प्रक्रिया तब तक जारी रखें जब तक MST में V-1 किनारे न हो जाएं (जहाँ V वर्टिस की संख्या है)।

साइकिल का पता लगाने के लिए, आमतौर पर डिसजॉइंट सेट यूनियन (DSU) डेटा स्ट्रक्चर का उपयोग किया जाता है।

(g) बूलियन सैटिसफाइअबिलिटी (SAT) समस्या:

बूलियन सैटिसफाइअबिलिटी (SAT) समस्या यह निर्धारित करने की समस्या है कि क्या किसी दिए गए बूलियन सूत्र (Boolean formula) को संतुष्ट करने वाला कोई वैरिएबल असाइनमेंट मौजूद है। दूसरे शब्दों में, क्या हम बूलियन वेरिएबल्स को TRUE या FALSE मान इस तरह से असाइन कर सकते हैं कि पूरा सूत्र TRUE हो जाए।

विस्तृत व्याख्या:

  • बूलियन सूत्र: यह बूलियन वेरिएबल्स (जो TRUE या FALSE हो सकते हैं) और ऑपरेटरों (जैसे AND (∧), OR (∨), NOT (¬)) से बना एक व्यंजक है।
  • संतुष्टि: एक सूत्र “संतुष्टि योग्य” (satisfiable) होता है, यदि उसके वेरिएबल्स के लिए मानों का कम से कम एक सेट मौजूद हो जो सूत्र को TRUE बनाता है। यदि ऐसा कोई असाइनमेंट मौजूद नहीं है, तो सूत्र “असंतुष्टि योग्य” (unsatisfiable) होता है।
  • उदाहरण:
    • सूत्र: F = (x ∨ y) ∧ (¬x ∨ z)
    • यह सूत्र satisfiable है। उदाहरण के लिए, यदि हम x = TRUE, y = FALSE, और z = TRUE सेट करते हैं, तो F = (TRUE ∨ FALSE) ∧ (¬TRUE ∨ TRUE) = TRUE ∧ TRUE = TRUE।
    • सूत्र: G = (a ∧ ¬a) असंतुष्टि योग्य है, क्योंकि ‘a’ के किसी भी मान के लिए यह हमेशा FALSE होगा।
  • महत्व: SAT समस्या पहली समस्या थी जिसे NP-कम्प्लीट साबित किया गया था (कुक-लेविन प्रमेय)। इसका मतलब है कि यह NP क्लास की सबसे कठिन समस्याओं में से एक है। कई अन्य कठिन समस्याओं (जैसे शेड्यूलिंग, सर्किट डिजाइन) को SAT में घटाया जा सकता है।

(h) ब्रेथ फर्स्ट सर्च (BFS) ट्रैवर्सल:

BFS एक ग्राफ ट्रैवर्सल एल्गोरिथ्म है जो एक स्रोत नोड से शुरू होता है और पड़ोसी नोड्स का पता लगाता है, फिर उन पड़ोसियों के पड़ोसियों का, और इसी तरह, स्तर-दर-स्तर। यह एक क्यू (Queue) डेटा स्ट्रक्चर का उपयोग करता है।

दिए गए ग्राफ (a–b, a–c, a–d, b–e, c–f) और शुरुआती नोड ‘a’ के लिए:

  1. एक खाली क्यू (Q) और एक खाली विज़िटेड सेट (V) प्रारंभ करें। ‘a’ को Q में डालें और V में चिह्नित करें। Q: [a], V: {a}
  2. ‘a’ को डीक्यू करें, इसे ट्रैवर्सल में जोड़ें। ‘a’ के सभी अन-विज़िटेड पड़ोसियों (b, c, d) को एनक्यू करें और उन्हें V में चिह्नित करें। ट्रैवर्सल: a Q: [b, c, d], V: {a, b, c, d}
  3. ‘b’ को डीक्यू करें, इसे ट्रैवर्सल में जोड़ें। ‘b’ के अन-विज़िटेड पड़ोसी (‘e’) को एनक्यू करें और V में चिह्नित करें। ट्रैवर्सल: a, b Q: [c, d, e], V: {a, b, c, d, e}
  4. ‘c’ को डीक्यू करें, इसे ट्रैवर्सल में जोड़ें। ‘c’ के अन-विज़िटेड पड़ोसी (‘f’) को एनक्यू करें और V में चिह्नित करें। ट्रैवर्सल: a, b, c Q: [d, e, f], V: {a, b, c, d, e, f}
  5. ‘d’ को डीक्यू करें, इसे ट्रैवर्सल में जोड़ें। ‘d’ का कोई अन-विज़िटेड पड़ोसी नहीं है। ट्रैवर्सल: a, b, c, d Q: [e, f]
  6. ‘e’ को डीक्यू करें, इसे ट्रैवर्सल में जोड़ें। कोई अन-विज़िटेड पड़ोसी नहीं है। ट्रैवर्सल: a, b, c, d, e Q: [f]
  7. ‘f’ को डीक्यू करें, इसे ट्रैवर्सल में जोड़ें। कोई अन-विज़िटेड पड़ोसी नहीं है। ट्रैवर्सल: a, b, c, d, e, f Q: []

क्यू अब खाली है, इसलिए ट्रैवर्सल पूरा हो गया है।

अंतिम BFS ट्रैवर्सल क्रम: a, b, c, d, e, f ।

Q2. (a) इष्टतमता के सिद्धांत (principle of optimality) को लिखें। बताएं कि डायनामिक प्रोग्रामिंग का उपयोग चेन मैट्रिक्स मल्टीप्लिकेशन समस्या को हल करने के लिए कैसे किया जा सकता है। 10 (b) एक फ्रैक्शनल नैपसैक समस्या को एक ऑप्टिमाइज़ेशन समस्या के रूप में परिभाषित करें। समस्या का एक इष्टतम समाधान खोजने के लिए एक ग्रीडी विधि लिखें। एल्गोरिथ्म की कॉम्प्लेक्सिटी ज्ञात करें। 10

Ans. (a) इष्टतमता का सिद्धांत और चेन मैट्रिक्स मल्टीप्लिकेशन

इष्टतमता का सिद्धांत (Principle of Optimality):

इष्टतमता का सिद्धांत डायनामिक प्रोग्रामिंग का आधार है। यह कहता है कि “एक इष्टतम नीति में यह गुण होता है कि प्रारंभिक अवस्था और प्रारंभिक निर्णय के परिणामस्वरूप होने वाली अवस्था के संबंध में, शेष निर्णय एक इष्टतम नीति का गठन करते हैं।”

सरल शब्दों में, इसका मतलब है कि किसी समस्या का इष्टतम समाधान उसकी उप-समस्याओं (sub-problems) के इष्टतम समाधानों से बना होता है। यदि हम एक बड़ी समस्या को छोटी-छोटी ओवरलैपिंग उप-समस्याओं में तोड़ सकते हैं, और इन उप-समस्याओं के इष्टतम समाधान बड़ी समस्या के इष्टतम समाधान में योगदान करते हैं, तो हम डायनामिक प्रोग्रामिंग का उपयोग कर सकते हैं।

चेन मैट्रिक्स मल्टीप्लिकेशन (Chain Matrix Multiplication – MCM) में डायनामिक प्रोग्रामिंग का उपयोग:

MCM समस्या मैट्रिसेस की एक श्रृंखला (जैसे A 1 , A 2 , …, A n ) का गुणन करने के लिए सबसे कुशल पैरेन्थेसाइज़ेशन (parenthesization) खोजने की है। लक्ष्य स्केलर गुणन की कुल संख्या को कम करना है।

मान लीजिए हमारे पास A i …A j श्रृंखला है। इस श्रृंखला के गुणन का अंतिम चरण एक विभाजन बिंदु k पर होगा, जहाँ i ≤ k < j, और हम (A i …A k ) और (A k+1 …A j ) के परिणामों को गुणा करेंगे।

यहां इष्टतमता का सिद्धांत लागू होता है: A i …A j के गुणन का कुल इष्टतम खर्च केवल तभी प्राप्त किया जा सकता है जब उप-श्रृंखला (A i …A k ) और (A k+1 …A j ) का गुणन भी इष्टतम रूप से किया गया हो।

डायनामिक प्रोग्रामिंग दृष्टिकोण:

  1. संरचना की पहचान करें: हम उप-समस्याओं को m[i, j] के रूप में परिभाषित करते हैं, जो मैट्रिक्स A i से A j तक गुणा करने के लिए आवश्यक न्यूनतम स्केलर गुणन की संख्या है।
  2. रिकर्सिव समाधान: हम m[i, j] के लिए एक रिकर्सिव सूत्र बनाते हैं।
    • यदि i = j, तो m[i, j] = 0 (एकल मैट्रिक्स के लिए कोई गुणन नहीं)।
    • यदि i < j, तो m[i, j] = min i≤k { m[i, k] + m[k+1, j] + p i-1 p k p j } जहाँ p i-1 , p k , और p j मैट्रिक्स A i , A k , और A j के आयाम हैं (A i का आकार p i-1 x p i है)।
  3. बॉटम-अप गणना: सादे रिकर्सन के बजाय, जो बार-बार उन्हीं उप-समस्याओं को हल करता है, डायनामिक प्रोग्रामिंग इन परिणामों को एक तालिका (table) में संग्रहीत करता है। यह छोटी श्रृंखलाओं (कम लंबाई) से शुरू होता है और बड़ी श्रृंखलाओं तक जाता है, प्रत्येक उप-समस्या के समाधान को फिर से उपयोग करता है। यह ओवरलैपिंग उप-समस्याओं की संपत्ति का लाभ उठाता है।

इस प्रकार, डायनामिक प्रोग्रामिंग तालिका भरकर और रिकर्सिव सूत्र को बॉटम-अप तरीके से लागू करके MCM समस्या को O(n 3 ) समय में कुशलतापूर्वक हल करता है।

(b) फ्रैक्शनल नैपसैक समस्या

परिभाषा:

फ्रैक्शनल नैपसैक समस्या एक ऑप्टिमाइज़ेशन समस्या है। इसमें, हमें n आइटम्स का एक सेट दिया जाता है, प्रत्येक का अपना भार (w i ) और मान (v i ) होता है। हमारे पास एक नैपसैक (बोरी) है जिसकी अधिकतम वजन क्षमता W है। लक्ष्य उन आइटम्स (या उनके अंशों) को चुनना है जिन्हें नैपसैक में रखा जा सके ताकि नैपसैक में आइटम्स का कुल मान अधिकतम हो, जबकि कुल भार क्षमता W से अधिक न हो। फ्रैक्शनल संस्करण में, हम किसी आइटम का एक अंश (fraction) ले सकते हैं।

ऑप्टिमाइज़ेशन समस्या के रूप में:

  • इनपुट: n आइटम्स का सेट {1, …, n}, प्रत्येक का भार w i > 0 और मान v i > 0, और नैपसैक क्षमता W > 0।
  • आउटपुट: प्रत्येक आइटम के लिए मात्रा x i (जहाँ 0 ≤ x i ≤ 1), जैसे कि:
    • बाधा (Constraint): Σ (x i * w i ) ≤ W (कुल भार क्षमता से अधिक नहीं होना चाहिए)
    • उद्देश्य (Objective): Σ (x i * v i ) को अधिकतम करना (कुल मान को अधिकतम करना)

ग्रीडी विधि से इष्टतम समाधान:

फ्रैक्शनल नैपसैक समस्या को एक ग्रीडी एल्गोरिथ्म का उपयोग करके इष्टतम रूप से हल किया जा सकता है। ग्रीडी रणनीति उच्चतम मान-प्रति-भार अनुपात (value-per-weight ratio) वाले आइटम्स को प्राथमिकता देना है।

एल्गोरिथ्म:

  1. प्रत्येक आइटम i के लिए, मान-प्रति-भार अनुपात (v i / w i ) की गणना करें।
  2. सभी आइटम्स को उनके अनुपात के घटते क्रम में सॉर्ट करें।
  3. एक खाली नैपसैक से शुरू करें (कुल मान = 0, वर्तमान भार = 0)।
  4. सॉर्ट किए गए आइटम्स की सूची के माध्यम से पुनरावृति करें:
    1. वर्तमान आइटम i के लिए, यदि उसका पूरा भार (w i ) नैपसैक की शेष क्षमता में फिट हो सकता है (यानी, w i ≤ W – वर्तमान भार), तो:
      • आइटम का पूरा हिस्सा लें (x i = 1)।
      • नैपसैक के कुल मान और वर्तमान भार को अपडेट करें।
    2. यदि आइटम पूरी तरह से फिट नहीं हो सकता है, तो:
      • आइटम का एक अंश लें जो शेष क्षमता को भर दे। अंश = (W – वर्तमान भार) / w i ।
      • इस अंश को नैपसैक में जोड़ें।
      • नैपसैक अब भरा हुआ है, इसलिए एल्गोरिथ्म को रोक दें।
  5. नैपसैक में कुल मान लौटाएं।

कॉम्प्लेक्सिटी:

  • अनुपात की गणना करने में O(n) समय लगता है।
  • आइटम्स को उनके अनुपात के आधार पर सॉर्ट करने में O(n log n) समय लगता है।
  • सॉर्ट की गई सूची के माध्यम से पुनरावृति करने में O(n) समय लगता है।

इसलिए, एल्गोरिथ्म की कुल टाइम कॉम्प्लेक्सिटी O(n log n) है, जो सॉर्टिंग चरण द्वारा निर्धारित होती है।

Q3. (a) डाइज्क्स्ट्रा का एल्गोरिथ्म लिखें और इसका उपयोग निम्नलिखित ग्राफ के लिए नोड ‘a’ जो स्रोत नोड के रूप में लिया गया है, से सभी नोड्स की न्यूनतम दूरी खोजने के लिए करें: 10 यू 7 © (7) ह 2 © © (b) क्विक सॉर्ट एल्गोरिथ्म लिखें। इस एल्गोरिथ्म की वर्स्ट केस कॉम्प्लेक्सिटी भी ज्ञात करें। निम्नलिखित सूची को सॉर्ट करने के लिए इस एल्गोरिथ्म का उपयोग करें : 10 20, 5, 5, 8, 6, 28

Ans. (a) डाइज्क्स्ट्रा का एल्गोरिथ्म और इसका अनुप्रयोग

डाइज्क्स्ट्रा का एल्गोरिथ्म:

डाइज्क्स्ट्रा का एल्गोरिथ्म एक ग्राफ में एकल-स्रोत से सबसे छोटे पथ (single-source shortest path) की समस्या का समाधान करता है, जिसमें किनारों का भार गैर-ऋणात्मक (non-negative) होता है। यह एक ग्रीडी एल्गोरिथ्म है जो स्रोत से सभी अन्य वर्टिस तक सबसे छोटी दूरी का पता लगाता है।

एल्गोरिथ्म:

  1. एक दूरी ऐरे `dist[]` बनाएं और स्रोत वर्टेक्स की दूरी 0 और अन्य सभी वर्टिस की दूरी अनंत (infinity) पर सेट करें।
  2. एक प्राथमिकता क्यू (priority queue) बनाएं जिसमें सभी वर्टिस हों। प्राथमिकता दूरी मान पर आधारित होती है।
  3. जब तक प्राथमिकता क्यू खाली न हो जाए:
    1. क्यू से सबसे छोटी दूरी वाले वर्टेक्स `u` को निकालें।
    2. `u` के प्रत्येक पड़ोसी `v` के लिए:
      • यदि `dist[u] + weight(u, v) < dist[v]`, तो `dist[v]` को अपडेट करें।
      • यह प्रक्रिया “रिलैक्सेशन” कहलाती है।
  4. एल्गोरिथ्म समाप्त होने पर, `dist[]` ऐरे में स्रोत से सभी वर्टिस की सबसे छोटी दूरी होती है।

दिए गए ग्राफ पर अनुप्रयोग:

ग्राफ के किनारे और भार: a-b(3), a-d(7), b-c(7), b-d(2), d-e(2)। स्रोत नोड: ‘a’।

प्रारंभिक स्थिति:

  • dist = {a: 0, b: ∞, c: ∞, d: ∞, e: ∞}
  • प्राथमिकता क्यू (PQ) = [(0, a)]

चरण-दर-चरण निष्पादन:

  1. पुनरावृत्ति 1:
    • PQ से (0, a) निकालें। नोड ‘a’ को विज़िट करें।
    • ‘a’ के पड़ोसी: ‘b’ और ‘d’।
    • रिलैक्स b: dist[b] = min(∞, 0+3) = 3। PQ में (3, b) डालें।
    • रिलैक्स d: dist[d] = min(∞, 0+7) = 7। PQ में (7, d) डालें।
    • dist = {a: 0, b: 3, c: ∞, d: 7, e: ∞}, PQ = [(3, b), (7, d)]
  2. पुनरावृत्ति 2:
    • PQ से सबसे छोटी दूरी वाला नोड (3, b) निकालें।
    • ‘b’ के पड़ोसी: ‘c’ और ‘d’।
    • रिलैक्स c: dist[c] = min(∞, 3+7) = 10। PQ में (10, c) डालें।
    • रिलैक्स d: dist[d] = min(7, 3+2) = 5। PQ में ‘d’ की दूरी अपडेट करें।
    • dist = {a: 0, b: 3, c: 10, d: 5, e: ∞}, PQ = [(5, d), (10, c)]
  3. पुनरावृत्ति 3:
    • PQ से (5, d) निकालें।
    • ‘d’ का पड़ोसी: ‘e’।
    • रिलैक्स e: dist[e] = min(∞, 5+2) = 7। PQ में (7, e) डालें।
    • dist = {a: 0, b: 3, c: 10, d: 5, e: 7}, PQ = [(7, e), (10, c)]
  4. पुनरावृत्ति 4:
    • PQ से (7, e) निकालें। ‘e’ का कोई अन-विज़िटेड पड़ोसी नहीं है।
  5. पुनरावृत्ति 5:
    • PQ से (10, c) निकालें। ‘c’ का कोई अन-विज़िटED पड़ोसी नहीं है।

PQ अब खाली है। स्रोत ‘a’ से न्यूनतम दूरियां हैं:

  • a: 0
  • b: 3
  • c: 10
  • d: 5
  • e: 7

(b) क्विक सॉर्ट एल्गोरिथ्म

एल्गोरिथ्म:

क्विक सॉर्ट एक कुशल, इन-प्लेस, डिवाइड और कॉन्कर सॉर्टिंग एल्गोरिथ्म है।

  1. डिवाइड (Divide): ऐरे से एक एलीमेंट को पिवट (pivot) के रूप में चुनें। ऐरे को दो सब-ऐरे में पुनर्व्यवस्थित (partition) करें: एक में पिवट से छोटे या बराबर एलीमेंट और दूसरे में पिवट से बड़े एलीमेंट।
  2. कॉन्कर (Conquer): दो सब-ऐरे पर रिकर्सिव रूप से क्विक सॉर्ट लागू करें।
  3. कंबाइन (Combine): कुछ भी करने की आवश्यकता नहीं है, क्योंकि सॉर्टिंग इन-प्लेस होती है।

सूडोकोड:

QUICKSORT(A, low, high) if low < high p = PARTITION(A, low, high) QUICKSORT(A, low, p – 1) QUICKSORT(A, p + 1, high) PARTITION(A, low, high) pivot = A[high] i = low – 1 for j = low to high – 1 if A[j] <= pivot i = i + 1 swap A[i] and A[j] swap A[i + 1] and A[high] return i + 1

वर्स्ट केस कॉम्प्लेक्सिटी:

क्विक सॉर्ट की वर्स्ट केस कॉम्प्लेक्सिटी O(n 2 ) है। यह तब होता है जब पिवट चयन हमेशा ऐरे का सबसे छोटा या सबसे बड़ा एलीमेंट होता है। इस मामले में, पार्टिशनिंग प्रक्रिया एक सब-ऐरे को 0 एलीमेंट्स के साथ और दूसरे को n-1 एलीमेंट्स के साथ बनाती है, जिससे एक असंतुलित विभाजन होता है। यह अक्सर तब होता है जब इनपुट ऐरे पहले से ही सॉर्ट किया हुआ या रिवर्स-सॉर्ट किया हुआ होता है।

दी गई सूची पर अनुप्रयोग: [20, 5, 5, 8, 6, 28]

हम अंतिम एलीमेंट को पिवट के रूप में उपयोग करेंगे।

  1. प्रारंभिक कॉल: `QUICKSORT([20, 5, 5, 8, 6, 28], 0, 5)`
    • पिवट = 28। पार्टिशनिंग के बाद, ऐरे अपरिवर्तित रहता है क्योंकि सभी एलीमेंट 28 से छोटे हैं। पिवट अपनी सही जगह पर है।
    • पार्टिशन इंडेक्स 5 पर है। `QUICKSORT([20, 5, 5, 8, 6], 0, 4)` पर रिकर्सिव कॉल।
  2. कॉल: `QUICKSORT([20, 5, 5, 8, 6], 0, 4)`
    • पिवट = 6। पार्टिशनिंग: 6 से छोटे या बराबर एलीमेंट बाईं ओर जाते हैं।
    • ऐरे बनता है: `[5, 5, 6, 8, 20]` (सब-ऐरे के भीतर)। पिवट (6) का नया इंडेक्स 2 है।
    • रिकर्सिव कॉल्स: `QUICKSORT([5, 5], 0, 1)` और `QUICKSORT([8, 20], 3, 4)`।
  3. कॉल: `QUICKSORT([5, 5], 0, 1)`
    • पिवट = 5। पार्टिशनिंग के बाद: `[5, 5]`।
    • आगे कोई रिकर्सिव कॉल नहीं क्योंकि सब-ऐरे सॉर्ट हो गए हैं।
  4. कॉल: `QUICKSORT([8, 20], 3, 4)`
    • पिवट = 20। पार्टिशनिंग के बाद: `[8, 20]`।
    • आगे कोई रिकर्सिव कॉल नहीं।

सभी रिकर्सिव कॉल्स के संयोजन के बाद, अंतिम सॉर्ट की गई सूची है: 5, 5, 6, 8, 20, 28 ।

Q4. (a) मिनिमम स्पैनिंग ट्री (MST) खोजने के लिए प्रिम का एल्गोरिथ्म लिखें। नीचे दिए गए ग्राफ के लिए MST खोजने के लिए प्रिम के एल्गोरिथ्म का उपयोग करें: 10 (छल © ; [a 7 wa (0) (b) DFS और BFS एल्गोरिथ्म लिखें। DFS और BFS एल्गोरिथ्म की टाइम कॉम्प्लेक्सिटी भी निर्धारित करें। दिए गए ग्राफ के लिए, नोड ‘A’ से DFS ट्रैवर्सल अनुक्रम लिखें: 10 <a

Ans. (a) प्रिम का एल्गोरिथ्म और इसका अनुप्रयोग

प्रिम का एल्गोरिथ्म:

प्रिम का एल्गोरिथ्म एक दिए गए, जुड़े हुए, भारित और अप्रत्यक्ष ग्राफ में मिनिमम स्पैनिंग ट्री (MST) खोजने के लिए एक ग्रीडी एल्गोरिथ्म है। यह MST को एक मनमाने ढंग से शुरू होने वाले वर्टेक्स से बढ़ाता है, और प्रत्येक चरण में, ट्री में अब तक जोड़े गए वर्टिस को ट्री के बाहर के वर्टिस से जोड़ने वाला सबसे सस्ता किनारा जोड़ता है।

एल्गोरिथ्म:

  1. MST में शामिल वर्टिस का एक सेट `mstSet` बनाएं, जो शुरू में खाली है।
  2. एक `key` ऐरे बनाएं जिसमें सभी वर्टिस के लिए अनंत मान हो, सिवाय पहले वर्टेक्स के, जिसका मान 0 हो। इसे प्राथमिकता क्यू के रूप में उपयोग किया जाएगा।
  3. एक `parent` ऐरे बनाएं जो MST में किनारों को संग्रहीत करेगा, शुरू में सभी मान NULL हों।
  4. जब तक `mstSet` में सभी वर्टिस शामिल न हो जाएं:
    1. `key` मान के आधार पर, `mstSet` में नहीं होने वाला एक वर्टेक्स `u` चुनें जिसका `key` मान न्यूनतम हो।
    2. `u` को `mstSet` में जोड़ें।
    3. `u` के सभी आसन्न वर्टिस `v` के लिए, यदि `v` `mstSet` में नहीं है और किनारे (u, v) का भार `key[v]` से कम है, तो `key[v]` को किनारे के भार से अपडेट करें और `parent[v]` को `u` पर सेट करें।
  5. `parent` ऐरे का उपयोग करके MST का निर्माण करें।

दिए गए ग्राफ पर अनुप्रयोग:

ग्राफ के किनारे और भार: A-B(1), A-C(7), B-D(5), C-D(2), C-E(8), D-E(3)।

हम वर्टेक्स ‘A’ से शुरू करते हैं।

प्रारंभिक स्थिति:

  • mstSet = {}
  • key = {A:0, B:∞, C:∞, D:∞, E:∞}
  • parent = {A:-1, B:null, C:null, D:null, E:null}

चरण-दर-चरण निष्पादन:

  1. चरण 1: ‘A’ चुनें (key=0)। mstSet = {A}। ‘A’ के पड़ोसियों को अपडेट करें:
    • key[B] = 1 (parent[B] = A)
    • key[C] = 7 (parent[C] = A)
    • key = {A:0, B:1, C:7, D:∞, E:∞}
  2. चरण 2: ‘B’ चुनें (key=1)। mstSet = {A, B}। ‘B’ के पड़ोसियों को अपडेट करें:
    • key[D] = 5 (parent[D] = B)
    • key = {A:0, B:1, C:7, D:5, E:∞}
  3. चरण 3: ‘D’ चुनें (key=5)। mstSet = {A, B, D}। ‘D’ के पड़ोसियों को अपडेट करें:
    • key[C] = min(7, 2) = 2 (parent[C] = D)
    • key[E] = 3 (parent[E] = D)
    • key = {A:0, B:1, C:2, D:5, E:3}
  4. चरण 4: ‘C’ चुनें (key=2)। mstSet = {A, B, D, C}। ‘C’ के पड़ोसियों को अपडेट करें:
    • key[E] = min(3, 8) = 3 (कोई परिवर्तन नहीं)
  5. चरण 5: ‘E’ चुनें (key=3)। mstSet = {A, B, D, C, E}। सभी वर्टिस शामिल हो गए हैं।

`parent` ऐरे से MST के किनारे हैं: (A, B), (B, D), (D, C), (D, E) ।

MST का कुल भार = 1 + 5 + 2 + 3 = 11 ।

(b) DFS और BFS एल्गोरिथ्म और कॉम्प्लेक्सिटी

डेप्थ-फर्स्ट सर्च (DFS) एल्गोरिथ्म (रिकर्सिव):

DFS ट्रैवर्सल के लिए एक स्टैक (या रिकर्सन) का उपयोग करता है। यह एक पथ के साथ जितना संभव हो उतना गहरा जाता है, फिर बैकट्रैक करता है। DFS(graph, u, visited) visited[u] = true print u for each vertex v adjacent to u if not visited[v] DFS(graph, v, visited)

ब्रेथ-फर्स्ट सर्च (BFS) एल्गोरिथ्म (इटरेटिव):

BFS ट्रैवर्सल के लिए एक क्यू का उपयोग करता है। यह स्तर-दर-स्तर खोज करता है। BFS(graph, start) create a queue Q create a set visited Q.enqueue(start) visited.add(start) while Q is not empty u = Q.dequeue() print u for each vertex v adjacent to u if v is not in visited visited.add(v) Q.enqueue(v)

टाइम कॉम्प्लेक्सिटी:

दोनों DFS और BFS के लिए, यदि ग्राफ को एडजेसेंसी लिस्ट का उपयोग करके दर्शाया गया है, तो टाइम कॉम्प्लेक्सिटी O(V + E) है, जहाँ V वर्टिस की संख्या है और E किनारों की संख्या है। ऐसा इसलिए है क्योंकि प्रत्येक वर्टेक्स और प्रत्येक किनारे पर ठीक एक बार विज़िट किया जाता है।

यदि एडजेसेंसी मैट्रिक्स का उपयोग किया जाता है, तो दोनों की कॉम्प्लेक्सिटी O(V 2 ) होती है।

दिए गए ग्राफ के लिए DFS ट्रैवर्सल अनुक्रम (नोड ‘A’ से):

ग्राफ की संरचना (चित्र से अनुमानित): A–B, A–C, A–D, B–E, C–F।

हम DFS ट्रैवर्सल के लिए एक स्टैक (रिकर्सन स्टैक) का उपयोग करेंगे। हम पड़ोसियों को वर्णानुक्रम में मानेंगे।

  1. ‘A’ से शुरू करें। ‘A’ को प्रिंट करें और इसे विज़िटेड के रूप में चिह्नित करें।
  2. ‘A’ के पड़ोसियों पर जाएं। पहले ‘B’ पर जाएं।
  3. ‘B’ को प्रिंट करें और इसे विज़िटेड के रूप में चिह्नित करें।
  4. ‘B’ के पड़ोसियों पर जाएं। ‘E’ पर जाएं।
  5. ‘E’ को प्रिंट करें और इसे विज़िटेड के रूप में चिह्नित करें। ‘E’ का कोई अन-विज़िटेड पड़ोसी नहीं है, इसलिए ‘B’ पर वापस जाएं (बैकट्रैक)।
  6. ‘B’ का कोई और अन-विज़िटेड पड़ोसी नहीं है, इसलिए ‘A’ पर वापस जाएं।
  7. ‘A’ के अगले पड़ोसी, ‘C’ पर जाएं।
  8. ‘C’ को प्रिंट करें और इसे विज़िटेड के रूप में चिह्नित करें।
  9. ‘C’ के पड़ोसियों पर जाएं। ‘F’ पर जाएं।
  10. ‘F’ को प्रिंट करें और इसे विज़िटेड के रूप में चिह्नित करें। ‘F’ का कोई अन-विज़िटेड पड़ोसी नहीं है, इसलिए ‘C’ पर वापस जाएं।
  11. ‘C’ का कोई और अन-विज़िटेड पड़ोसी नहीं है, इसलिए ‘A’ पर वापस जाएं।
  12. ‘A’ के अगले पड़ोसी, ‘D’ पर जाएं।
  13. ‘D’ को प्रिंट करें और इसे विज़िटेड के रूप में चिह्नित करें।

DFS ट्रैवर्सल अनुक्रम: A, B, E, C, F, D ।

(नोट: पड़ोसियों को संसाधित करने के क्रम के आधार पर अन्य मान्य अनुक्रम भी संभव हैं, जैसे A, D, C, F, B, E)।

Q5. (a) क्लास P, NP और NP-कम्प्लीट समस्या की व्याख्या करें। प्रत्येक क्लास के लिए एक उदाहरण दें। 8 (b) निम्नलिखित पर संक्षिप्त नोट्स लिखें: 4×3=12 (i) बैकट्रैकिंग (ii) ब्रांच एंड बाउंड (iii) एप्रोक्सीमेशन एल्गोरिथ्म

Ans. (a) कॉम्प्लेक्सिटी क्लास P, NP, और NP-कम्प्लीट

P क्लास (Polynomial Time):

P उन सभी निर्णय समस्याओं (decision problems) का समूह है जिन्हें एक नियतात्मक ट्यूरिंग मशीन (deterministic Turing machine) द्वारा पॉलीनोमियल समय (polynomial time) में हल किया जा सकता है। पॉलीनोमियल समय का अर्थ है कि समाधान का समय इनपुट आकार n के किसी पॉलीनोमियल फ़ंक्शन, जैसे O(n), O(n 2 ), या O(n k ) से घिरा होता है।

P क्लास की समस्याओं को आम तौर पर “ट्रैक्टेबल” या “कुशलता से हल करने योग्य” माना जाता है।

  • उदाहरण:
    • सॉर्टिंग (Sorting): यह जांचना कि क्या एक सूची सॉर्ट की गई है (निर्णय संस्करण)। सॉर्टिंग एल्गोरिदम जैसे मर्ज सॉर्ट O(n log n) समय में चलते हैं।
    • सबसे छोटा पथ (Shortest Path): एक ग्राफ में दो नोड्स के बीच सबसे छोटा पथ खोजना (डाइज्क्स्ट्रा का एल्गोरिथ्म)।
    • प्राइम नंबर टेस्टिंग: यह निर्धारित करना कि कोई संख्या अभाज्य है या नहीं।

NP क्लास (Nondeterministic Polynomial Time):

NP उन सभी निर्णय समस्याओं का समूह है जिनके लिए, यदि समाधान “हाँ” है, तो उस समाधान को प्रमाणित करने वाला एक “प्रमाणपत्र” (certificate) या “गवाह” (witness) मौजूद होता है, जिसे पॉलीनोमियल समय में सत्यापित किया जा सकता है।

इसका मतलब यह नहीं है कि समस्या को पॉलीनोमियल समय में हल किया जा सकता है, बल्कि यह कि दिए गए समाधान की शुद्धता की जाँच जल्दी की जा सकती है।

  • P क्लास की सभी समस्याएं NP में भी हैं (P ⊆ NP), क्योंकि यदि आप किसी समस्या को पॉलीनोमियल समय में हल कर सकते हैं, तो आप निश्चित रूप से समाधान को भी पॉलीनोमियल समय में सत्यापित कर सकते हैं।
  • उदाहरण:
    • बूलियन सैटिसफाइअबिलिटी (SAT): दिया गया एक बूलियन सूत्र, क्या वेरिएबल्स का कोई ऐसा असाइनमेंट है जो सूत्र को सत्य बनाता है? समाधान खोजना मुश्किल है, लेकिन यदि कोई आपको एक असाइनमेंट देता है, तो आप इसे पॉलीनोमियल समय में प्लग इन करके आसानी से जांच सकते हैं।
    • हैमिल्टोनियन साइकिल: क्या एक ग्राफ में एक ऐसा चक्र है जो प्रत्येक वर्टेक्स से ठीक एक बार गुजरता है? यदि कोई आपको एक पथ देता है, तो आप जल्दी से जांच सकते हैं कि क्या यह एक वैध हैमिल्टोनियन साइकिल है।

NP-कम्प्लीट क्लास (NP-Complete):

NP-कम्प्लीट (NPC) समस्याएं NP क्लास की सबसे कठिन समस्याएं हैं। एक समस्या NP-कम्प्लीट होती है यदि वह दो शर्तों को पूरा करती है:

  1. यह NP में है।
  2. NP में हर दूसरी समस्या पॉलीनोमियल समय में इस समस्या में रिड्यूस (reduce) हो सकती है।

दूसरी शर्त का मतलब है कि यदि आप किसी एक NP-कम्प्लीट समस्या को हल करने के लिए एक पॉलीनोमियल-समय एल्गोरिथ्म खोज लेते हैं, तो आप उस एल्गोरिथ्म का उपयोग NP में हर समस्या को पॉलीनोमियल समय में हल करने के लिए कर सकते हैं। इससे P = NP साबित हो जाएगा, जो कम्प्यूटेशनल कॉम्प्लेक्सिटी थ्योरी में सबसे बड़ी अनसुलझी समस्याओं में से एक है।

  • उदाहरण:
    • SAT (Boolean Satisfiability Problem): यह पहली समस्या थी जिसे NP-कम्प्लीट साबित किया गया था।
    • ट्रैवलिंग सेल्समैन प्रॉब्लम (TSP) (निर्णय संस्करण): क्या शहरों के दिए गए सेट के लिए एक ऐसा टूर मौजूद है जिसकी कुल लंबाई एक निश्चित मान K से कम है?
    • 0/1 नैपसैक समस्या (निर्णय संस्करण): क्या दिए गए मानों और भार वाले आइटम्स का एक सबसेट चुना जा सकता है ताकि कुल मान एक निश्चित सीमा से अधिक हो और कुल भार क्षमता से अधिक न हो?

(b) संक्षिप्त नोट्स

(i) बैकट्रैकिंग (Backtracking):

बैकट्रैकिंग एक सामान्य एल्गोरिथम तकनीक है जो समस्याओं को वृद्धिशील रूप से समाधान बनाने का प्रयास करके रिकर्सिव रूप से हल करने के लिए उपयोग की जाती है। यह समाधान के लिए सभी संभावित उम्मीदवारों को व्यवस्थित रूप से खोजता है। जैसे ही यह निर्धारित होता है कि कोई उम्मीदवार संभवतः एक वैध समाधान तक नहीं ले जा सकता, यह “बैकट्रैक” करता है – यानी, एक विकल्प को पूर्ववत करता है और एक विकल्प का प्रयास करता है। यह डेप्थ-फर्स्ट सर्च के समान है, लेकिन यह उन रास्तों को छाँट देता है जो समाधान नहीं दे सकते। यह उन समस्याओं के लिए विशेष रूप से उपयोगी है जिनमें बाधाएं (constraints) होती हैं।

उदाहरण: N-क्वींस समस्या (एक N×N शतरंज की बिसात पर N रानियों को इस तरह रखना कि कोई भी दो रानियां एक-दूसरे पर हमला न करें), सुडोकू पहेलियाँ, और भूलभुलैया में पथ खोजना।

(ii) ब्रांच एंड बाउंड (Branch and Bound):

ब्रांच एंड बाउंड एक एल्गोरिथम डिजाइन पैराडाइम है जो असतत और संयोजी अनुकूलन समस्याओं (discrete and combinatorial optimization problems) के लिए उपयोग किया जाता है। बैकट्रैकिंग की तरह, यह समाधान स्थान (solution space) का एक व्यवस्थित अन्वेषण करता है। हालाँकि, यह अधिक बुद्धिमान है क्योंकि यह अनुकूलित की जा रही मात्रा के अनुमानित ऊपरी और निचले बाउंड का उपयोग करके उन शाखाओं को छाँट (prune) देता है जो एक इष्टतम समाधान की ओर नहीं ले जा सकती हैं। यह एक स्टेट-स्पेस ट्री बनाता है और उस नोड को प्राथमिकता देता है जो सबसे आशाजनक प्रतीत होता है (आमतौर पर ब्रेथ-फर्स्ट तरीके से या बेस्ट-फर्स्ट तरीके से)।

उदाहरण: ट्रैवलिंग सेल्समैन प्रॉब्लम (TSP), 0/1 नैपसैक प्रॉब्लम, और इंटीजर प्रोग्रामिंग। यह बैकट्रैकिंग से अलग है क्योंकि यह अनुकूलन समस्याओं के लिए है, न कि केवल निर्णय समस्याओं के लिए।

(iii) एप्रोक्सीमेशन एल्गोरिथ्म (Approximation Algorithms):

एप्रोक्सीमेशन एल्गोरिथ्म का उपयोग NP-हार्ड अनुकूलन समस्याओं के लिए किया जाता है, जिनके लिए पॉलीनोमियल समय में सटीक इष्टतम समाधान खोजना अव्यावहारिक (intractable) माना जाता है। एक सटीक समाधान खोजने के बजाय, ये एल्गोरिदम पॉलीनोमियल समय में एक निकट-इष्टतम (near-optimal) समाधान खोजने का लक्ष्य रखते हैं।

समाधान की गुणवत्ता एक प्रदर्शन अनुपात (performance ratio) या एप्रोक्सीमेशन फैक्टर द्वारा गारंटीकृत होती है। यह अनुपात लौटाए गए समाधान के मान और इष्टतम समाधान के मान के बीच के अनुपात को सीमित करता है। उदाहरण के लिए, 2-एप्रोक्सीमेशन एल्गोरिथ्म एक ऐसा समाधान लौटाएगा जो इष्टतम समाधान से अधिकतम दोगुना खराब है।

उदाहरण: वर्टेक्स कवर समस्या के लिए एक सरल 2-एप्रोक्सीमेशन एल्गोरिथ्म मौजूद है। यूक्लिडियन TSP के लिए भी एप्रोक्सीमेशन एल्गोरिदम हैं।

IGNOU MCS-211 Previous Year Solved Question Paper in English

Q1. (a) Apply merge sort algorithm to sort the following array elements : 5 4, 6, 2, 3, 8, 5, 7, 1 (b) Explain the Horner’s method of polynomial evaluation with the help of an example. What is the time complexity of this method ? 5 (c) Build the Huffman tree for the following data : 5 Character Frequency a 70 b 2 c 5 d 3 e 3 f 7 (d) Make all possible binary search trees consisting of three keys 0 50 90. 5 (e) Consider the following graph : 5 @ (B) (c) Represent this graph using adjacency list. (f) Explain the Kruskal’s-algorithm for Minimum Spanning Tree (MST) construction. 5 (g) What is Boolean Satisfiability (SAT) problem ? Explain in detail. 5 (h) Using Breadth First Search (BFS), traverse the following graph by using ‘a’ as the starting node : 5 | () ee a

Ans. (a) Merge Sort Algorithm: Merge sort is a divide and conquer algorithm. It works by recursively dividing the input array into two halves, sorting both halves, and then merging the two sorted halves. Given array: [4, 6, 2, 3, 8, 5, 7, 1]

  1. Divide:
    • [4, 6, 2, 3] and [8, 5, 7, 1]
    • [4, 6], [2, 3] and [8, 5], [7, 1]
    • [4], [6] | [2], [3] | [8], [5] | [7], [1]
  2. Merge and Sort:
    • Merge [4] and [6] -> [4, 6]
    • Merge [2] and [3] -> [2, 3]
    • Merge [8] and [5] -> [5, 8]
    • Merge [7] and [1] -> [1, 7]
  3. Further Merge:
    • Merge [4, 6] and [2, 3] -> [2, 3, 4, 6]
    • Merge [5, 8] and [1, 7] -> [1, 5, 7, 8]
  4. Final Merge:
    • Merge [2, 3, 4, 6] and [1, 5, 7, 8] -> [1, 2, 3, 4, 5, 6, 7, 8]

The final sorted array is:

1, 2, 3, 4, 5, 6, 7, 8

.

(b) Horner’s Method: Horner’s method is an efficient algorithm for evaluating a polynomial at a given value of x. It minimizes the number of multiplications required by using nested multiplication. A polynomial P(x) = a n x n + a n-1 x n-1 + … + a 1 x + a 0 can be written as: P(x) = a 0 + x(a 1 + x(a 2 + … + x(a n-1 + x * a n )…)) Example: Evaluate P(x) = 2x 3 – 6x 2 + 2x – 1 at x = 3. The coefficients are: a 3 =2, a 2 =-6, a 1 =2, a 0 =-1. In Horner’s form: P(x) = -1 + x(2 + x(-6 + x(2))) Step-by-step calculation:

  1. Start with result = a 3 = 2
  2. Next result = a 2 + (previous result × x) = -6 + (2 × 3) = 0
  3. Next result = a 1 + (previous result × x) = 2 + (0 × 3) = 2
  4. Final result = a 0 + (previous result × x) = -1 + (2 × 3) = 5

So, P(3) = 5.


Time Complexity:

The method requires only n multiplications and n additions for a polynomial of degree n. Therefore, its time complexity is

O(n)

, which is much better than direct evaluation (which takes O(n

2

) multiplications).

(c) Huffman Tree Construction: Huffman coding is a lossless data compression algorithm. It uses a greedy approach by repeatedly merging the two nodes with the lowest frequencies to build a tree. Given characters and frequencies: a: 70, b: 2, c: 5, d: 3, e: 3, f: 7 Steps:

  1. Pick the two nodes with the lowest frequency: ‘b’ (2) and ‘d’ (3). Merge them under a new internal node (N1) with frequency 2+3=5.
  2. The frequencies are now: e(3), N1(5), c(5), f(7), a(70). Pick ‘e’ (3) and N1 (5). Merge them under a new internal node (N2) with frequency 3+5=8.
  3. The frequencies are now: c(5), f(7), N2(8), a(70). Pick ‘c’ (5) and ‘f’ (7). Merge them under a new internal node (N3) with frequency 5+7=12.
  4. The frequencies are now: N2(8), N3(12), a(70). Pick N2 (8) and N3 (12). Merge them under a new internal node (N4) with frequency 8+12=20.
  5. The frequencies are now: N4(20), a(70). Pick N4 (20) and ‘a’ (70). Merge them under the root node (N5) with frequency 20+70=90.


Final Tree and Codes (using 0 for left edge, 1 for right edge):

  • a: 1
  • f: 011
  • c: 010
  • e: 001
  • d: 0001
  • b: 0000

(d) Possible Binary Search Trees (BSTs) for three keys (0, 50, 90): The property of a BST is that for any node, all values in its left subtree are less than the node’s value, and all values in its right subtree are greater. For three distinct keys, there are 5 possible BSTs (Catalan number C(3) = 5). Keys: {0, 50, 90} The possible trees are:

  1. 50 is root: 
     50 / \ 0 90
  2. 0 is root (right-skewed): 
     0 \ 50 \ 90
  3. 90 is root (left-skewed): 
     90 / 50 / 0
  4. 0 is root (different structure): 
     0 \ 90 / 50
  5. 90 is root (different structure): 
     90 / 0 \ 50

(e) Graph Representation using Adjacency List: The given graph has three nodes: A, B, C. There is an edge between A and B, and an edge between A and C. An adjacency list maintains, for each vertex, a list of its adjacent vertices. The adjacency list for this graph would be:

  • A: -> [ B, C ]
  • B: -> [ A ]
  • C: -> [ A ]

This representation is memory-efficient, especially for sparse graphs (graphs with few edges).

(f) Kruskal’s Algorithm: Kruskal’s algorithm is a greedy algorithm to find a Minimum Spanning Tree (MST) for a given connected, weighted, and undirected graph. An MST is a subgraph that connects all the vertices, contains no cycles, and has the minimum possible total edge weight. Algorithm Steps:

  1. Sort all the edges in the graph in non-decreasing order of their weights.
  2. Create an empty set, MST.
  3. Iterate through the sorted edges. For each edge (u, v):
  4. If adding the edge (u, v) to the MST does not form a cycle, add it to the MST.
  5. If it does form a cycle, discard it.
  6. Continue this process until there are V-1 edges in the MST (where V is the number of vertices).

To detect cycles, a

Disjoint Set Union (DSU)

data structure is commonly used.

(g) Boolean Satisfiability (SAT) Problem: The Boolean Satisfiability (SAT) problem is the problem of determining if there exists a variable assignment that satisfies a given Boolean formula. In other words, can we assign TRUE or FALSE values to the boolean variables in such a way that the entire formula evaluates to TRUE. Detailed Explanation:

  • Boolean Formula: This is an expression made up of boolean variables (which can be TRUE or FALSE) and operators like AND (∧), OR (∨), and NOT (¬).
  • Satisfiability: A formula is “satisfiable” if there exists at least one set of values for its variables that makes the formula TRUE. If no such assignment exists, the formula is “unsatisfiable.”
  • Example:
    • Formula: F = (x ∨ y) ∧ (¬x ∨ z)
    • This formula is satisfiable. For instance, if we set x = TRUE, y = FALSE, and z = TRUE, then F = (TRUE ∨ FALSE) ∧ (¬TRUE ∨ TRUE) = TRUE ∧ TRUE = TRUE.
    • Formula: G = (a ∧ ¬a) is unsatisfiable, as it will always be FALSE for any value of ‘a’.
  • Significance: The SAT problem was the first problem ever proven to be NP-complete (by the Cook-Levin theorem). This means it is among the hardest problems in the NP class. Many other hard problems (like scheduling, circuit design) can be reduced to SAT.

(h) Breadth-First Search (BFS) Traversal: BFS is a graph traversal algorithm that starts at a source node and explores neighbor nodes first, before moving to the next level neighbors. It uses a queue data structure. For the given graph (interpreted as a–b, a–c, a–d, b–e, c–f) and starting node ‘a’:

  1. Initialize an empty queue (Q) and an empty visited set (V). Add ‘a’ to Q and mark it in V. Q: [a], V: {a}
  2. Dequeue ‘a’, add to traversal. Enqueue all unvisited neighbors of ‘a’ (b, c, d) and mark them in V. Traversal: a Q: [b, c, d], V: {a, b, c, d}
  3. Dequeue ‘b’, add to traversal. Enqueue unvisited neighbor of ‘b’ (‘e’) and mark in V. Traversal: a, b Q: [c, d, e], V: {a, b, c, d, e}
  4. Dequeue ‘c’, add to traversal. Enqueue unvisited neighbor of ‘c’ (‘f’) and mark in V. Traversal: a, b, c Q: [d, e, f], V: {a, b, c, d, e, f}
  5. Dequeue ‘d’, add to traversal. ‘d’ has no unvisited neighbors. Traversal: a, b, c, d Q: [e, f]
  6. Dequeue ‘e’, add to traversal. No unvisited neighbors. Traversal: a, b, c, d, e Q: [f]
  7. Dequeue ‘f’, add to traversal. No unvisited neighbors. Traversal: a, b, c, d, e, f Q: []

The queue is now empty, so the traversal is complete.

Final BFS traversal order:

a, b, c, d, e, f

.

Q2. (a) Write the principle of optimality. Explain how dynamic programming can be used to solve chain matrix multiplication problem. 10 (b) Define a fractional Knapsack problem as an optimization problem. Write a Greedy method to find an optimal solution to the problem. Find the complexity of the algorithm. 10

Ans. (a) Principle of Optimality and Chain Matrix Multiplication Principle of Optimality: The principle of optimality is the foundation of dynamic programming. It states that “an optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.” In simpler terms, it means that the optimal solution to a problem is composed of optimal solutions to its sub-problems. If we can break a large problem into smaller, overlapping sub-problems, and the optimal solutions to these sub-problems contribute to the optimal solution of the larger problem, then we can use dynamic programming. Using Dynamic Programming for Chain Matrix Multiplication (MCM): The MCM problem is to find the most efficient parenthesization for multiplying a chain of matrices (e.g., A 1 , A 2 , …, A n ). The goal is to minimize the total number of scalar multiplications. Let’s say we have the chain A i …A j . The final step of multiplying this chain will occur at some split point k, where i ≤ k < j, and we will multiply the results of (A i …A k ) and (A k+1 …A j ). The principle of optimality applies here: the total optimal cost to multiply A i …A j can only be obtained if the multiplications of the sub-chains (A i …A k ) and (A k+1 …A j ) were also done optimally. The Dynamic Programming Approach:

  1. Characterize the Structure: We define the sub-problems as m[i, j], which is the minimum number of scalar multiplications needed to multiply the matrices from A i to A j .
  2. Recursive Solution: We formulate a recursive formula for m[i, j].
    • If i = j, then m[i, j] = 0 (no multiplications for a single matrix).
    • If i < j, then m[i, j] = min i≤k { m[i, k] + m[k+1, j] + p i-1 p k p j } Where p i-1 , p k , and p j are the dimensions of matrices A i , A k , and A j (A i has size p i-1 x p i ).
  3. Bottom-Up Computation: Instead of plain recursion, which repeatedly solves the same sub-problems, dynamic programming stores these results in a table. It starts with small chains (short length) and builds up to larger chains, reusing the solution to each sub-problem. This leverages the property of overlapping subproblems.

Thus, dynamic programming efficiently solves the MCM problem in O(n

3

) time by filling the table and applying the recursive formula in a bottom-up manner.

(b) Fractional Knapsack Problem Definition: The fractional knapsack problem is an optimization problem . In it, we are given a set of n items, each with its own weight (w i ) and value (v i ). We have a knapsack with a maximum weight capacity W. The goal is to choose items (or fractions of them) to put into the knapsack to maximize the total value of items in the knapsack, while the total weight does not exceed the capacity W. In the fractional version, we are allowed to take a fraction of an item. As an Optimization Problem:

  • Input: A set of n items {1, …, n}, each with weight w i > 0 and value v i > 0, and a knapsack capacity W > 0.
  • Output: An amount x i (where 0 ≤ x i ≤ 1) for each item, such that:
    • Constraint: Σ (x i * w i ) ≤ W (Total weight must not exceed capacity)
    • Objective: Maximize Σ (x i * v i ) (Maximize total value)

Greedy Method for an Optimal Solution: The fractional knapsack problem can be solved optimally using a greedy algorithm. The greedy strategy is to prioritize items with the highest value-per-weight ratio . Algorithm:

  1. For each item i, calculate the value-per-weight ratio (v i / w i ).
  2. Sort all items in decreasing order of their ratio.
  3. Start with an empty knapsack (total value = 0, current weight = 0).
  4. Iterate through the sorted list of items:
    1. For the current item i, if its entire weight (w i ) can fit into the remaining capacity of the knapsack (i.e., w i ≤ W – current weight):
      • Take the whole item (x i = 1).
      • Update the total value and current weight of the knapsack.
    2. If the item cannot fit completely:
      • Take a fraction of the item that fills the remaining capacity. Fraction = (W – current weight) / w i .
      • Add this fraction to the knapsack.
      • The knapsack is now full, so stop the algorithm.
  5. Return the total value in the knapsack.

Complexity:

  • Calculating the ratios takes O(n) time.
  • Sorting the items based on their ratio takes O(n log n) time.
  • Iterating through the sorted list takes O(n) time.

Therefore, the overall time complexity of the algorithm is

O(n log n)

, which is dominated by the sorting step.

Q3. (a) Write Dijkstra’s algorithm and use it to find the minimum distances of all the nodes from node ‘a which is taken as the source node for the following graph : 10 यू 7 © (7) ह 2 © © (b) Write the quick sort algorithm. Also find the worst case complexity of this algorithm. Use this algorithm for sorting the following list : 10 20, 5, 5, 8, 6, 28

Ans. (a) Dijkstra’s Algorithm and its Application Dijkstra’s Algorithm: Dijkstra’s algorithm solves the single-source shortest path problem on a graph with non-negative edge weights. It is a greedy algorithm that finds the shortest distance from a source to all other vertices. Algorithm:

  1. Create a distance array `dist[]` and set the source vertex’s distance to 0 and all other vertices’ distances to infinity.
  2. Create a priority queue containing all vertices. The priority is based on the distance value.
  3. While the priority queue is not empty:
    1. Extract the vertex `u` with the smallest distance from the queue.
    2. For each neighbor `v` of `u`:
      • If `dist[u] + weight(u, v) < dist[v]`, update `dist[v]`.
      • This process is called “relaxation”.
  4. When the algorithm finishes, the `dist[]` array holds the shortest distances from the source to all vertices.


Application on the given graph:

Graph edges and weights: a-b(3), a-d(7), b-c(7), b-d(2), d-e(2). Source node: ‘a’.

Initial state:

  • dist = {a: 0, b: ∞, c: ∞, d: ∞, e: ∞}
  • Priority Queue (PQ) = [(0, a)]


Step-by-step execution:

  1. Iteration 1:
    • Extract (0, a) from PQ. Visit node ‘a’.
    • Neighbors of ‘a’: ‘b’ and ‘d’.
    • Relax b: dist[b] = min(∞, 0+3) = 3. Insert (3, b) into PQ.
    • Relax d: dist[d] = min(∞, 0+7) = 7. Insert (7, d) into PQ.
    • dist = {a: 0, b: 3, c: ∞, d: 7, e: ∞}, PQ = [(3, b), (7, d)]
  2. Iteration 2:
    • Extract the node with the smallest distance from PQ: (3, b).
    • Neighbors of ‘b’: ‘c’ and ‘d’.
    • Relax c: dist[c] = min(∞, 3+7) = 10. Insert (10, c) into PQ.
    • Relax d: dist[d] = min(7, 3+2) = 5. Update distance of ‘d’ in PQ.
    • dist = {a: 0, b: 3, c: 10, d: 5, e: ∞}, PQ = [(5, d), (10, c)]
  3. Iteration 3:
    • Extract (5, d) from PQ.
    • Neighbor of ‘d’: ‘e’.
    • Relax e: dist[e] = min(∞, 5+2) = 7. Insert (7, e) into PQ.
    • dist = {a: 0, b: 3, c: 10, d: 5, e: 7}, PQ = [(7, e), (10, c)]
  4. Iteration 4:
    • Extract (7, e). No unvisited neighbors.
  5. Iteration 5:
    • Extract (10, c). No unvisited neighbors.

The PQ is now empty. The minimum distances from source ‘a’ are:

  • a: 0
  • b: 3
  • c: 10
  • d: 5
  • e: 7

(b)

Quick Sort Algorithm

Algorithm:

Quick sort is an efficient, in-place, divide-and-conquer sorting algorithm.

  1. Divide: Choose an element from the array as a pivot. Partition the array into two sub-arrays: one with elements less than or equal to the pivot, and the other with elements greater than the pivot.
  2. Conquer: Recursively apply quick sort to the two sub-arrays.
  3. Combine: Nothing needs to be done, as the sorting is done in-place.


Pseudocode:

QUICKSORT(A, low, high) if low < high p = PARTITION(A, low, high) QUICKSORT(A, low, p - 1) QUICKSORT(A, p + 1, high)
PARTITION(A, low, high) pivot = A[high] i = low - 1 for j = low to high - 1 if A[j] <= pivot i = i + 1 swap A[i] and A[j] swap A[i + 1] and A[high] return i + 1


Worst Case Complexity:

The worst-case complexity of Quick Sort is

O(n

2

)

. This occurs when the pivot selection consistently picks the smallest or largest element in the array. In this case, the partitioning process creates one sub-array with 0 elements and another with n-1 elements, leading to an unbalanced split. This often happens when the input array is already sorted or reverse-sorted.


Application on the given list: [20, 5, 5, 8, 6, 28]

We will use the last element as the pivot.

  1. Initial call: `QUICKSORT([20, 5, 5, 8, 6, 28], 0, 5)`
    • Pivot = 28. After partitioning, the array remains unchanged as all elements are smaller than 28. Pivot is at its correct place.
    • Partition index is 5. Recursive call on `QUICKSORT([20, 5, 5, 8, 6], 0, 4)`.
  2. Call: `QUICKSORT([20, 5, 5, 8, 6], 0, 4)`
    • Pivot = 6. Partitioning: elements <= 6 go to the left.
    • The array becomes: `[5, 5, 6, 8, 20]` (within the sub-array). The new index of pivot (6) is 2.
    • Recursive calls: `QUICKSORT([5, 5], 0, 1)` and `QUICKSORT([8, 20], 3, 4)`.
  3. Call: `QUICKSORT([5, 5], 0, 1)`
    • Pivot = 5. After partitioning: `[5, 5]`.
    • No further recursive calls as sub-arrays are sorted.
  4. Call: `QUICKSORT([8, 20], 3, 4)`
    • Pivot = 20. After partitioning: `[8, 20]`.
    • No further recursive calls.

Combining all the recursive calls, the final sorted list is:

5, 5, 6, 8, 20, 28

.

Q4. (a) Write Prim’s algorithm to find Minimum Spanning Tree (MST). Use Prim’s algorithm to find MST for the graph given below : 10 (छल © ; [a 7 wa (0) (b) Write DFS and BFS algorithms. Also determine the time complexity of DFS and BFS algorithms. For the given graph, write DFS traversal sequence from node ‘A’ : 10 <a

Ans. (a) Prim’s Algorithm and its Application Prim’s Algorithm: Prim’s algorithm is a greedy algorithm that finds a Minimum Spanning Tree (MST) for a given connected, weighted, and undirected graph. It grows the MST from an arbitrary starting vertex, and at each step, it adds the cheapest possible edge that connects a vertex in the tree to a vertex outside the tree. Algorithm:

  1. Initialize a set `mstSet` of vertices included in MST, initially empty.
  2. Create a `key` array to store the minimum weight edge for each vertex to connect to the tree, initialized to infinity for all vertices except the first, which is 0. This will be used as a priority queue.
  3. Create a `parent` array to store the edges in the MST, initially all null.
  4. While `mstSet` does not include all vertices:
    1. Pick a vertex `u` not in `mstSet` that has the minimum `key` value.
    2. Add `u` to `mstSet`.
    3. For all adjacent vertices `v` of `u`, if `v` is not in `mstSet` and the weight of edge (u, v) is less than `key[v]`, update `key[v]` with the edge weight and set `parent[v]` to `u`.
  5. Construct the MST using the `parent` array.


Application on the given graph:

Graph edges and weights: A-B(1), A-C(7), B-D(5), C-D(2), C-E(8), D-E(3).

We start at vertex ‘A’.

Initial state:

  • mstSet = {}
  • key = {A:0, B:∞, C:∞, D:∞, E:∞}
  • parent = {A:-1, B:null, C:null, D:null, E:null}


Step-by-step execution:

  1. Step 1: Pick ‘A’ (key=0). mstSet = {A}. Update neighbors of ‘A’:
    • key[B] = 1 (parent[B] = A)
    • key[C] = 7 (parent[C] = A)
    • key = {A:0, B:1, C:7, D:∞, E:∞}
  2. Step 2: Pick ‘B’ (key=1). mstSet = {A, B}. Update neighbors of ‘B’:
    • key[D] = 5 (parent[D] = B)
    • key = {A:0, B:1, C:7, D:5, E:∞}
  3. Step 3: Pick ‘D’ (key=5). mstSet = {A, B, D}. Update neighbors of ‘D’:
    • key[C] = min(7, 2) = 2 (parent[C] = D)
    • key[E] = 3 (parent[E] = D)
    • key = {A:0, B:1, C:2, D:5, E:3}
  4. Step 4: Pick ‘C’ (key=2). mstSet = {A, B, D, C}. Update neighbors of ‘C’:
    • key[E] = min(3, 8) = 3 (no change)
  5. Step 5: Pick ‘E’ (key=3). mstSet = {A, B, D, C, E}. All vertices are included.

The edges of the MST from the `parent` array are:

(A, B), (B, D), (D, C), (D, E)

.

The total weight of the MST = 1 + 5 + 2 + 3 =

11

.

(b) DFS and BFS Algorithms and Complexity Depth-First Search (DFS) Algorithm (Recursive): DFS uses a stack (or recursion) for traversal. It goes as deep as possible along a path before backtracking. 

DFS(graph, u, visited) visited[u] = true print u for each vertex v adjacent to u if not visited[v] DFS(graph, v, visited)

Breadth-First Search (BFS) Algorithm (Iterative): BFS uses a queue for traversal. It explores level by level. 

BFS(graph, start) create a queue Q create a set visited Q.enqueue(start) visited.add(start) while Q is not empty u = Q.dequeue() print u for each vertex v adjacent to u if v is not in visited visited.add(v) Q.enqueue(v)

Time Complexity: For both DFS and BFS, if the graph is represented using an adjacency list , the time complexity is O(V + E) , where V is the number of vertices and E is the number of edges. This is because every vertex and every edge is visited exactly once. If an adjacency matrix is used, the complexity for both is O(V 2 ) . DFS Traversal Sequence for the given graph (from node ‘A’): Graph structure (inferred from the image): A–B, A–C, A–D, B–E, C–F. We’ll use a stack (the recursion stack) for DFS traversal. Let’s assume we visit neighbors in alphabetical order.

  1. Start at ‘A’. Print ‘A’ and mark as visited.
  2. Go to neighbor of ‘A’. First, visit ‘B’.
  3. Print ‘B’ and mark as visited.
  4. Go to neighbor of ‘B’. Visit ‘E’.
  5. Print ‘E’ and mark as visited. ‘E’ has no unvisited neighbors, so backtrack to ‘B’.
  6. ‘B’ has no more unvisited neighbors, so backtrack to ‘A’.
  7. Go to the next neighbor of ‘A’, which is ‘C’.
  8. Print ‘C’ and mark as visited.
  9. Go to neighbor of ‘C’. Visit ‘F’.
  10. Print ‘F’ and mark as visited. ‘F’ has no unvisited neighbors, so backtrack to ‘C’.
  11. ‘C’ has no more unvisited neighbors, so backtrack to ‘A’.
  12. Go to the next neighbor of ‘A’, which is ‘D’.
  13. Print ‘D’ and mark as visited.

The DFS traversal sequence is: A, B, E, C, F, D . (Note: Other valid sequences are possible depending on the order in which neighbors are processed, e.g., A, D, C, F, B, E).

Q5. (a) Explain the class P, NP and NP-complete problem. Give one example for each class. 8 (b) Write short notes on the following : 4×3=12 (i) Backtracking (ii) Branch and Bound (iii) Approximation algorithms

Ans. (a) Complexity Classes P, NP, and NP-Complete Class P (Polynomial Time): P is the set of all decision problems that can be solved by a deterministic Turing machine in polynomial time . Polynomial time means the solution time is bounded by a polynomial function of the input size n, such as O(n), O(n 2 ), or O(n k ). Problems in class P are generally considered “tractable” or “efficiently solvable.”

  • Example:
    • Sorting: Checking if a list is sorted (decision version). Sorting algorithms like Merge Sort run in O(n log n) time.
    • Shortest Path: Finding the shortest path between two nodes in a graph (Dijkstra’s algorithm).
    • Prime Number Testing: Determining if a number is prime.

Class NP (Nondeterministic Polynomial Time): NP is the set of all decision problems for which, if the answer is “yes,” there exists a “certificate” or “witness” that can be used to verify the solution in polynomial time. This does not mean the problem can be solved in polynomial time, but rather that a given solution’s correctness can be checked quickly.

  • All problems in P are also in NP (P ⊆ NP), because if you can solve a problem in polynomial time, you can certainly verify the solution in polynomial time.
  • Example:
    • Boolean Satisfiability (SAT): Given a Boolean formula, is there an assignment of variables that makes the formula true? Finding a solution is hard, but if someone gives you an assignment, you can easily check it by plugging it in, which takes polynomial time.
    • Hamiltonian Cycle: Does a graph contain a cycle that passes through every vertex exactly once? If someone gives you a path, you can quickly check if it is a valid Hamiltonian cycle.

Class NP-Complete (NP-Complete): The NP-complete (NPC) problems are the hardest problems in the NP class. A problem is NP-complete if it satisfies two conditions:

  1. It is in NP.
  2. Every other problem in NP can be reduced to it in polynomial time.

The second condition implies that if you find a polynomial-time algorithm for any single NP-complete problem, you could use that algorithm to solve every problem in NP in polynomial time. This would prove P = NP, one of the biggest unsolved problems in computational complexity theory.

  • Example:
    • SAT (Boolean Satisfiability Problem): This was the first problem proven to be NP-complete.
    • Traveling Salesperson Problem (TSP) (decision version): For a given set of cities, is there a tour with a total length less than some value K?
    • 0/1 Knapsack Problem (decision version): Can a subset of items with given values and weights be chosen such that the total value is above a certain threshold and the total weight does not exceed capacity?

(b)

Short Notes

(i) Backtracking:

Backtracking is a general algorithmic technique for solving problems recursively by trying to build a solution incrementally. It systematically searches for all possible candidates for a solution. As soon as it determines that a candidate cannot possibly be completed to a valid solution, it “backtracks” — i.e., undoes a choice and tries an alternative. It is similar to a depth-first search, but it prunes paths that cannot lead to a solution. It is especially useful for problems with constraints.


Examples:

N-Queens problem (placing N queens on an N×N chessboard so that no two queens attack each other), Sudoku puzzles, and finding a path in a maze.

(ii) Branch and Bound: Branch and Bound is an algorithm design paradigm used for discrete and combinatorial optimization problems. Like backtracking, it performs a systematic exploration of the solution space. However, it is more intelligent as it prunes branches that cannot lead to an optimal solution by using estimated upper and lower bounds of the quantity being optimized. It builds a state-space tree and prioritizes the node that seems most promising (usually in a breadth-first or best-first manner). Examples: Traveling Salesperson Problem (TSP), the 0/1 Knapsack Problem, and integer programming. It differs from backtracking as it is for optimization problems, not just decision problems.

(iii) Approximation Algorithms: Approximation algorithms are used for NP-hard optimization problems, for which finding the exact optimal solution is considered intractable (cannot be done in polynomial time). Instead of finding an exact solution, these algorithms aim to find a near-optimal solution in polynomial time. The quality of the solution is guaranteed by a performance ratio or approximation factor . This ratio bounds the ratio between the returned solution’s value and the optimal solution’s value. For example, a 2-approximation algorithm will return a solution that is at most twice as bad as the optimal one. Examples: A simple 2-approximation algorithm exists for the Vertex Cover problem. There are also approximation algorithms for the Euclidean TSP.

Download IGNOU previous Year Question paper download PDFs for MCS-211 to improve your preparation. These ignou solved question paper IGNOU Previous Year Question paper solved PDF in Hindi and English help you understand the exam pattern and score better.

Thanks!

Reader Interactions

Leave a Reply

Your email address will not be published. Required fields are marked *