Classification of algorithms: Practice Questions

In the classification of algorithms, an algorithm is described as having a complexity of \(O(n^2)\). Which of the following best describes this order of complexity?

Which of the following statements regarding the Halting problem is correct?

An algorithm is used to solve a version of the Traveling Salesperson Problem. If the problem is classified as intractable, which of the following is most likely true regarding the classification of algorithms for this problem?

A specific problem has an algorithm that solves it in \(O(2^n)\) time. According to the classification of algorithmic problems, how would this problem be categorized if no polynomial-time solution exists?

Which of the following best describes the use of heuristics in the classification of algorithms?

In the context of the Classification of algorithms, explain why the Halting problem is significant for the theory of computation.

In the classification of algorithmic problems, a problem is found to have no known solution that runs in polynomial time, with the best-known solution being \(O(2^n)\). Define the specific term used to describe such a problem.

The Halting Problem is a classic example of a non-computable problem.

(a) Describe what the Halting Problem is.
(b) Explain the significance of the Halting Problem for the theory of computation and what it tells us about the limits of what computers can do.
(c) Why can't we simply run a program to see if it stops to solve the Halting Problem?

In the classification of algorithms, problems are categorized as tractable or intractable.

(a) Define what makes a problem 'intractable' in terms of its time complexity.
(b) If an algorithm has a complexity of \(O(2^n)\), classify the problem it solves and justify your answer.
(c) When an exact solution for an intractable problem is not feasible, what approach do programmers typically use to find a 'good enough' solution?