Algorithms

Binary search: finding a value in a sorted array by halving the range at every step, with the invariant, the midpoint and the boundaries that make it correct.

Intermediate9 cards · 5 qnot started

Elementary sorting: bubble, selection and insertion sort traced pass by pass, and the one place each still beats an O(n log n) algorithm.

Intermediate11 cards · 5 qnot started

Divide and conquer: designing an algorithm by splitting a problem, solving the parts recursively and combining them, then reading its cost from a recurrence.

Intermediate to Advanced8 cards · 4 qnot started

Merge sort: the sorting algorithm that splits an array in half, sorts each half and merges them, in O(n log n) time on every input.

Intermediate8 cards · 4 qnot started

Quicksort: sorting by partitioning around a pivot, fast on average, slow on the inputs a bad pivot meets, and the source of quickselect.

Intermediate to Advanced9 cards · 4 qnot started

Heapsort: sorting in place in O(n log n) time on every input by building a heap and extracting its largest item, one at a time.

Intermediate7 cards · 3 qnot started

Linear-time sorting: counting, radix and bucket sort, which beat the comparison bound by reading the keys' values, and the inputs each one needs.

Intermediate to Advanced11 cards · 5 qnot started

Choosing a sorting algorithm: picking a sort by memory, stability, worst case and keys, the n log n limit on comparison sorts, and built-in sorts.

Intermediate to Advanced8 cards · 4 qnot started

Backtracking: building every candidate solution one choice at a time, undoing each choice, and pruning branches that cannot succeed.

Intermediate to Advanced9 cards · 4 qnot started

Greedy algorithms: taking the locally best choice at every step, proving it with an exchange argument, and disproving it with a counterexample.

Intermediate to Advanced8 cards · 4 qnot started

Dynamic programming: solving a problem from the answers to its overlapping subproblems, top-down with memoisation or bottom-up with a table.

Intermediate to Advanced10 cards · 6 qnot started

Knapsack and grid dynamic programming: filling a table over items and capacities, or over the cells of a grid, and the loop orders that change the answer.

Intermediate to Advanced9 cards · 4 qnot started

Sequence dynamic programming in algorithms: longest common subsequence, edit distance and longest increasing subsequence, each a table over prefixes.

Intermediate to Advanced9 cards · 4 qnot started

Choosing between divide and conquer, dynamic programming, greedy and backtracking in algorithms, by how a problem's subproblems behave.

Intermediate to Advanced7 cards · 3 qnot started

Breadth-first and depth-first search in algorithms, and what they find: components, cycles, bipartite graphs and unweighted shortest paths.

Intermediate to Advanced10 cards · 6 qnot started

Ordering tasks so every dependency comes first, in algorithms: Kahn's algorithm, depth-first finishing times, and how each one finds a cycle.

Intermediate to Advanced8 cards · 4 qnot started

Shortest paths in weighted graphs, in algorithms: Dijkstra's algorithm, Bellman-Ford and Floyd-Warshall, and how weights and pairs choose between them.

Intermediate to Advanced11 cards · 6 qnot started

Minimum spanning trees in algorithms: the cut property, Kruskal's algorithm with union-find, Prim's algorithm with a heap, and why neither gives shortest paths.

Intermediate to Advanced9 cards · 4 qnot started

Graph connectivity in algorithms: strongly connected components with Kosaraju's two passes, bridges and articulation points from low values, and choosing the tool.

Intermediate to Advanced7 cards · 3 qnot started