3.17: Algorithmic Efficiency

ENDURING UNDERSTANDING AAP-4 There exist problems that computers cannot solve, and even when a computer can solve a problem, it may not be able to do so in a reasonable amount of time.

LEARNING OBJECTIVE AAP-4.A For determining the efficiency of an algorithm: a. Explain the difference between algorithms that run in reasonable time and those that do not. b. Identify situations where a heuristic solution may be more appropriate

ESSENTIAL KNOWLEDGE AAP-4.A.1 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.

AAP-4.A.2 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?).

AAP-4.A.3 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 (EK AAP-4.A.3):
Formal analysis of algorithms (Big-O) and formal reasoning using mathematical formulas are outside the scope of this course and the AP Exam.

AAP-4.A.4 An algorithm’s efficiency is determined through formal or mathematical reasoning.

ESSENTIAL KNOWLEDGE

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

AAP-4.A.6 Different correct algorithms for the same problem can have different efficiencies.

AAP-4.A.7 Algorithms with a polynomial efficiency or slower (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.

AAP-4.A.8 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.

AAP-4.A.9 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 (AAP-4.A.9):
Specific heuristic solutions are outside the scope of the this course and the AP Exam.

3.18: Undecidable Problems

ENDURING UNDERSTANDING AAP-4 There exist problems that computers cannot solve, and even when a computer can solve a problem, it may not be able to do so in a reasonable amount of time.

LEARNING OBJECTIVE AAP-4.B Explain the existence of undecidable problems in computer science.  1.A

ESSENTIAL KNOWLEDGE AAP-4.B.1 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?”).

AAP-4.B.2 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 (EK AAP-4.B.2):
Determining whether a given problem is undecidable is outside the scope of this course and the AP Exam.

AAP-4.B.3 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.

Sources used