उत्तरों सहित एल्गोरिदम और जटिलता वर्कशीट

डिवाइड-एंड-कॉन्कर एल्गोरिदम के तीन चरण कौन-से हैं?

1. Aसॉर्ट, सर्च, रिटर्न
2. Bअनुमान, जाँच, दोहराव
3. Cपढ़ना, गणना, लिखना
4. Dविभाजन (divide), विजय (conquer), संयोजन (combine)

किसी एल्गोरिदम का रनिंग टाइम O(n) है। इस वृद्धि को क्या कहते हैं?

1. Aद्विघाती (quadratic)
2. Bलघुगणकीय (logarithmic)
3. Cरैखिक (linear)
4. Dस्थिर (constant)

n तत्वों वाले अनसॉर्टेड ऐरे में लीनियर सर्च (linear search) की टाइम कॉम्प्लेक्सिटी (वर्स्ट केस) क्या है?

1. AO(log n)
2. BO(n²)
3. CO(n)
4. DO(1)

मर्ज सॉर्ट के लिए डायनेमिक प्रोग्रामिंग कोई वास्तविक गति-वृद्धि क्यों नहीं देती?

1. Aमर्ज सॉर्ट की कोई रिकर्सिव संरचना नहीं है
2. Bडायनेमिक प्रोग्रामिंग केवल ग्राफ़ समस्याओं पर काम करती है, ऐरे पर नहीं
3. Cइसकी उप-समस्याएँ अतिव्यापी नहीं हैं, इसलिए दोबारा उपयोग करने को कुछ नहीं है
4. Dमर्ज सॉर्ट पहले से ही O(n) है

किसी समस्या में इष्टतम उप-संरचना (optimal substructure) होने का क्या अर्थ है?

1. Aहर उप-समस्या का आकार समान है
2. Bएक इष्टतम समाधान उसकी उप-समस्याओं के इष्टतम समाधानों से बनाया जा सकता है
3. Cसमस्या को स्थिर समय में हल किया जा सकता है
4. Dसमस्या का ठीक एक इष्टतम समाधान है, जो हर उप-समस्या में साझा होता है

m और n लंबाई की स्ट्रिंग्स के लॉन्गेस्ट कॉमन सबसीक्वेंस के लिए मानक डायनेमिक प्रोग्रामिंग एल्गोरिदम की टाइम कॉम्प्लेक्सिटी क्या है?

1. AO(mn log n)
2. BO(m + n)
3. CO(mn)
4. DO(2^m+n)

कौन-सा एल्गोरिदम बार-बार ऐसा सबसे सस्ता एज जोड़कर, जो चक्र न बनाए, मिनिमम स्पैनिंग ट्री खोजता है?

1. AKruskal का एल्गोरिदम
2. BDijkstra का एल्गोरिदम
3. CFloyd–Warshall
4. Dएक नोड से शुरू होने वाला Prim का एल्गोरिदम

स्ट्रासेन का एल्गोरिदम आधे आकार के ब्लॉकों के 8 के बजाय 7 रिकर्सिव गुणनों से मैट्रिक्स गुणा करता है। इसका रनिंग टाइम क्या है?

1. AΘ(n³)
2. BΘ(n² log n)
3. CΘ(n^{log₂ 7}), लगभग n^2.81
4. DΘ(n²)