An algorithm is a finite, precise procedure that turns an input into an output. The field asks which procedures are correct, how many steps and how much memory they need as inputs grow, and whether a better one exists. It is the difference between a program that answers in a second and one that never finishes.
Key concepts
- Correctness: a loop invariant or an induction argument shows the procedure does what it claims, on every input.
- Asymptotic cost: big-O describes how time and space grow with input size, ignoring constants.
- Design paradigms: divide and conquer, greedy choice, dynamic programming, backtracking, randomisation.
- Sorting and searching: the standard problems on which every technique is first learned.
- Worst, average and amortised cases: the same algorithm can be judged by its worst input, a typical one, or a long sequence of operations.
Vocabulary
- Recurrence: an equation that defines the cost of a problem through the cost of smaller ones.
- Optimal substructure: an optimal answer is built from optimal answers to subproblems.
- Heuristic: a method with no proof of the best answer, used because it is fast and usually good.
- Approximation ratio: how far from optimal an answer can be, guaranteed in the worst case.
What to study, in order
- Write binary search and insertion sort from scratch, and state their invariants.
- Learn big-O and solve simple recurrences, such as the one for merge sort.
- Implement merge sort, quicksort and heaps; count comparisons on random and adversarial inputs.
- Solve classic problems with dynamic programming and greedy choice, and see where greedy fails.
- Study graph traversals and shortest paths, then measure your code against the predicted growth.
Related tags
#data-structures #complexity #graph-theory #competitive-programming