EU 4.1 Algorithms are precise sequences of instructions for processes that can be executed by a computer and are implemented using programming languages.
EU 4.2 Algorithms can solve many, but not all, computational problems.
The above chapter readings include specific knowledge for EKs marked in bold. Work to include unmarked learning objectives in the CS Field Guide is currently in progress.
EK 4.2.1A Many problems can be solved in a reasonable time.
EK 4.2.1B Reasonable time means that the number of steps the algorithm takes is less than or equal to a polynomial function (constant, linear, square, cube, etc.) of the size of the input.
EK 4.2.1C Some problems cannot be solved in a reasonable time, even for small input sizes.
EK 4.2.1D Some problems can be solved but not in a reasonable time. In these cases, heuristic approaches may be helpful to
find solutions in reasonable time.
EK 4.2.2A A heuristic is a technique that may allow us to find an approximate solution when typical methods fail to find an exact solution.
EK 4.2.2B Heuristics may be helpful for finding an approximate solution more quickly when exact methods are too slow.
EK 4.2.2C Some optimization problems such as "find the best" or "find the smallest" cannot be solved in a reasonable time but approximations to the optimal solution can.
EK 4.2.2D Some problems cannot be solved using any algorithm.
EK 4.2.3A An undecidable problem may have instances that have an algorithmic solution, but there is no algorithmic solution that solves all instances of the problem.
EK 4.2.3B A decidable problem is one in which an algorithm can be constructed to answer "yes" or "no" for all inputs (e.g. "is the number even?").
EK 4.2.3C An undecidable problem is one in which no algorithm can be constructed that always leads to a correct yes-or-no answer.
EK 4.2.4A Determining an algorithm’s efficiency is done by reasoning formally or mathematically about the algorithm.
EK 4.2.4B Empirical analysis of an algorithm is done by implementing the algorithm and running it on different inputs.
EK 4.2.4C The correctness of an algorithm is determined by reasoning formally or mathematically about the algorithm, not by testing an implementation of the algorithm.
EK 4.2.4D Different correct algorithms for the same problem can have different efficiencies.
EK 4.2.4E Sometimes, more efficient algorithms are more complex.
EK 4.2.4F Finding an efficient algorithm for a problem can help solve larger instances of the problem.
EK 4.2.4G Efficiency includes both execution time and memory usage.
EK 4.2.4H Linear search can be used when searching for an item in any list; binary search can be used only when the list is sorted.