2.6 Problem Solving

For determining the efficiency of an algorithm:

• Explain the difference between algorithms that run in reasonable time and those that do not.

For determining the efficiency of an algorithm:

• Identify situations where a heuristic solution may be more appropriate.

Explain the existence of undecidable problems in computer science.

A problem is a general description of a task that can (or cannot) be solved algorithmically. An instance of a problem also includes specific input.

For example, sorting is a problem; sorting the list (2,3,1,7) is an instance of the problem.

A decision problem is a problem with a yes/no answer (e.g., is there a path from A to B?). An optimization problem is a problem with the goal of finding the "best" solution among many (e.g., what is the shortest path from A to B?).

Efficiency is an estimation of the amount of computational resources used by an algorithm. Efficiency is typically expressed as a function of the size of the input.

• EXCLUSION STATEMENT - Formal analysis of algorithms (Big-O) and formal reasoning using mathematical formulas are outside the scope of this course and the AP Exam.

An algorithm’s efficiency is determined through formal or mathematical reasoning.

An algorithm’s efficiency can be informally measured by determining the number of times a statement or group of statements executes.

Different correct algorithms for the same problem can have different efficiencies.

Algorithms with a polynomial efficiency or lower (constant, linear, square, cube, etc.) are said to run in a reasonable amount of time. Algorithms with exponential or factorial efficiencies are examples of algorithms that run in an unreasonable amount of time.

Some problems cannot be solved in a reasonable amount of time because there is no efficient algorithm for solving them. In these cases, approximate solutions are sought.

A heuristic is an approach to a problem that produces a solution that is not guaranteed to be optimal but may be used when techniques that are guaranteed to always find an optimal solution are impractical.

• EXCLUSION STATEMENT - Specific heuristic solutions are outside the scope of this course and the AP Exam.

A decidable problem is a decision problem for which an algorithm can be written to produce a correct output for all inputs (e.g., “Is the number even?”).

An undecidable problem is one for which no algorithm can be constructed that is always capable of providing a correct yes- or-no answer.

• EXCLUSION STATEMENT - Determining whether a given problem is undecidable is outside the scope of this course and the AP Exam.

An undecidable problem may have some instances that have an algorithmic solution, but there is no algorithmic solution that could solve all instances of the problem.