Algorithms Previous Year Questions

Explanation

Removing the condition means the bound O(f(n)) holds for all n, not only when g(n) holds. The result is the plain unconditional notation O(f(n)), often obtained using smoothness of f.शर्त हटाने का अर्थ है कि सीमा O(f(n)) सभी n के लिए लागू होती है, केवल तब नहीं जब g(n) लागू हो। परिणाम सामान्य शर्तरहित notation O(f(n)) है, जो अक्सर f की smoothness का उपयोग करके मिलता है।

Explanation

In Big-O, constant factors and lower-order terms are dropped because the dominant term decides growth for large n. The key calls this the ignorability property. For example, 3n² + 5n + 2 = O(n²).Big-O में स्थिर गुणक और निचले क्रम के पद हटा दिए जाते हैं क्योंकि बड़े n के लिए प्रमुख पद ही वृद्धि तय करता है। कुंजी इसे ignorability property कहती है। उदाहरण के लिए, 3n² + 5n + 2 = O(n²)।

Explanation

T(n) = 2T(n/2) + n splits the problem into 2 subproblems of half size and does linear extra work, which is divide and conquer (as in merge sort). In aT(n/b) + f(n) form, a = 2, b = 2, f(n) = n, giving Θ(n log n).T(n) = 2T(n/2) + n समस्या को आधे आकार की 2 उप-समस्याओं में बाँटता है और रैखिक अतिरिक्त कार्य करता है, जो divide and conquer है (जैसे merge sort में)। aT(n/b) + f(n) रूप में a = 2, b = 2, f(n) = n है, जिससे Θ(n log n) मिलता है।

Explanation

The Cook-Levin theorem (1971) proved Boolean Satisfiability (SAT) NP-complete. It was the first such problem, and others like TSP and Knapsack were later shown NP-complete by reduction from it.Cook-Levin प्रमेय (1971) ने Boolean Satisfiability (SAT) को NP-complete सिद्ध किया। यह ऐसी पहली समस्या थी, और TSP तथा Knapsack जैसी अन्य समस्याओं को बाद में इसी से reduction द्वारा NP-complete दिखाया गया।

Explanation

In a time-space tradeoff you usually use extra memory, for example lookup tables, caching or memoization, to make an algorithm run faster. Less time is bought with more space.Time-space tradeoff में आमतौर पर एल्गोरिदम को तेज़ चलाने के लिए अतिरिक्त मेमोरी, जैसे lookup tables, caching या memoization, का उपयोग किया जाता है। कम समय अधिक स्थान देकर खरीदा जाता है।

Explanation

Constant factors are ignored in Big-O: if f(n) = O(g(n)), then k·f(n) = O(g(n)) for any constant k > 0. This is the multiplication-by-constant rule.Big-O में स्थिर गुणक (constant factors) को छोड़ दिया जाता है: यदि f(n) = O(g(n)), तो किसी भी स्थिरांक k > 0 के लिए k·f(n) = O(g(n))। यह अचर से गुणा करने का नियम है।

Explanation

Merge sort always splits the array in half and merges in linear time: T(n) = 2T(n/2) + n = O(n log n) in the best, average and worst case.Merge sort हमेशा array को आधा बाँटता है और रैखिक समय में merge करता है: T(n) = 2T(n/2) + n = O(n log n), सर्वोत्तम, औसत और सबसे खराब, तीनों स्थितियों में।

Explanation

Musa's Basic Execution Time Model is a software reliability growth model that predicts failure intensity over execution time. FP and LOC measure size, and cyclomatic complexity measures control-flow complexity.Musa का Basic Execution Time Model एक software reliability growth मॉडल है जो निष्पादन समय के साथ विफलता की तीव्रता का अनुमान लगाता है। FP और LOC आकार मापते हैं, और cyclomatic complexity नियंत्रण-प्रवाह की जटिलता मापती है।

Explanation

Putnam's model (SLIM) uses the Rayleigh curve and the software equation to estimate development effort and development time (schedule) for large projects.Putnam का मॉडल (SLIM) बड़ी परियोजनाओं के लिए विकास प्रयास और विकास समय (schedule) का अनुमान लगाने हेतु Rayleigh curve और software equation का उपयोग करता है।

Explanation

Strictly, completeness means the algorithm can derive every entailed sentence, while being truth-preserving is soundness. The key combines both properties, describing an algorithm that is sound and complete.सख्ती से, completeness का अर्थ है कि एल्गोरिदम हर निहित (entailed) वाक्य निकाल सकता है, जबकि सत्य को बनाए रखना soundness है। कुंजी दोनों गुणों को मिलाकर ऐसे एल्गोरिदम का वर्णन करती है जो sound और complete हो।

Explanation

Per the key, this recurrence describes a problem broken into overlapping smaller subproblems (size n − 1), the pattern that dynamic programming targets. Solved naively, T(n) = 2T(n−1) + n grows as O(2ⁿ).कुंजी के अनुसार, यह recurrence एक ऐसी समस्या बताती है जो overlapping छोटी उप-समस्याओं (आकार n − 1) में बँटी है, यानी वह पैटर्न जिसे dynamic programming हल करता है। सीधे हल करने पर T(n) = 2T(n−1) + n का मान O(2ⁿ) के रूप में बढ़ता है।

Explanation

Transitivity means if i can reach k and k can reach j, then i can reach j. Floyd-Warshall and transitive closure use this to find reachability between vertex pairs.Transitivity का अर्थ है कि यदि i से k तक और k से j तक पहुँचा जा सकता है, तो i से j तक भी पहुँचा जा सकता है। Floyd-Warshall और transitive closure इसी का उपयोग करके शीर्ष-युग्मों के बीच पहुँच (reachability) निकालते हैं।

Explanation

Counting sort runs in O(n + k), where k is the range of key values, so it is efficient only when that range is small compared with n.Counting sort O(n + k) में चलता है, जहाँ k कुंजी-मानों की सीमा है, इसलिए यह तभी कारगर है जब वह सीमा n की तुलना में छोटी हो।

Explanation

DFS stores only the current path and its unexplored siblings, O(bm) memory, whereas BFS must keep a whole frontier, O(bᵈ).DFS केवल वर्तमान रास्ता और उसके अनदेखे भाई-नोड रखता है, यानी O(bm) मेमोरी, जबकि BFS को पूरी frontier रखनी पड़ती है, यानी O(bᵈ)।

Explanation

Conditional asymptotic notation states a bound that holds only under a condition. "Θ(f(n)) if g(n)" means the running time is tightly bounded by f(n) whenever condition g(n) is true (for example, n being a power of 2).Conditional asymptotic notation ऐसी सीमा बताता है जो केवल किसी शर्त में लागू होती है। "Θ(f(n)) if g(n)" का अर्थ है कि जब शर्त g(n) सत्य हो (जैसे n का 2 की घात होना) तो चलने का समय f(n) से कसकर बँधा है।

Explanation

A* is an informed best-first search. It expands the node with the lowest f(n) = g(n) + h(n), which combines the path cost so far with a heuristic estimate.A* सूचित best-first खोज है। वह सबसे कम f(n) = g(n) + h(n) वाले नोड को विस्तारित करती है, जो अब तक की पथ लागत और heuristic अनुमान को जोड़ता है।

Explanation

DIKSHA is the Government of India's digital learning platform for school teachers and students, not a search engine. Google, Bing and Yahoo are search engines.DIKSHA भारत सरकार का स्कूल शिक्षकों और विद्यार्थियों के लिए डिजिटल अधिगम मंच है, सर्च इंजन नहीं। Google, Bing और Yahoo सर्च इंजन हैं।

Explanation

Dijkstra first proposed the idea behind monitors (his "secretary" concept). Hoare and Brinch Hansen later formalised it. Among the options given, Dijkstra is the one linked to the concept. Turing, Berners-Lee and Torvalds have no connection to it.Monitors के पीछे का विचार सबसे पहले Dijkstra ने (अपनी "secretary" अवधारणा में) प्रस्तावित किया। बाद में Hoare और Brinch Hansen ने उसे औपचारिक रूप दिया। दिए गए विकल्पों में Dijkstra इस अवधारणा से जुड़े हैं। Turing, Berners-Lee और Torvalds का इससे कोई संबंध नहीं।

Explanation

Delphi (expert consensus) and COCOMO (an algorithmic model based on lines of code) are both techniques for estimating software development cost and effort.Delphi (विशेषज्ञ सहमति) और COCOMO (लाइन्स ऑफ कोड पर आधारित एल्गोरिदमिक मॉडल) दोनों सॉफ़्टवेयर विकास की लागत और प्रयास के आकलन की तकनीकें हैं।

Explanation

When asked for all solutions, backtracking records each feasible 8-Queens placement it finds and then keeps backtracking to search for more. There are 92 solutions in total.सभी हल माँगे जाने पर backtracking मिले हर संभव 8-Queens विन्यास को दर्ज करता है और फिर और खोजने के लिए backtrack करता रहता है। कुल 92 हल हैं।

Explanation

Insertion sort makes about n²/2 comparisons and shifts on reverse-sorted input, so its worst case is O(n²). Merge sort is O(n log n) and counting sort is O(n + k). Basic quick sort also has an O(n²) worst case, which makes the question loose.Insertion sort उलटे क्रम के इनपुट पर लगभग n²/2 तुलनाएँ और खिसकाव करती है, इसलिए उसका सबसे बुरा मामला O(n²) है। Merge sort O(n log n) और counting sort O(n + k) है। साधारण quick sort का भी सबसे बुरा मामला O(n²) है, जिससे प्रश्न ढीला है।

Explanation

Musa's basic execution time model is a software reliability growth model. It predicts failure intensity and reliability as faults are removed during testing.Musa का basic execution time model एक सॉफ़्टवेयर विश्वसनीयता वृद्धि मॉडल है। यह टेस्टिंग में दोष हटने के साथ विफलता तीव्रता और विश्वसनीयता का अनुमान लगाता है।

Explanation

The cut property says that for any cut of the graph, the minimum-weight edge crossing that cut belongs to some MST. Prim's algorithm always picks the lightest edge crossing from the tree to the rest, so it is correct.Cut property कहती है कि ग्राफ़ के किसी भी cut को पार करने वाला न्यूनतम भार का एज किसी न किसी MST में होता है। Prim का एल्गोरिदम हमेशा पेड़ से बाकी की ओर जाने वाला सबसे हल्का एज चुनता है, इसलिए वह सही है।

Explanation

Algorithm analysis estimates the resources an algorithm needs, mainly its running time (time complexity) and memory (space complexity), as a function of the input size.Algorithm analysis इनपुट आकार के फ़ंक्शन के रूप में एल्गोरिदम को चाहिए संसाधनों का अनुमान लगाती है, मुख्यतः चलने का समय (time complexity) और मेमोरी (space complexity)।

Explanation

The question is garbled. The intended idea is that once the extra condition on g(n) is dropped, the bound is simply in terms of f(n), so the algorithm is o(f(n)).प्रश्न विकृत है। आशय यह है कि g(n) की अतिरिक्त शर्त हटने पर सीमा केवल f(n) के रूप में होती है, इसलिए एल्गोरिदम o(f(n)) है।

Explanation

The Church-Turing thesis says that any algorithm can be carried out by a Turing machine and vice versa, so a TM is both a model of algorithms and of a general-purpose computer.Church-Turing थीसिस कहती है कि कोई भी एल्गोरिदम Turing मशीन से चलाया जा सकता है और उलटा भी, इसलिए TM एल्गोरिदम और सामान्य-उद्देश्य कंप्यूटर दोनों का मॉडल है।

Explanation

The Turing Test, proposed by Alan Turing in 1950, checks whether a machine can show intelligent behaviour that cannot be told apart from a human's.1950 में Alan Turing द्वारा प्रस्तावित Turing Test जाँचता है कि क्या मशीन ऐसा बुद्धिमान व्यवहार दिखा सकती है जो मनुष्य से अलग न पहचाना जाए।

Explanation

Bubble sort compares adjacent (neighbouring) elements and swaps them if they are in the wrong order. Selection and insertion sort compare across the list.Bubble sort आसन्न (पड़ोसी) तत्वों की तुलना करती है और क्रम गलत हो तो अदला-बदली करती है। Selection और insertion sort सूची में दूर तक तुलना करती हैं।

Explanation

LOC stands for Lines of Code, a size metric used to estimate effort and cost in software projects.LOC का अर्थ Lines of Code है, जो सॉफ़्टवेयर परियोजनाओं में प्रयास और लागत के अनुमान के लिए उपयोग होने वाला आकार मापक है।

Explanation

DFS keeps only the current path (plus unexplored siblings) on its stack, so it needs O(bd) memory. BFS must store the whole frontier level, which grows exponentially.DFS अपने स्टैक पर केवल मौजूदा पथ (और अनदेखे सहोदर) रखता है, इसलिए उसे O(bd) मेमोरी चाहिए। BFS को पूरा frontier स्तर रखना पड़ता है, जो चरघातांकी रूप से बढ़ता है।

Explanation

NP is the class of decision problems whose proposed solution (certificate) can be verified in polynomial time by a deterministic machine. Equivalently, they are solvable in polynomial time by a non-deterministic machine.NP उन निर्णय समस्याओं का वर्ग है जिनका प्रस्तावित हल (certificate) एक deterministic मशीन polynomial समय में जाँच सकती है। समतुल्य रूप से, वे non-deterministic मशीन से polynomial समय में हल हो जाती हैं।

Explanation

Hill climbing keeps moving to a better neighbour and stops when no neighbouring state has a higher value. That point may only be a local maximum, not the global one.Hill climbing बेहतर पड़ोसी की ओर बढ़ता रहता है और तब रुकता है जब किसी पड़ोसी अवस्था का मान अधिक न हो। वह बिंदु केवल local maximum हो सकता है, global नहीं।

Explanation

RFID modules such as the RC522 use the SPI bus, where MISO means Master In Slave Out: the line on which the slave sends data to the master.RC522 जैसे RFID मॉड्यूल SPI बस का उपयोग करते हैं, जहाँ MISO का अर्थ Master In Slave Out है: वह लाइन जिस पर slave, master को डेटा भेजता है।

Explanation

Each half returns its own max and min; the overall max is the larger of the two maxima and the overall min is the smaller of the two minima, costing 2 comparisons per combine.हर आधा हिस्सा अपना max और min लौटाता है; कुल max दोनों max में बड़ा और कुल min दोनों min में छोटा होता है, और हर मेल पर 2 तुलनाएँ लगती हैं।

Explanation

A tradeoff means giving up some of one resource (for example memory) to gain in another (for example speed). Greedy, divide-and-conquer and DP are algorithm design paradigms, not this strategy.Tradeoff का अर्थ है एक संसाधन (जैसे मेमोरी) का कुछ हिस्सा छोड़कर दूसरे (जैसे गति) में लाभ पाना। Greedy, divide-and-conquer और DP एल्गोरिथ्म डिज़ाइन के प्रतिमान हैं, यह रणनीति नहीं।

Explanation

Conditional asymptotic notation gives a bound that holds only under a condition on n or the input (for example n a power of 2). It helps when an algorithm's behaviour depends on such input characteristics.Conditional asymptotic notation ऐसी सीमा देता है जो केवल n या इनपुट पर किसी शर्त (जैसे n का 2 की घात होना) में लागू होती है। यह तब उपयोगी है जब एल्गोरिथ्म का व्यवहार ऐसे इनपुट गुणों पर निर्भर करता है।

Explanation

Once the condition is dropped and the bound still holds generally, the conditional statement "o(f(n)) if g(n)" just becomes o(f(n)). The bound function stays f(n).जब शर्त हटा दी जाती है और सीमा फिर भी सामान्य रूप से सही रहती है, तो सशर्त कथन "o(f(n)) if g(n)" केवल o(f(n)) बन जाता है। सीमा फलन f(n) ही रहता है।

Explanation

T(n) = T(n/2) + 1 halves the problem at each step, as in binary search, a divide-and-conquer algorithm. It solves to O(log n).T(n) = T(n/2) + 1 हर चरण में समस्या को आधा कर देता है, जैसे binary search में, जो एक divide-and-conquer एल्गोरिथ्म है। इसका हल O(log n) है।

Explanation

Divide and conquer splits a problem into smaller subproblems of the same type, solves them recursively, and then combines their solutions (for example merge sort or quick sort).Divide and conquer किसी समस्या को उसी प्रकार की छोटी उप-समस्याओं में बाँटता है, उन्हें रिकर्सिवली हल करता है और फिर उनके हल जोड़ता है (जैसे merge sort या quick sort)।

Explanation

RFID modules such as the RC522 talk over SPI. On the MISO (Master In Slave Out) pin, the module (slave) sends data to the microcontroller (master).RC522 जैसे RFID मॉड्यूल SPI पर संवाद करते हैं। MISO (Master In Slave Out) पिन पर मॉड्यूल (slave) माइक्रोकंट्रोलर (master) को डेटा भेजता है।