Computational Complexity and Algorithms Quiz

Why are faster exact algorithms for NP-complete problems important?

• They are easier to implement

• They prove that P=NP

• They can solve problems exactly in less time for certain instances

• They are not concerned with solution optimality

What does an approximation ratio signify in the context of approximation algorithms?

• The measure of how close the algorithm's solution is to the optimal one

• The number of approximations made during the algorithm's execution

• The amount of time it takes to approximate a solution

• The probability that the algorithm will find the optimal solution

What is a reduction in the context of computational complexity?

• Minimizing resource usage in a computation

• Transforming one problem into another to prove complexity

• Reducing the time complexity of an algorithm

• Optimizing an algorithm for better performance

When constructing a minimum spanning tree, what determines the set of edges to be used?

• The edges chosen randomly.

• The edges with the lowest cost that do not form a cycle.

• The edges with the highest cost.

• The edges with the most connections to other edges.

Prim’s algorithm is a modified version of which other well-known algorithm?

• Dijkstra’s algorithm

• Breadth-First Search algorithm

• Bellman-Ford algorithm

• Floyd-Warshall algorithm

Which step is not part of the process in a greedy algorithm approach?

• Backtracking to the previous decision if it was wrong.

• Starting with an empty solution set.

• Keeping an item if the current solution set is feasible.

• Adding an item to the solution set at each step.

What is the primary focus of a greedy algorithm at each step?

• Local optimality

• Minimizing the number of steps

• Both local and global optimality simultaneously

• Global optimality

Which of these is NOT a characteristic of local search algorithms?

• Based on iterative improvement

• Guaranteed to find a global optimum

• Often fast and simple

• Useful for large instances of problems

Why are local search algorithms used for NP-complete problems?

• They are easier to implement than other algorithms

• They can often find good solutions quickly for large instances

• They use less memory than other algorithms

• They always guarantee the optimal solution

When using a greedy algorithm to make change for a given amount, which strategy does it typically use?

• Selecting the largest denomination coin that does not exceed the remaining amount.

• Using the same denomination of coins throughout.

• Selecting the smallest denomination coin first.

• Randomly selecting coins until the amount is reached.