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

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

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

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

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

f(n) = Θ(g(n)) का क्या अर्थ है?

1. Aहर n के लिए f हमेशा g से छोटा है, इसलिए g उसे ऊपर से सीमित करता है पर नीचे से कभी नहीं
2. Bf, g से सख़्ती से तेज़ बढ़ता है
3. Cf, g की ही दर से बढ़ता है, और ऊपर व नीचे दोनों ओर g के स्थिर गुणजों से सीमित है
4. Df, g से सख़्ती से धीमा बढ़ता है

रिकरेंस T(n) = T(n − 1) + O(1) का हल क्या है?

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

for i = 1 to n: for j = 1 to i: O(1) कार्य करें — इसकी टाइम कॉम्प्लेक्सिटी क्या है?

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

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

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

नैपसैक के किस रूप के लिए ग्रीडी नियम "वस्तुओं को प्रति भार मूल्य के क्रम में लें" हमेशा इष्टतम उत्तर देता है?

1. Aदोनों रूप
2. Bकोई भी रूप नहीं
3. C0/1 नैपसैक, जिसमें वस्तुएँ हमेशा पूरी ली जानी चाहिए
4. Dफ़्रैक्शनल नैपसैक, जिसमें वस्तुएँ बाँटी जा सकती हैं

कौन-सी तकनीक किसी भी इनपुट पर क्विकसॉर्ट को अपेक्षित (expected) O(n log n) रनिंग टाइम देती है?

1. Aहमेशा पहला तत्व चुनना
2. Bक्विकसॉर्ट चलाने से पहले इनपुट को सॉर्ट करना
3. Cपिवट को समान रूप से यादृच्छिक (uniformly at random) चुनना
4. Dकेवल बाईं ओर रिकर्शन का उपयोग करना