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

इंसर्शन सॉर्ट (insertion sort) की वर्स्ट-केस टाइम कॉम्प्लेक्सिटी क्या है?

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

किसी समस्या को सामान्यतः सुसाध्य (tractable) कब कहा जाता है?

1. Aजब उसका कोई समाधान न हो
2. Bजब उसे केवल हर संभावना आज़माकर हल किया जा सके
3. Cजब उसे स्थिर समय में हल किया जा सके
4. Dजब उसे बहुपदी समय में हल किया जा सके

0 से k की सीमा में n पूर्णांकों के लिए काउंटिंग सॉर्ट (counting sort) का रनिंग टाइम क्या है?

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

एक ग्रीडी एल्गोरिदम (greedy algorithm):

1. Aहमेशा इष्टतम समाधान देता है
2. Bहर चरण में स्थानीय रूप से सर्वोत्तम विकल्प चुनता है
3. Cकेवल रिकर्शन का उपयोग करता है
4. Dहर संभव समाधान आज़माता है

फ़्लॉयड–वॉर्शल एल्गोरिदम क्या गणना करता है, और कितनी तेज़ी से?

1. Aएक मिनिमम स्पैनिंग ट्री, O(E log V) में
2. Bएक टोपोलॉजिकल क्रम, O(V²) में
3. Cएक स्रोत शीर्ष से बाकी सभी तक सबसे छोटे पथ, O(V + E) में
4. Dशीर्षों के सभी युग्मों के बीच सबसे छोटे पथ, O(V³) में

क्या यह कहना सही है कि एक O(n²) एल्गोरिदम O(n³) भी है?

1. Aनहीं, क्योंकि Big O को हमेशा फ़ंक्शन की सटीक वृद्धि दर बतानी चाहिए
2. Bहाँ, क्योंकि Big O एक ऊपरी सीमा है और n², n³ से तेज़ नहीं बढ़ता
3. Cहाँ, पर केवल तब जब n 100 से छोटा हो
4. Dनहीं, क्योंकि बड़े n के लिए n³, n² से छोटा है

बाइनरी काउंटर को बढ़ाने (increment) की एमॉर्टाइज़्ड लागत क्या है, यह देखते हुए कि एक वृद्धि कई बिट पलट सकती है?

1. Aप्रति वृद्धि O(n log n)
2. Bप्रति वृद्धि O(1)
3. Cप्रति वृद्धि O(log n)
4. Dप्रति वृद्धि O(n)

इनमें से कौन-सी संतुष्टि समस्या बहुपदी समय में हल होने योग्य ज्ञात है?

1. Aसर्किट संतुष्टि
2. B2-SAT, जिसमें हर क्लॉज़ में अधिकतम दो लिटरल होते हैं
3. Cकंजंक्टिव नॉर्मल फ़ॉर्म में सूत्रों पर सामान्य SAT
4. D3-SAT, जिसमें हर क्लॉज़ में ठीक तीन लिटरल होते हैं