Algorithm Design Techniques: Master Divide-and-Conquer, Greedy, Dynamic Programming, Backtracking, and Branch-and-Bound

Question 1

Which of the following is NOT a fundamental algorithm design technique covered in this unit?

Accepted Answer

Breadth-first search

Answer

Divide-and-conquer

Answer

Greedy algorithms

Answer

Dynamic programming

Question 2

The divide-and-conquer technique involves:

Accepted Answer

Breaking a problem into smaller, solvable parts

Answer

Exploring all possible solutions

Answer

Guiding the search using heuristics

Answer

Iteratively improving a solution

Question 3

Which of the following is a benefit of using greedy algorithms?

Accepted Answer

Often computationally efficient

Answer

Guaranteed optimal solution

Answer

Can handle complex constraints

Answer

Always finds a feasible solution

Question 4

Dynamic programming is used when:

Accepted Answer

There are overlapping subproblems

Answer

The problem is NP-hard

Answer

The solution space is large

Answer

Heuristics are not applicable

Question 5

Which of the following is a limitation of backtracking?

Accepted Answer

Can lead to exponential time complexity

Answer

Does not guarantee optimality

Answer

Cannot handle constraints effectively

Answer

Requires a solution tree

Question 6

What is the underlying principle of dynamic programming?

Accepted Answer

Caching the solutions to overlapping subproblems

Answer

Breaking down the problem into smaller subproblems

Answer

Exploring alternative solutions

Answer

Bounding the search space

Question 7

Identify the most suitable technique for solving problems where subproblems overlap.

Accepted Answer

Dynamic Programming

Answer

Divide-and-Conquer

Answer

Greedy Algorithms

Answer

Backtracking

Question 8

Distinguish the key feature of dynamic programming from other algorithm design techniques.

Accepted Answer

Storing solutions to subproblems to prevent redundant calculations

Answer

Decomposing a problem into smaller subproblems

Answer

Exploring all possible solutions

Answer

Approximating the optimal solution

Question 9

Which algorithm design technique allows for iterative decision-making and potential revisiting of choices?

Accepted Answer

Backtracking

Answer

Divide-and-Conquer

Answer

Greedy Algorithms

Answer

Branch-and-Bound

Question 10

Identify a potential drawback of utilizing branch-and-bound algorithms.

Accepted Answer

Potential for computational intensiveness

Answer

Guarantee of finding the optimal solution

Answer

Ability to solve problems unsolvable by other techniques

Answer

Frequent provision of a close approximation of the optimal solution

Question 11

For a problem involving arranging n objects in a row, which algorithm design technique offers the highest efficiency?

Accepted Answer

Dynamic Programming

Answer

Divide-and-Conquer

Answer

Greedy Algorithms

Answer

Backtracking

Question 12

Describe the foundational principle underlying divide-and-conquer algorithms.

Accepted Answer

Decomposing a problem into smaller subproblems

Answer

Storing solutions to subproblems

Answer

Exploring all possible solutions

Answer

Approximating the optimal solution

Question 13

Determine the most appropriate algorithm design technique for finding the longest increasing subsequence within a sequence of numbers.

Accepted Answer

Dynamic Programming

Answer

Divide-and-Conquer

Answer

Greedy Algorithms

Answer

Backtracking

Question 14

Identify a potential shortcoming of greedy algorithms.

Accepted Answer

Tendency to make locally optimal choices that may lead to a globally suboptimal solution

Answer

Guarantee of finding the optimal solution

Answer

Requirement of a comprehensive understanding of the problem

Answer

High computational efficiency

Question 15

Which of the following is NOT a fundamental algorithm design technique?

Accepted Answer

Breadth-first search

Answer

Backtracking

Answer

Dynamic programming

Answer

Divide-and-conquer

Question 16

What is the core idea behind the divide-and-conquer algorithm design technique?

Accepted Answer

Decomposing a problem into smaller subproblems that can be solved recursively

Answer

Trying all possible solutions and selecting the best one

Answer

Iteratively approximating the optimal solution

Answer

Searching for a solution in a tree-like data structure

Question 17

What distinctive characteristic makes a problem suitable for a dynamic programming solution?

Accepted Answer

Optimal solutions to subproblems can be used to efficiently solve larger subproblems

Answer

The problem cannot be solved using other techniques

Answer

The optimal solution can be found in linear time

Answer

Subproblems are completely independent of each other

Question 18

How does branch-and-bound differ from backtracking?

Accepted Answer

Branch-and-bound uses bounds to guide the search and prune infeasible branches

Answer

Backtracking can find multiple solutions while branch-and-bound only finds one

Answer

Branch-and-bound is always more efficient than backtracking

Answer

Backtracking only allows for depth-first traversal

Question 19

What is the time complexity of a well-optimized implementation of Merge Sort?

Accepted Answer

O(n log n)

Answer

O(n^2)

Answer

O(log n)

Answer

O(n)

Question 20

What is the key difference between 'worst-case' and 'average-case' time complexity analyses?

Accepted Answer

Worst-case analysis assumes the worst possible input, while average-case analysis assumes a typical input

Answer

Average-case analysis is always more accurate than worst-case analysis

Answer

Average-case analysis is only applicable to iterative algorithms

Answer

Worst-case analysis is more optimistic than average-case analysis

Question 21

Which algorithm design technique is suitable for problems that can be recursively divided into smaller subproblems with optimal substructure?

Accepted Answer

Divide-and-Conquer

Answer

Greedy Algorithms

Answer

Backtracking

Answer

Dynamic Programming

Question 22

Which algorithm design technique stores optimal solutions to subproblems to avoid duplicate calculations and is suitable for problems with overlapping subproblems and optimal substructure?

Accepted Answer

Dynamic Programming

Answer

Divide-and-Conquer

Answer

Backtracking

Answer

Branch-and-Bound

Question 23

Which algorithm design technique systematically explores all possible solutions to find the optimal one, backtracking to try alternate solutions when necessary?

Accepted Answer

Backtracking

Answer

Dynamic Programming

Answer

Branch-and-Bound

Answer

Divide-and-Conquer

Question 24

Which algorithm design technique recursively explores a tree of possible solutions, backtracking when it reaches a dead end, and is typically used for combinatorial optimization problems?

Accepted Answer

Backtracking

Answer

Greedy Algorithms

Answer

Branch-and-Bound

Answer

Dynamic Programming

Question 25

Which algorithm design technique decomposes a problem into smaller subproblems, solves each subproblem recursively, and combines their solutions to solve the original problem?

Accepted Answer

Divide-and-conquer

Answer

Backtracking

Answer

Greedy algorithm

Answer

Dynamic programming

Question 26

Which algorithm design technique involves making locally optimal choices at each step in the hope of finding a globally optimal solution?

Accepted Answer

Greedy algorithm

Answer

Divide-and-conquer

Answer

Branch-and-bound

Answer

Dynamic programming

Question 27

Which algorithm design technique solves a problem by breaking it down into overlapping subproblems, storing the solutions to these subproblems, and reusing them when needed?

Accepted Answer

Dynamic programming

Answer

Backtracking

Answer

Divide-and-conquer

Answer

Greedy algorithm

Question 28

Which algorithm design technique systematically explores all possible solutions to a problem by backtracking through the search space?

Accepted Answer

Backtracking

Answer

Dynamic programming

Answer

Greedy algorithm

Answer

Divide-and-conquer

Question 29

Which of the following is a common reason for using a greedy algorithm?

Accepted Answer

When finding an optimal solution is computationally intractable (NP-hard).

Answer

When the problem involves overlapping subproblems.

Answer

When the problem is recursive in nature.

Answer

When the solution space can be systematically explored.

Question 30

Which of the following is a key principle of dynamic programming?

Accepted Answer

Optimal substructure: An optimal solution to a subproblem can be used to construct an optimal solution to the original problem.

Answer

Divide the problem into smaller, independent subproblems.

Question 31

Which algorithm design technique is well-suited for problems where we need to find a subset of elements from a set that satisfies certain constraints?

Accepted Answer

Backtracking

Answer

Greedy algorithm

Answer

Dynamic programming

Answer

Divide-and-conquer

Question 32

Which algorithm design technique divides a problem into smaller, independent subproblems and solves them recursively?

Accepted Answer

Divide-and-Conquer

Answer

Greedy Algorithm

Answer

Dynamic Programming

Answer

Backtracking

Question 33

A distinctive feature of a greedy algorithm is that it:

Accepted Answer

Makes locally optimal choices without considering the global impact.

Answer

Requires exponential time complexity.

Answer

Guarantees an optimal solution for all problem instances.

Question 34

When should you consider using dynamic programming?

Accepted Answer

When a problem exhibits overlapping subproblems that are solved repeatedly.

Answer

When the problem requires a brute-force approach.

Answer

When the problem can be broken down into independent subproblems.

Question 35

What is the primary purpose of backtracking in algorithm design?

Accepted Answer

To explore all possible solutions by systematically trying different combinations.

Answer

To ensure an optimal solution.

Answer

To reduce the time complexity of the algorithm.

Question 36

Which algorithm design technique is particularly well-suited for optimization problems with constraints?

Accepted Answer

Branch-and-Bound

Answer

Dynamic Programming

Answer

Divide-and-Conquer

Answer

Greedy Algorithm

Question 37

When designing an efficient divide-and-conquer algorithm, what is a crucial consideration?

Accepted Answer

Establishing a base case to terminate the recursion

Answer

Ignoring the overhead of recursion

Answer

Using a large recursion depth

Answer

Making unnecessary recursive calls

Question 38

In dynamic programming, what is the purpose of a memoization table?

Accepted Answer

To store results of previous computations to avoid redundant calculations

Answer

To track the progress of the algorithm

Answer

To check if the problem has been solved earlier

Question 39

Which of the following algorithms is a classic example of Divide-and-Conquer technique?

Accepted Answer

Merge Sort

Answer

Dijkstra's Algorithm

Answer

Naive String Matching

Answer

Breadth-First Search

Question 40

Backtracking algorithms are particularly suited for problems with:

Accepted Answer

Large solution spaces

Answer

Small solution spaces

Answer

Guaranteed optimal solutions

Question 41

Which of the following algorithms is an example of Branch-and-Bound technique?

Accepted Answer

Knapsack Problem

Answer

Prim's Algorithm

Answer

Minimum Spanning Tree

Answer

Floyd-Warshall Algorithm

Question 42

A heuristic is used in an algorithm to:

Accepted Answer

Find a good approximate solution quickly

Answer

Reduce the time complexity to linear

Answer

Guarantee the optimal solution

Answer

Make the algorithm easier to implement

Question 43

Which of the following algorithms is an example of a metaheuristic?

Accepted Answer

Genetic Algorithm

Answer

Dijkstra's Algorithm

Answer

Breadth-First Search

Answer

Prim's Algorithm

Question 44

The fundamental difference between deterministic and non-deterministic algorithms is that:

Accepted Answer

Deterministic algorithms always produce the same output for the same input, while non-deterministic algorithms may not

Answer

Deterministic algorithms are faster than non-deterministic algorithms

Question 45

Which algorithm design technique involves breaking down a problem into smaller, similar subproblems, solving these subproblems recursively, and then combining their solutions to solve the original problem?

Accepted Answer

Divide-and-Conquer

Answer

Greedy Algorithm

Answer

Backtracking

Answer

Dynamic Programming

Question 46

Which of the following algorithms is NOT a greedy algorithm?

Accepted Answer

Bellman-Ford Algorithm

Answer

Kruskal's Algorithm

Answer

Dijkstra's Algorithm

Answer

Huffman Coding

Question 47

What is the primary goal of a backtracking algorithm?

Accepted Answer

To systematically explore all possible solutions, eliminating branches that cannot lead to a valid solution.

Answer

To find the optimal solution by making locally optimal choices.

Answer

To construct a solution step-by-step, making irreversible decisions at each stage.

Answer

To efficiently solve problems by breaking them down into overlapping subproblems.

Question 48

Which algorithm design technique is particularly well-suited for optimization problems, where the goal is to find the best solution within a large search space?

Accepted Answer

Branch-and-Bound

Answer

Greedy Algorithm

Answer

Divide-and-Conquer

Answer

Dynamic Programming

Question 49

Which algorithm design technique is often used in conjunction with other techniques to enhance their efficiency, such as pruning unnecessary search paths in backtracking or optimizing subproblem solutions in dynamic programming?

Accepted Answer

Branch-and-Bound

Answer

Divide-and-Conquer

Answer

Greedy Algorithm

Answer

Dynamic Programming

Question 50

When selecting an algorithm design technique, which factor is NOT a primary consideration?

Accepted Answer

The specific programming language used to implement the algorithm

Answer

The size and complexity of the input data

Answer

The desired time and space efficiency of the solution

Answer

The specific requirements of the problem to be solved