4. Algorithms

- 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.

Start by reading through:

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.1.1A Sequencing, selection, and iteration are building blocks of algorithms.
- EK 4.1.1B Sequencing is the application of each step of an algorithm in the order in which the statements are given.
- EK 4.1.1C Selection uses a Boolean condition to determine which of two parts of an algorithm is used.
- EK 4.1.1D Iteration is the repetition of part of an algorithm until a condition is met or for a specified number of times.
- EK 4.1.1E Algorithms can be combined to make new algorithms.
- EK 4.1.1F Using existing correct algorithms as building blocks for constructing a new algorithm helps ensure the new algorithm is correct.
**EK 4.1.1G Knowledge of standard algorithms can help in constructing new algorithms.****EK 4.1.1H Different algorithms can be developed to solve the same problem.**- EK 4.1.1I Developing a new algorithm to solve a problem can yield insight into the problem.

**EK 4.1.2A Languages for algorithms include natural language, pseudocode, and visual and textual programming languages.****EK 4.1.2B Natural language and pseudocode describe algorithms so that humans can understand them.****K 4.1.2C Algorithms described in programming languages can be executed on a computer.**- EK 4.1.2D Different languages are better suited for expressing different algorithms.
- EK 4.1.2E Some programming languages are designed for specific domains and are better for expressing algorithms in those domains.

**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.**