Algorithm Concepts Quiz L2

Which of the following describes a simple recursive algorithm?

• Solves complex problems without any base cases.

• Directly solves base cases, recurses with a simpler subproblem, and does extra work to convert the solution.

• Requires multiple recursive calls to be classified as divide and conquer.

• Always guarantees an optimal solution.

In a backtracking algorithm, what does the algorithm do when it finds a solution?

• Returns failure immediately.

• Ignores the solution and continues searching.

• Tests to see if a solution has been found, and if so, returns it.

• Stops all processing.

Which of the following is NOT a characteristic of divide and conquer algorithms?

• The problem is divided into smaller subproblems.

• The algorithm typically has at least two recursive calls.

• Subproblems can overlap and are reused.

• Solutions to subproblems are combined to solve the original problem.

What is a defining feature of dynamic programming algorithms?

• They always solve problems in linear time.

• They use a brute-force approach to find solutions.

• They store past results to avoid redundant calculations.

• They require multiple solutions to exist.

A greedy algorithm aims to:

• Find the best solution after considering all possibilities.

• Make the best choice at each step without regard for future consequences.

• Always guarantee an optimal solution.

• Use complex data structures to keep track of choices.

Which of the following examples illustrates a failure of a greedy algorithm?

• Choosing the largest coin denomination to make change.

• Finding the shortest path using Dijkstra's algorithm.

• Using a 10 kron piece and five 1 kron pieces to make 15 krons.

• Using dynamic programming to solve the knapsack problem.

In a branch and bound algorithm, what does the tree represent?

• The different states of a game being played.

• The different possibilities to explore for a solution.

• The optimal solution path only.

• The upper and lower bounds of solutions only.

What is the main goal of a brute force algorithm?

• To find the best solution efficiently.

• To use random numbers for decision-making.

• To exhaustively try all possibilities until a satisfactory solution is found.

• To optimize performance by avoiding calculations.

What differentiates a randomized algorithm from other types?

• It requires precise calculations for all possible outcomes.

• It uses randomness at least once during computation to make a decision.

• It guarantees the same result each time it is run.

• It cannot be used for optimization problems.

What is the primary purpose of classifying algorithms based on their problem-solving approaches?

• To exhaustively categorize every algorithm into a single type.

• To highlight the various ways in which a problem can be attacked.

• To determine which algorithms are the fastest.

• To create a hierarchical structure for all known algorithms.