Complexity and Algorithm Long Quiz

are strategies used to find near-optimal

solutions to complex optimization problems where finding the exact

optimal solution is impractical or too costly.

They provide solutions that are close to the best possible one but in a

significantly shorter time.

Many problems are NP-hard (Non-deterministic Polynomial-

time Hard), meaning no efficient algorithm exists to find the

optimal solution in reasonable time.

• TRUE

• FALSE

Which of the following problems is considered NP-hard?

• Binary Search

• raveling Salesman Problem (TSP)

• Sorting Arrays

• Matrix Multiplication

Why might finding exact solutions not be feasible for NP-hard problems in real-world applications?

• They always provide incorrect solutions.

• Exact algorithms require exponential time, which is impractical for large datasets.

• They lack any approximation techniques.

• They can only solve small datasets.

In real-world applications, why are approximate solutions often preferred over exact solutions?

• They are always more accurate than exact solutions.

• Real-world problems typically have infinite solutions.

• Quick solutions that are "close enough" are sufficient for applications like logistics and scheduling.

• Exact solutions are illegal in some cases.

What is the main characteristic of the Greedy Approach in approximation algorithms?

• It considers the entire problem before making any choices.

• It makes a series of choices that seem best at the moment.

• It swaps the order of elements to optimize the solution.

• It works by maintaining dual solutions.

Which example illustrates the Greedy Approach?

• Choosing the item with the highest value-to-weight ratio in the Knapsack problem.

• Swapping the order of two cities in the Traveling Salesman Problem (TSP).

• Using primal and dual solutions in network design.

• Randomly generating solutions for complex problems.

What does the Primal-Dual Method involve?

• Starting with a single solution and refining it locally.

• Maintaining and improving two sets of solutions (primal and dual).

• Selecting globally optimal solutions immediately.

• Ignoring dual solutions entirely.

In which domain is the Primal-Dual Method commonly used?

• Scheduling algorithms

• Knapsack problems

• Network design

• Game theory