TRB PG Assistant - Advanced Algorithms - parallel algorithms, approximation algorithms, randomized algorithms Online Test (MCQ Quiz)

1. What is the primary goal of parallel algorithms?

A) To reduce the number of operations in an algorithm. B) To execute parts of an algorithm simultaneously on multiple processors. C) To find an exact solution for NP-hard problems. D) To minimize the memory usage of an algorithm.

2. Which of the following is a common challenge in designing parallel algorithms?

A) Load balancing across processors. B) Minimizing the number of comparisons. C) Ensuring data integrity in a sequential system. D) Maximizing the use of a single CPU core.

3. In the context of parallel algorithms, 'granularity' refers to:

A) The size of the data being processed. B) The number of processors available. C) The size of the individual tasks assigned to processors. D) The communication overhead between processors.

4. Which parallel programming model involves explicitly managing threads and their synchronization?

A) Message Passing Interface (MPI). B) OpenMP (Open Multi-Processing). C) CUDA (Compute Unified Device Architecture). D) MapReduce.

5. The 'Amdahl's Law' is a principle that limits the speedup achievable by parallelizing a task. It states that the speedup is limited by:

A) The number of available processors. B) The sequential portion of the algorithm. C) The communication latency between processors. D) The memory bandwidth.

6. Which type of parallel algorithm is designed to find a solution that is close to the optimal solution, especially for NP-hard problems?

A) Randomized algorithms. B) Deterministic algorithms. C) Approximation algorithms. D) Distributed algorithms.

7. What is the 'approximation ratio' of an approximation algorithm?

A) The ratio of the time taken by the approximation algorithm to the time taken by the optimal algorithm. B) The ratio of the size of the input to the size of the output. C) The ratio of the cost of the approximate solution to the cost of the optimal solution. D) The probability of finding a correct solution.

8. Which of these problems is a classic example where approximation algorithms are commonly used?

A) Sorting an array. B) Finding the shortest path in a DAG. C) The Traveling Salesperson Problem (TSP). D) Searching for an element in a sorted array.

9. A 'greedy' approach is often used in approximation algorithms. What characterizes a greedy algorithm?

A) It explores all possible solutions before making a choice. B) It makes the locally optimal choice at each step with the hope of finding a global optimum. C) It uses random choices to explore the solution space. D) It guarantees finding the exact optimal solution.

10. What is a key advantage of using approximation algorithms?

A) They always find the exact optimal solution. B) They are typically much faster than exact algorithms for NP-hard problems. C) They require significantly less memory than exact algorithms. D) They are easier to implement than deterministic algorithms.

11. Which of the following is a common technique used in randomized algorithms?

A) Systematic exploration of all possibilities. B) Making choices based on probabilities. C) Finding the locally optimal choice at each step. D) Backtracking to previous states.

12. What does it mean for a randomized algorithm to have a high probability of success?

A) It always produces the correct answer. B) It produces the correct answer with a probability greater than some threshold (e.g., 0.99). C) It is guaranteed to be faster than any deterministic algorithm. D) It uses a fixed sequence of random numbers.

13. The 'Las Vegas' type of randomized algorithm:

A) Always terminates with the correct answer, but its running time is random. B) May terminate with an incorrect answer, but its running time is deterministic. C) Always terminates with the correct answer and has a deterministic running time. D) Never terminates but provides a correct answer eventually.

14. The 'Monte Carlo' type of randomized algorithm:

A) Always terminates with the correct answer and has a deterministic running time. B) May terminate with an incorrect answer, but its running time is bounded. C) Always terminates with the correct answer, but its running time is random. D) Never terminates but provides a correct answer eventually.

15. Which of these algorithms is a well-known example of a randomized algorithm?

A) Dijkstra's algorithm for shortest paths. B) QuickSort (in its typical implementation). C) Binary Search. D) Bubble Sort.

16. In parallel algorithms, 'synchronous' parallel computation means:

A) Processors can operate independently at their own pace. B) Processors must wait for each other at certain synchronization points. C) Processors communicate only through shared memory. D) Processors execute tasks in a strictly sequential order.

17. Which of the following is a typical hardware component used for parallel processing?

A) A single CPU core. B) A Graphics Processing Unit (GPU). C) A Hard Disk Drive (HDD). D) A standard keyboard.

18. What is the 'speedup' in the context of parallel algorithms?

A) The ratio of the number of operations in the parallel algorithm to the sequential algorithm. B) The ratio of the time taken by the sequential algorithm to the time taken by the parallel algorithm. C) The reduction in memory usage achieved by parallelization. D) The increase in the number of tasks executed per unit time.

19. What is 'efficiency' in parallel algorithms?

A) The ratio of speedup to the number of processors. B) The total work done by the parallel algorithm divided by the time taken. C) The percentage of time processors are actively computing. D) The ratio of optimal solution cost to approximate solution cost.

20. Which of the following is NOT a typical approach for designing approximation algorithms?

A) Greedy algorithms. B) Linear programming relaxation. C) Randomized selection. D) Dynamic programming (for exact solutions).

21. What is a 'randomized approximation algorithm'?

A) An algorithm that uses randomness and guarantees an approximate solution. B) An algorithm that uses randomness and guarantees the optimal solution. C) An algorithm that uses randomness and may not terminate. D) An algorithm that deterministically finds an approximate solution.

22. 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?

A) Task parallelism. B) Data parallelism. C) Pipeline parallelism. D) Shared memory parallelism.

23. In shared-memory parallel programming, what is a potential issue that needs careful management?

A) Message passing overhead. B) Deadlocks and race conditions. C) Network latency. D) Limited number of threads.

24. MPI (Message Passing Interface) is a standard for:

A) Shared-memory parallel programming. B) Distributed-memory parallel programming. C) GPU computing. D) Asynchronous computation.

25. What is a 'cut' in the context of approximation algorithms for problems like Minimum Cut?

A) A path between two vertices. B) A partition of vertices into two sets. C) A cycle in the graph. D) A bridge in the graph.

26. Karger's algorithm for Minimum Cut is an example of which type of algorithm?

A) Deterministic approximation algorithm. B) Randomized algorithm. C) Greedy algorithm. D) Dynamic programming algorithm.

27. What is the primary advantage of using approximation algorithms for NP-hard problems?

A) They provide a guaranteed optimal solution in polynomial time. B) They offer a trade-off between solution quality and computation time. C) They are always faster than any exact algorithm, regardless of problem size. D) They reduce the memory requirements to constant space.

28. Which of the following best describes 'task parallelism'?

A) Dividing the data into smaller chunks and processing them simultaneously. B) Assigning different independent tasks to different processors. C) Executing a sequence of operations on a single stream of data. D) Distributing computations across multiple machines in a network.

29. In parallel algorithms, 'load balancing' refers to:

A) Ensuring that all processors have the same amount of data. B) Distributing computational work evenly among processors to minimize idle time. C) Minimizing the communication between processors. D) Maximizing the sequential portion of the algorithm.

30. Which of the following is a metric used to evaluate the performance of approximation algorithms?

A) Speedup. B) Efficiency. C) Approximation ratio. D) Granularity.

31. A 'fully polynomial-time approximation scheme' (FPTAS) for a problem P has an approximation ratio that:

A) Is constant. B) Depends polynomially on the input size and the approximation factor. C) Is exponential in the approximation factor. D) Is independent of the input size.

32. What is the main purpose of using randomization in algorithms?

A) To guarantee an exact solution for NP-hard problems. B) To achieve good average-case performance or to simplify algorithm design. C) To eliminate the need for any input data. D) To ensure deterministic execution time.

33. Which statement best describes the relationship between parallel algorithms and approximation algorithms?

A) Parallel algorithms are always approximation algorithms. B) Approximation algorithms are a type of parallel algorithm. C) Both can be used independently or in combination to solve complex problems efficiently. D) Parallel algorithms are only used for exact solutions, while approximation algorithms are for inexact solutions.

34. In the context of parallel algorithms, 'embarrassingly parallel' problems are those that:

A) Require significant communication between processors. B) Can be easily parallelized with little or no modification and minimal communication. C) Are inherently sequential and cannot be parallelized. D) Require complex synchronization mechanisms.

35. What is a common application of randomized algorithms in computer science?

A) Data compression. B) Network routing. C) Primality testing. D) Database indexing.

36. When designing an approximation algorithm for a minimization problem, a ratio of 1.5 means:

A) The approximate solution is always 1.5 times smaller than the optimal. B) The approximate solution's cost is at most 1.5 times the cost of the optimal solution. C) The algorithm runs 1.5 times faster than the optimal algorithm. D) The algorithm has a 1.5% chance of failure.

37. Which of the following is a potential drawback of randomized algorithms?

A) They always produce incorrect results. B) Their performance might vary between runs due to randomness. C) They require significantly more memory than deterministic algorithms. D) They are only applicable to trivial problems.

38. What is the primary goal of parallel algorithms from a performance perspective?

A) To increase the accuracy of results. B) To reduce the time complexity by using multiple processing units. C) To decrease the memory footprint of computations. D) To simplify the logic of complex algorithms.

39. The 'parallel random access machine' (PRAM) model is a theoretical model for parallel computation. It assumes:

A) Processors communicate via message passing. B) Processors share a common memory and synchronize access. C) Processors have independent memory and communicate asynchronously. D) Processors operate in a strictly sequential manner.

40. Which type of approximation algorithm provides a guarantee on the solution quality based on a parameter epsilon (ε)?

A) Greedy algorithm. B) Randomized algorithm. C) Approximation scheme (e.g., PTAS, FPTAS). D) Heuristic algorithm.

41. What is the main challenge in implementing parallel algorithms for distributed systems?

A) Ensuring processor synchronization. B) Managing network latency and communication overhead. C) Minimizing the number of computations. D) Avoiding redundant calculations.

42. A 'probabilistic polynomial time' (BPP) algorithm is one that:

A) Always runs in polynomial time and always gives the correct answer. B) Runs in polynomial time and gives the correct answer with high probability. C) May run in exponential time but always gives the correct answer. D) Runs in polynomial time but may give an incorrect answer.

43. What is the role of 'random seeds' in randomized algorithms?

A) To determine the exact solution. B) To ensure reproducibility of results by initializing the random number generator. C) To increase the complexity of the algorithm. D) To guarantee a faster execution time.

44. Which of the following is a characteristic of approximation algorithms for NP-hard problems?

A) They always find the exact optimal solution. B) They aim for solutions that are provably close to the optimal. C) They are typically slower than exact algorithms. D) They require specialized parallel hardware.

45. In parallel computing, 'data parallelism' involves:

A) Applying the same operation to different subsets of data concurrently. B) Executing different operations on the same data concurrently. C) Breaking down a task into sequential steps executed by different processors. D) Using a single processor to process all data.

46. The 'Traveling Salesperson Problem' (TSP) is famously known to be:

A) Easily solvable in polynomial time. B) An NP-hard problem for which approximation algorithms are often used. C) A problem solvable efficiently with dynamic programming. D) A problem that has no known algorithmic solution.

47. What is the primary advantage of using a randomized algorithm over a deterministic one for certain problems?

A) It always provides a more accurate solution. B) It can achieve better average-case performance or a simpler design. C) It guarantees a faster execution time in all cases. D) It requires less memory.

48. Which of the following best describes a 'parallel algorithm'?

A) An algorithm designed to run on a single processor with optimal efficiency. B) An algorithm that breaks down a problem into smaller parts that can be solved simultaneously by multiple processors. C) An algorithm that finds an approximate solution to a complex problem. D) An algorithm that uses random choices to find a solution.

49. What does 'NP-hard' imply about a problem?

A) It can be solved efficiently by a deterministic algorithm. B) It is at least as hard as the hardest problems in NP. C) It can be solved efficiently by a randomized algorithm. D) It can always be approximated within a constant factor.

50. A 'parallel algorithm' aims to improve performance primarily by:

A) Reducing the number of operations. B) Minimizing memory access. C) Utilizing multiple processing units concurrently. D) Using probabilistic methods.

Advanced Algorithms - parallel algorithms, approximation algorithms, randomized algorithms - Online Test

Test Results