An algorithm is a well-defined step-by-step computational procedure that takes an input and an output in a finite amount of time. They find considerable use in software engineering and mathematics.
An algorithm is correct if for every input it halts (i.e., it finishes computations in finite time) and outputs the correct solution. It solves a problem if the algorithm can be applied to any instance of the problem and be guaranteed to produce a solution for that instance.
Resources
- Introduction to Algorithms, by Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein (CLRS)
- Algorithms by Jeff Erickson
- https://cs.uwaterloo.ca/~r5olivei/courses/2021-fall-cs466/other-resources/
Key concepts
- Time complexity
- Correctness
- Greedy algorithm
- Sorting algorithm
- Searching algorithm
- Quantum algorithm