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

एल्गोरिदम क्या है?

1. Aग्राफ़िकल इंटरफ़ेस वाला कोई भी कंप्यूटर प्रोग्राम
2. Bसंख्याएँ संग्रहीत करने वाली एक डेटा संरचना
3. Cगणितीय सूत्र लिखने के लिए बनाई गई एक प्रोग्रामिंग भाषा
4. Dसुपरिभाषित चरणों का एक सीमित अनुक्रम जो किसी समस्या को हल करता है

मर्ज सॉर्ट की वर्स्ट-केस टाइम कॉम्प्लेक्सिटी क्या है?

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

मर्ज सॉर्ट कौन-सी डिज़ाइन रणनीति का उपयोग करता है?

1. Aग्रीडी चयन
2. Bब्रूट फ़ोर्स
3. Cडायनेमिक प्रोग्रामिंग
4. Dडिवाइड एंड कॉन्कर (विभाजन और विजय)

आप n तत्वों का ऐरे एक बार सॉर्ट करते हैं और फिर बाइनरी सर्च से k सदस्यता प्रश्नों के उत्तर देते हैं। कुल लागत क्या है?

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

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

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

बॉटम-अप तालिका से n-वीं फ़िबोनाची संख्या की गणना की टाइम कॉम्प्लेक्सिटी क्या है?

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

सॉर्टेड ऐरे में किसी भी तुलना-आधारित खोज को वर्स्ट केस में Ω(log n) तुलनाएँ क्यों चाहिए?

1. Aबाइनरी सर्च ही एकमात्र संभव एल्गोरिदम है, और उसे log₂ n तुलनाएँ चाहिए
2. Bn संभावित परिणामों वाले निर्णय वृक्ष (decision tree) की गहराई कम से कम log₂ n होनी चाहिए
3. Cहर तत्व की कम से कम एक बार तुलना होनी चाहिए
4. Dहर तुलना में लघुगणकीय समय लगता है

P और NP के बारे में कौन-सा कथन सही है?

1. Aयह सिद्ध हो चुका है कि P ≠ NP
2. BP की हर समस्या NP में भी है
3. CNP समस्याओं को जल्दी सत्यापित नहीं किया जा सकता
4. DNP का अर्थ है "not polynomial"