Advanced Algorithms - parallel algorithms, approximation algorithms, randomized algorithms - One Line Questions

1. What is a 'cut' in the context of approximation algorithms for problems like Minimum Cut? — A partition of vertices into two sets.
2. Which of the following is a typical hardware component used for parallel processing? — A Graphics Processing Unit (GPU).
3. A 'probabilistic polynomial time' (BPP) algorithm is one that: — Runs in polynomial time and gives the correct answer with high probability.
4. The 'Monte Carlo' type of randomized algorithm: — May terminate with an incorrect answer, but its running time is bounded.
5. The 'Las Vegas' type of randomized algorithm: — Always terminates with the correct answer, but its running time is random.
6. Which of the following best describes a 'parallel algorithm'? — An algorithm that breaks down a problem into smaller parts that can be solved simultaneously by multiple processors.
7. What is a 'randomized approximation algorithm'? — An algorithm that uses randomness and guarantees an approximate solution.
8. In parallel computing, 'data parallelism' involves: — Applying the same operation to different subsets of data concurrently.
9. What is a common application of randomized algorithms in computer science? — Primality testing.
10. Karger's algorithm for Minimum Cut is an example of which type of algorithm? — Randomized algorithm.
11. Which of these algorithms is a well-known example of a randomized algorithm? — QuickSort (in its typical implementation).
12. Which of the following best describes 'task parallelism'? — Assigning different independent tasks to different processors.
13. The 'Traveling Salesperson Problem' (TSP) is famously known to be: — An NP-hard problem for which approximation algorithms are often used.
14. What is the main challenge in implementing parallel algorithms for distributed systems? — Managing network latency and communication overhead.
15. In parallel algorithms, 'load balancing' refers to: — Distributing computational work evenly among processors to minimize idle time.
16. Which type of approximation algorithm provides a guarantee on the solution quality based on a parameter epsilon (ε)? — Approximation scheme (e.g., PTAS, FPTAS).
17. Which of the following is NOT a typical approach for designing approximation algorithms? — Dynamic programming (for exact solutions).
18. A 'fully polynomial-time approximation scheme' (FPTAS) for a problem P has an approximation ratio that: — Depends polynomially on the input size and the approximation factor.
19. What does it mean for a randomized algorithm to have a high probability of success? — It produces the correct answer with a probability greater than some threshold (e.g., 0.99).
20. What is the primary advantage of using a randomized algorithm over a deterministic one for certain problems? — It can achieve better average-case performance or a simpler design.
21. What does 'NP-hard' imply about a problem? — It is at least as hard as the hardest problems in NP.
22. A 'greedy' approach is often used in approximation algorithms. What characterizes a greedy algorithm? — It makes the locally optimal choice at each step with the hope of finding a global optimum.
23. Which of the following is a common challenge in designing parallel algorithms? — Load balancing across processors.
24. Which parallel programming model involves explicitly managing threads and their synchronization? — OpenMP (Open Multi-Processing).
25. In shared-memory parallel programming, what is a potential issue that needs careful management? — Deadlocks and race conditions.
26. Which statement best describes the relationship between parallel algorithms and approximation algorithms? — Both can be used independently or in combination to solve complex problems efficiently.
27. In parallel algorithms, 'synchronous' parallel computation means: — Processors must wait for each other at certain synchronization points.
28. The 'parallel random access machine' (PRAM) model is a theoretical model for parallel computation. It assumes: — Processors share a common memory and synchronize access.
29. Which type of parallel algorithm is designed to find a solution that is close to the optimal solution, especially for NP-hard problems? — Approximation algorithms.
30. A 'parallel algorithm' aims to improve performance primarily by: — Utilizing multiple processing units concurrently.
31. In the context of parallel algorithms, 'embarrassingly parallel' problems are those that: — Can be easily parallelized with little or no modification and minimal communication.
32. MPI (Message Passing Interface) is a standard for: — Distributed-memory parallel programming.
33. Which of these problems is a classic example where approximation algorithms are commonly used? — The Traveling Salesperson Problem (TSP).
34. Which of the following is a metric used to evaluate the performance of approximation algorithms? — Approximation ratio.
35. Which of the following is a common technique used in randomized algorithms? — Making choices based on probabilities.
36. Which parallel algorithm paradigm is suitable for problems that can be broken down into independent subproblems that are processed in parallel, and then their results are combined? — Data parallelism.
37. When designing an approximation algorithm for a minimization problem, a ratio of 1.5 means: — The approximate solution's cost is at most 1.5 times the cost of the optimal solution.
38. The 'Amdahl's Law' is a principle that limits the speedup achievable by parallelizing a task. It states that the speedup is limited by: — The sequential portion of the algorithm.
39. What is 'efficiency' in parallel algorithms? — The ratio of speedup to the number of processors.
40. What is the 'speedup' in the context of parallel algorithms? — The ratio of the time taken by the sequential algorithm to the time taken by the parallel algorithm.
41. What is the 'approximation ratio' of an approximation algorithm? — The ratio of the cost of the approximate solution to the cost of the optimal solution.
42. In the context of parallel algorithms, 'granularity' refers to: —
43. What is a key advantage of using approximation algorithms? — They are typically much faster than exact algorithms for NP-hard problems.
44. Which of the following is a characteristic of approximation algorithms for NP-hard problems? — They aim for solutions that are provably close to the optimal.
45. Which of the following is a potential drawback of randomized algorithms? — Their performance might vary between runs due to randomness.
46. What is the primary advantage of using approximation algorithms for NP-hard problems? — They offer a trade-off between solution quality and computation time.
47. What is the role of 'random seeds' in randomized algorithms? — To ensure reproducibility of results by initializing the random number generator.
48. What is the main purpose of using randomization in algorithms? — To achieve good average-case performance or to simplify algorithm design.
49. What is the primary goal of parallel algorithms from a performance perspective? — To reduce the time complexity by using multiple processing units.
50. What is the primary goal of parallel algorithms? — To execute parts of an algorithm simultaneously on multiple processors.
All One Line Questions
E-Book Advanced Algorithms - parallel algorithms, approximation algorithms, randomized algorithms Online Test Advanced Algorithms - parallel algorithms, approximation algorithms, randomized algorithms Question Bank Advanced Algorithms - parallel algorithms, approximation algorithms, randomized algorithms