Algorithm Design Techniques

120 flashcards by MentisLibrary

Divide and conquer, greedy, dynamic programming, backtracking, graph algorithms, amortized analysis, randomization, and approximation, with the signals that tell you which one a problem needs.

What is an algorithm design technique?

A reusable strategy for constructing an algorithm, such as divide and conquer or dynamic programming, independent of which data structures the implementation happens to use.

Big-O notation

An asymptotic upper bound. f(n) is $O(g(n))$ when constants c > 0 and n0 exist such that f(n) <= c*g(n) for every n >= n0.

Big-Omega and Big-Theta

$\Omega(g(n))$ is an asymptotic lower bound and $\Theta(g(n))$ is both bounds at once, so $\Theta$ is the tight description of a growth rate.

Recurrence relation

An equation that expresses the cost of a recursive algorithm in terms of the cost on smaller inputs, plus the work done to split and combine.

Master theorem

Solves T(n) = aT(n/b) + f(n) by comparing f(n) with $n^{\log_b a}$: the larger of the two dominates, and if they match the answer picks up a $\log n$ factor.

Recursion tree method

Draw the recursion as a tree, sum the work at each level, then sum the levels. It gives both an answer and an intuition for where the cost lives.

Substitution method

Guess a closed form for the recurrence, then prove it by induction, strengthening the guess if the induction does not close.

Worst case, average case, and best case

Worst case is the maximum cost over all inputs of size n, average case is the expectation over an input distribution, and best case is the minimum.

Comparison sorting lower bound

Any sorting algorithm that only compares elements needs $\Omega(n \log n)$ comparisons in the worst case, because a decision tree with n! leaves has depth at least $\log_2(n!) = \Theta(n \log n)$.

Pseudo-polynomial time

Running time polynomial in the numeric VALUE of an input, but exponential in the number of bits used to write it.

Reduction

Transforming problem A into problem B so that a solver for B answers A. It carries algorithms forward and hardness backward.

Divide and conquer, the three steps

Divide the input into independent subproblems, conquer them recursively, and combine their answers into a solution for the whole.

Merge sort

Split the array in half, sort each half recursively, then merge the two sorted halves in linear time.

Quicksort

Choose a pivot, partition the array so smaller elements sit left and larger right, then recurse on both sides. No combine step is needed.

Quickselect

Partition like quicksort but recurse into only the side that contains the rank you want, which drops the $\log n$ factor.

Binary search

Halve a sorted search space each step by comparing against the middle element.

Karatsuba multiplication

Multiplies two n-digit numbers with three recursive half-size multiplications instead of four, using (a+b)(c+d) to recover the middle term.

Strassen matrix multiplication

Multiplies two n by n matrices with seven recursive multiplications of half-size blocks instead of eight.

Closest pair of points

Sort by x, split at the median, solve both halves, then check only the points within the best distance found so far of the dividing line.

Counting inversions

Count pairs i < j with a[i] > a[j] by running merge sort and adding, at each merge, the number of remaining left-hand elements when a right-hand element is taken.

Fast Fourier transform

Evaluates a degree n polynomial at the n complex roots of unity by splitting it into even and odd coefficient halves, which lets polynomial multiplication become pointwise multiplication.

Maximum subarray by divide and conquer

Split in half; the best subarray lies entirely left, entirely right, or crosses the midpoint, and the crossing case is a linear scan outward from the middle.

Median of medians

Selects a pivot guaranteed to be near the middle by splitting into groups of five, taking each group's median, and recursively selecting the median of those medians.

Exponentiation by squaring

Computes x^n by squaring repeatedly and multiplying in a factor of x for each set bit of n.

Why does divide and conquer parallelize well?

The subproblems are independent by construction, so each recursive call can run on a different core with no coordination until the combine step.

When does divide and conquer fail?

When the subproblems overlap, so the same subproblem is solved exponentially many times, and when the combine step costs as much as solving the problem directly.

Greedy algorithm

Builds a solution by repeatedly taking the choice that looks best right now and never reconsidering it.

Greedy-choice property

The property that some optimal solution contains the choice the greedy rule makes first, so committing to it never rules out optimality.

Optimal substructure

An optimal solution to the whole problem contains optimal solutions to its subproblems.

Activity selection

Given intervals, pick the largest set that do not overlap by repeatedly taking the activity with the earliest finish time among those still compatible.