Find a concept
BRANCH OVERVIEW
Algorithms
Design procedures, prove them correct, and bound their cost.
← All branches · Each sheet includes definitions, theorems, applications, and exercises with hints and worked solutions.
Algorithms
Design procedures, prove them correct, and bound their cost.
- Asymptotics & recurrencesState the input-size measure and computational model before counting operations.
- Sorting, binary search & lower boundsUse ordering to narrow possibilities, and distinguish algorithm cost from unavoidable cost.
- Graph traversal & shortest pathsChoose a traversal based on edge weights, direction, and the question being asked.
- Dynamic programming & greedy choiceIdentify what information a subproblem needs, or prove why a local choice is safe.