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.
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.
AAP-4.A.4 An algorithm’s efficiency is determined through formal or mathematical reasoning.
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.