PyQdeck LogoPyQdeckSubjectsSyllabusBlog
Back to the 2024 paper

Module 5: Advanced Topics

20242m

Randomized algorithms make use of:
(i) Deterministic input
(ii) Random choices during execution
(iii) Recursive backtracking
(iv) Fixed input-output pairs

Search GoogleAsk AI
Worked SolutionAI Assisted

Answer: (ii) Random choices during execution

Explanation:

  • Randomized algorithms use a random number generator to make decisions; behavior is probabilistic.
  • Types: Las Vegas (always correct, random running time, e.g., Randomized QuickSort) vs Monte Carlo (may be incorrect with bounded probability, e.g., Miller-Rabin primality).
  • Random choices help avoid worst-case inputs (Randomized QuickSort expected O(nlog⁡n)O(n \log n)) or achieve simplicity/probabilistic guarantees.

Correct choice: (ii)

Similar questions

Design and Analysis of Algorithms Answer the following: (i) Describe randomized algorithms. (ii) Write the algorithm for randomized quick sort. (iii) Give the time complexity of randomized quick sort.20247mDesign and Analysis of Algorithms Write the short note on the following: (a) Cook's theorm (b) Randomized algorithms (c) Bin Packing202314mDesign and Analysis of Algorithms In which algorithmic strategy are problems systematically divided into smaller subproblems until the solution to the original problem is found? (i) Brute-force (ii) Greedy (iii) Dynamic programming (iv) Backtracking20232mFormal Language & Automata TheoryWhich of the following pairs have DIFFERENT expressive powers? (i) Deterministic finite automata (DFA) and non-deterministic finite automata (NDFA) (ii) Deterministic push-down automata (DPDA) and non-deterministic push-down automata (NDPDA) (iii) Deterministic single-tape Turing machine and non-deterministic single-tape Turing machine (iv) Single-tape Turing machine and multi-tape Turing machine20222m
PreviousWhat is the primary technique used to prove that a problem is NP-complete? (i) Divide and conquer (ii) Dynamic programming (iii) Polynomial-time reduction from a known NP-complete problem (iv) Space complexity calculationNextAnswer the following: (i) Differentiate between best-case, worst-case, and average-case complexity with suitable examples. (ii) Use examples like linear search to demonstrate the differences. (iii) Discuss why worst-case analysis is often preferred in practice.
Official AppAndroid App

PYQDeck for Android

Solve BEU previous-year exam papers anywhere, anytime. Fast search, offline paper viewing, and step-by-step solutions designed specifically for your phone.

Get on Google Play