ALG · Short notes
24 short notes in syllabus order, about 201 minutes to read end to end.
The exact running time of a program depends on the machine, the compiler and the input. To compare algorithms rather than programs, we describe how the running time grows as the input size n grows, ignoring constant factors and small inputs.
Asymptotic notation says how to compare growth rates. This note shows how to obtain the function to compare: how to count the work done by loops, nested loops and recursive calls, and how much memory a program needs beyond its input.
The running time of a recursive algorithm is naturally described by a recurrence: an equation that gives T(n) in terms of T on smaller inputs. Merge sort splits an array into two halves, sorts each and merges in linear time, so T(n) = 2T(n/2) + Θ(n).
Searching asks whether a key x occurs in a collection and, if so, where.
Sorting rearranges n records so that their keys are in non-decreasing order. Bubble sort, selection sort and insertion sort are the three simple quadratic methods. Their worst-case quadratic cost is slower than merge sort or heapsort on large inputs, but they are short and in place.
Merge sort is the standard example of divide and conquer. It splits the array into two halves, sorts each half recursively, and merges the two sorted halves in linear time. Its worst-case running time is Θ(n lg n), which matches the lower bound for comparison sorting, and it is stable.
Quicksort sorts by divide and conquer, but puts the work in the divide step. It chooses a pivot, partitions the array so that smaller elements come before larger ones, and then sorts the two parts recursively; no combine step is needed.
Heapsort sorts an array by first arranging it into a max-heap and then repeatedly moving the maximum to the end. It is the only standard comparison sort that is both in place (O(1) auxiliary space) and guaranteed O(n lg n) in the worst case.
Every comparison sort needs Ω(n lg n) comparisons in the worst case (see Comparison of Sorting Algorithms). The three algorithms in this note beat that bound because they are not comparison sorts: they use the keys as array indices or split them into digits.
Brings the sorting algorithms together: the lower bound that no comparison sort can beat, exact comparison counts for related problems, and a comparison of all standard sorts on time, space, stability and adaptivity.
A dictionary stores a set of keys (each possibly with satellite data) and supports INSERT, SEARCH and DELETE. A sorted array answers SEARCH in Θ(lg n) time and a balanced search tree does all three in O(lg n).
m-1], and collisions (two keys with the same slot) cannot be avoided once the universe is larger than the table (see Hashing and Hash Functions). The cost analysis uses expectation and linearity of expectation from Random Variables, Expectation and Variance.
Divide and conquer solves a problem by splitting it into smaller instances of the same problem, solving those recursively, and combining their answers. Merge sort, quicksort and binary search are the familiar examples.
A greedy algorithm builds a solution one choice at a time. At every step it picks the option that looks best right now, never undoing that choice later. The hope is that a sequence of locally optimal choices produces a globally optimal answer.
Huffman coding builds an optimal prefix code for a set of symbols with known frequencies: no codeword is a prefix of another, so a bit stream decodes uniquely without separators, and the expected codeword length is minimised among all binary prefix codes.
Dynamic programming (DP) solves an optimisation (or counting) problem by combining answers to smaller overlapping subproblems. Where plain recursion recomputes the same subproblem many times, DP stores each answer once and reuses it.
Three classical DP problems act on sequences: the longest common subsequence (LCS) of two strings, the edit distance (Levenshtein distance) between two strings, and the longest increasing subsequence (LIS) of one sequence.
Three classical DP problems share a tabular fill and a reconstruction step: the 0/1 knapsack problem (and its decision twin subset sum), and matrix-chain multiplication.3-4). Both need DP.
Breadth-first search (BFS) explores a graph level by level from a source s: it visits every vertex at distance k before any vertex at distance k+1. The search builds a BFS tree of shortest paths in the unweighted sense (fewest edges) and assigns each reachable vertex a distance d[v] = δ(s,v).
Depth-first search (DFS) explores a graph by going as deep as possible along each path before backtracking. It assigns every vertex a discovery time d[u] and a finish time f[u], and it classifies every edge as a tree, back, forward or cross edge.
Two classical applications of DFS finish times are topological sort of a directed acyclic graph (DAG) and the computation of strongly connected components (SCCs) of a directed graph. A topological order lists vertices so that every edge goes forward in the list.
A spanning tree of a connected undirected graph G=(V,E) is a subset of E that connects all vertices and forms a tree (|V|-1 edges, no cycle). A minimum spanning tree (MST) is a spanning tree of minimum total edge weight.
The single-source shortest-paths problem asks for a shortest path from a source s to every vertex of a weighted directed graph.
The all-pairs shortest-paths problem asks for δ(i,j) for every pair of vertices.
