MODULE 1Ch 1 · Fundamentals of Algorithms
What an algorithm is, its defining properties, how it is specified and proven correct, the steps of designing and analysing one, and the important problem types.
What an algorithm is
An algorithm is a sequence of clear instructions for solving a problem — that is, for obtaining the required output for any legitimate input in a finite amount of time. The same problem can be solved by algorithms based on very different ideas and with dramatically different speeds.
Characteristics of an algorithm
Every algorithm has five characteristics: input (zero or more quantities supplied externally), output (at least one quantity produced), definiteness (each instruction is clear and unambiguous), finiteness (it terminates after a finite number of steps for all cases), and efficiency (each instruction is basic and runs in a short time).
Writing an algorithm: head and body
An algorithm is written as a procedure with two parts. The head holds the keyword Algorithm, the name, and the parameter list, plus comment lines for problem description, input, and output. The body uses constructs such as if, for, and while and data structures such as arrays, trees, lists, and sets. The left arrow is used as the assignment operator and comments begin with two slashes.
Euclid's algorithm for gcd
Euclid's algorithm computes gcd(m, n) by repeatedly replacing the pair with (n, m mod n) until the second number is zero, at which point the first number is the answer. In pseudocode it loops while n is not zero, setting r to m mod n, then m to n and n to r, finally returning m.
Steps of designing and analysing an algorithm
Designing and analysing an algorithm proceeds through understanding the problem, deciding on the computational device and on exact versus approximate solving and a design technique, specifying the algorithm, proving its correctness, analysing it, and finally coding it.
Understanding the problem
Understanding the problem means reading its description carefully, asking clarifying questions, identifying the problem type so an existing algorithm can be reused, and fixing the inputs and their range. A correct algorithm is not one that works most of the time but one that works correctly for all legitimate inputs.
Ascertaining the computational device
On a random-access machine (RAM) instructions are executed one after another, one operation at a time, and algorithms for such machines are called sequential algorithms. Some newer computers execute operations concurrently, and algorithms that exploit this are called parallel algorithms. The choice of device is driven mainly by space and time efficiency.
Exact versus approximate solving
An exact algorithm solves the problem exactly and produces a correct result. When a problem is too complex to solve exactly, an approximation algorithm is used instead. Extracting square roots, solving nonlinear equations, and evaluating definite integrals are problems often handled approximately.
Algorithm design techniques
An algorithm design technique is a general approach to solving problems algorithmically that applies to a variety of problems from different areas. Choosing a proper data structure is required before designing the algorithm — captured by the slogan Algorithms + Data Structures = Programs. Brute force, divide-and-conquer, dynamic programming, and the greedy technique are among the techniques.
Methods of specifying an algorithm
There are three ways to specify an algorithm: natural language, pseudocode, and flowchart. Pseudocode is the option most widely used today. Natural language is simple but often gives only a brief specification, and the flowchart — a graphical representation using connected shapes — was dominant in the early days but is now inconvenient.
Proving correctness
After specifying an algorithm its correctness must be established: it must give the required result for every legitimate input in finite time. Mathematical induction is a common technique because an algorithm's iterations give a natural sequence of steps. For approximation algorithms correctness is less straightforward — the error must not exceed a predefined limit.
Analysing an algorithm
Analysis weighs four qualities: time efficiency (how fast it runs), space efficiency (how much extra memory it uses), simplicity, and generality. The efficiency of an algorithm is determined by measuring both its time and its space efficiency.
Important problem types
The most important problem types are sorting, searching, string processing, graph problems, combinatorial problems, geometric problems, and numerical problems. Algorithm design techniques are general strategies applicable across these areas.
The sorting problem
Sorting rearranges the items of a list into nondecreasing (ascending) order and can be applied to numbers, characters, strings, or records. The chosen piece of information used to order records is the key. A sorting algorithm is in-place if it needs no extra memory, and stable if it preserves the relative order of any two equal elements.
The searching problem
Searching deals with finding a given value, called the search key, in a given set. Ordinary linear (sequential) search and the faster binary search are two examples.
String processing
A string is a sequence of characters from an alphabet — text strings of letters and numbers, bit strings of zeros and ones, or gene sequences over the four-letter alphabet {A, C, G, T}, useful in bioinformatics. Searching for a given word in a text is called string matching.
Graph and combinatorial problems
A graph is a collection of points (vertices) some of which are joined by line segments (edges); graph problems include traversal, shortest paths, topological sort, the travelling salesman problem, and graph colouring. Combinatorial problems ask for an object such as a permutation, combination, or subset satisfying constraints, and are in practice the most difficult problems in computing.
Geometric and numerical problems
Geometric algorithms deal with objects such as points, lines, and polygons and are used in computer graphics, robotics, and tomography; the closest-pair and convex-hull problems belong here. Numerical problems involve mathematical equations, systems of equations, integrals, and function evaluation, and most can be solved only approximately.
MODULE 2Ch 2 · Algorithm Analysis Methods
The analysis framework — input size, basic operation, orders of growth, the three case efficiencies — asymptotic notation, and mathematical analysis of recursive and non-recursive algorithms.
The analysis framework
There are two kinds of efficiency: time efficiency (time complexity) indicating how fast an algorithm runs, and space efficiency (space complexity) indicating the memory it needs. The analysis framework consists of measuring an input's size, choosing units for measuring running time, studying orders of growth, and distinguishing worst-, best-, and average-case efficiencies.
Issues and approaches
Analysing an algorithm addresses correctness, time efficiency, space efficiency, and optimality. Two approaches exist: empirical analysis, which is less useful, and theoretical analysis, which is the most important.
Basic operation and running time
Time efficiency is analysed by counting how many times the basic operation — the operation contributing most to the running time — is executed, as a function of input size. The running time is estimated as T(n) approximately equal to cop times C(n), where cop is the execution time of the basic operation and C(n) is its count.
Units for measuring running time
Measuring running time in seconds or milliseconds has drawbacks: it depends on the computer's speed, the quality of the implementation, and the compiler, and the actual time is hard to clock. Counting every operation is excessively difficult, so analysis counts how many times the basic operation is executed.
Orders of growth
Differences in running time on small inputs do not really distinguish efficient algorithms from inefficient ones. For large values of n it is the function's order of growth that counts; the difference in efficiencies becomes clear only for large inputs.
Worst-, best-, and average-case efficiency
When the running time can differ for the same input size, the cases are distinguished. For sequential search, the worst case has no match (or the match is last), so the key is compared with all n elements; the best case has a match at the first element. The average case is investigated separately.
Key points of the framework
Both time and space efficiencies are measured as functions of the input size; time by counting basic-operation executions and space by counting extra memory units. Where efficiencies differ for inputs of the same size, the worst, average, and best cases are distinguished. The framework's primary interest is the order of growth as input size goes to infinity.
Asymptotic notations
Asymptotic notation lets us make a meaningful statement about a program's efficiency, concentrating on the order of growth of the basic-operation count. Three notations are used to compare and rank orders of growth: O (big-oh), Omega (big-omega), and Theta (big-theta).
O-notation
A function t(n) is in O(g(n)) when t(n) is at most c times g(n) for all n at least n0. O is the asymptotic upper bound, useful for worst-case analysis, and is a loose bound. For example, n is in O(n^2) and 100n + 5 is in O(n^2).
Analysing recursive algorithms
The general plan for a recursive algorithm: decide on an input-size parameter, identify the basic operation, check whether its count varies on inputs of the same size, set up a recurrence relation with an initial condition for the basic-operation count, and solve the recurrence or at least find the order of growth of its solution.
Recurrence for the factorial
For F(n) = F(n-1) times n, the basic operation is multiplication, whose count M(n) satisfies M(n) = M(n-1) + 1: one multiplication to combine the recursively computed F(n-1) with n. Such recurrences are solved by the method of backward substitution.
Analysing non-recursive algorithms
The general plan for a non-recursive algorithm: decide on an input-size parameter, identify the basic operation in the innermost loop, check whether its count depends only on input size, set up a sum expressing the basic-operation count, and use standard sum-manipulation rules to find a closed form or the order of growth.
Empirical analysis
The principal alternative to mathematical analysis is empirical analysis, useful when mathematical analysis is difficult. Its plan: understand the experiment's purpose, choose the efficiency metric and unit (operation count versus time), decide on the input sample, implement the algorithm, generate inputs, run and record the data, and analyse the results.
MODULE 3Ch 3 · Brute Force & Exhaustive Search
Brute force and its exhaustive-search variant: selection and bubble sort, sequential search and string matching, closest-pair, the TSP / knapsack / assignment problems, and the DFS and BFS graph traversals.
The brute-force approach
Brute force is a straightforward approach to solving a problem, based directly on the problem statement and definitions of the concepts involved — the 'just do it' strategy. It is one of the easiest strategies and, although generally inefficient, can be useful for small instances of a problem.
Selection sort
Selection sort scans the list to find the smallest element and exchanges it with the first, then scans from the second element for the next smallest, and so on. On the i-th pass (numbered 0 to n-2) it searches the last n-i elements for the smallest and swaps it into place. Its basic operation is the key comparison, and it is a quadratic algorithm on all inputs.
Bubble sort
Bubble sort compares adjacent elements and exchanges them if they are out of order, repeatedly 'bubbling up' the largest element to the last position. After n-1 passes the list is sorted. Its number of key comparisons is the same for all arrays of size n.
Sequential search
Sequential search compares successive elements of a list with the search key until either a match is found (successful) or the list is exhausted (unsuccessful). Appending the search key to the end guarantees a match and removes the end-of-list check; sorting the list lets the search stop as soon as an element greater than or equal to the key is met.
Brute-force string matching
Brute-force string matching aligns a pattern P against a text T and, moving left to right, compares pattern characters with the corresponding text characters until all match or a mismatch occurs; on a mismatch the pattern is shifted one position to the right and the comparison repeats.
Closest-pair problem by brute force
The closest-pair problem finds the two closest points among n points and is among the simplest computational-geometry problems. The brute-force approach computes the distance between each distinct pair of points and keeps the smallest, considering only pairs (pi, pj) with i < j to avoid computing the same distance twice. Its basic operation is computing the square root.
Exhaustive search
Exhaustive search is simply a brute-force approach to combinatorial problems: it generates each element of the problem domain, selects those satisfying all constraints, and finds the desired one — for example, the one optimising an objective function. It is illustrated with the travelling salesman, knapsack, and assignment problems.
Travelling salesman problem
The TSP asks for the shortest tour through n cities that visits each exactly once and returns to the start. Modelled by a weighted graph, it becomes finding the shortest Hamiltonian circuit. Generating all permutations of the n-1 intermediate cities gives 1/2 times (n-1)! tours, making exhaustive search impractical for all but very small n.
Knapsack problem (exhaustive search)
Given n items with known weights and values and a knapsack of capacity W, the knapsack problem finds the most valuable subset of items that fit. The exhaustive-search approach generates all subsets of the n items and checks which are feasible; since an n-element set has 2^n subsets, this yields an exponential algorithm.
Assignment problem
The assignment problem assigns n people to n jobs, one person per job and one job per person, with a known cost C[i, j] for each pairing, and seeks the assignment of minimum total cost. Feasible assignments correspond one-to-one with permutations of the integers 1 to n, so exhaustive search generates all such permutations and keeps the cheapest.
Depth-first search
DFS starts at an arbitrary vertex, marks it visited, and on each iteration proceeds to an unvisited adjacent vertex; at a dead end it backs up one edge and continues, halting after backing up to the start. It uses a stack and yields a DFS forest with tree and back edges. Its time is proportional to the size of the graph representation.
Breadth-first search
BFS proceeds concentrically: it first visits all vertices adjacent to the start, then all vertices two edges away, and so on. It uses a queue, a FIFO (first-in first-out) structure: the queue is initialised with the start vertex, then on each iteration the unvisited neighbours of the front vertex are marked, enqueued, and the front vertex is removed.
Efficiency of DFS and BFS
DFS and BFS have the same time efficiency, which is proportional to the size of the graph's representation: for the adjacency-matrix representation it is proportional to the square of the number of vertices, and for the adjacency-list representation it is proportional to the number of vertices plus the number of edges.
MODULE 4Ch 4 · Decrease-and-Conquer
Solving a problem from the solution to a smaller instance: the three decrease variants, insertion sort, topological sorting of digraphs, binary search, and partition-based selection.
The decrease-and-conquer idea
Decrease-and-conquer exploits the relationship between a solution to a given instance and a solution to a smaller instance of the same problem. Once that relationship is established it can be used either top down or bottom up.
Top-down and bottom-up
The top-down variation is usually implemented recursively. The bottom-up variation is usually implemented iteratively, starting from a solution to the smallest instance; it is sometimes called the incremental approach.
Three variations
There are three major variations of decrease-and-conquer: decrease by a constant (most often by one, as in insertion sort), decrease by a constant factor (most often by two, as in binary search), and variable-size decrease (as in Euclid's algorithm).
Decrease by a constant
In the decrease-by-a-constant variation the size of an instance is reduced by the same constant — usually one — on each iteration. The exponentiation problem of computing a^n uses the relationship a^n = a^(n-1) times a between an instance of size n and one of size n-1.
Decrease by a constant factor
In the decrease-by-a-constant-factor variation the instance is reduced by the same constant factor — most often two — on each iteration. Computing a^n recursively this way and counting multiplications gives a logarithmic algorithm, because the size is roughly halved each iteration at the cost of one or two multiplications.
Variable-size decrease
In the variable-size-decrease variation the size-reduction pattern varies from one iteration to the next. Euclid's algorithm for the greatest common divisor is a good example, based on gcd(m, n) = gcd(n, m mod n), in which the second argument is always smaller on the right-hand side than on the left.
Insertion sort
Insertion sort assumes A[0..n-1] is sorted except for the last element and finds the right position for A[n-1] among the sorted elements by scanning from right to left until the first element smaller than or equal to it is met. It is based on a recursive idea, but the bottom-up (iterative) implementation is more efficient.
Insertion sort analysis
Insertion sort's basic operation is the key comparison. Its worst-case input is an array of decreasing values; its best case is an already-sorted (non-decreasing) array, where the comparison runs only once per outer iteration. It is a quadratic algorithm in the worst and average cases but about twice as fast on average as in the worst case, and it performs well on almost-sorted arrays. It is better than selection sort and bubble sort.
Directed graphs and DFS edge types
A directed graph (digraph) has directions on all its edges; its adjacency matrix need not be symmetric and each edge appears once in the adjacency lists. A DFS forest of a digraph can contain four edge types: tree edges, back edges (to ancestors), forward edges (to non-child descendants), and cross edges (none of the others).
Directed cycles and DAGs
A directed cycle is a sequence of three or more vertices that starts and ends at the same vertex with each vertex joined to its predecessor by an edge directed from predecessor to successor. If a DFS forest of a digraph has no back edges, the digraph is a DAG — a directed acyclic graph.
Topological sorting and source removal
Topological sorting lists the vertices of a digraph so that for every edge the vertex it starts at comes before the vertex it points to. The source-removal algorithm repeatedly identifies a source — a vertex with no incoming edges — and deletes it with its outgoing edges, breaking ties arbitrarily; the order of deletion gives a topological ordering.
Binary search
Binary search is a very efficient algorithm for a sorted array. It compares the search key K with the middle element A[m]; if they match it stops, otherwise it repeats on the first half if K is smaller and on the second half if K is larger. It is based on a recursive idea but can be implemented non-recursively, and it is a principal example of a decrease-by-a-constant-factor algorithm.
Binary search analysis
Binary search counts comparisons of the key with array elements, assuming one comparison tells whether K is smaller, equal to, or larger than A[m]. Its worst-case inputs include all arrays not containing the key plus some successful searches, giving a recurrence whose solution is logarithmic. Restricting operations to key comparisons, binary search is an optimal searching algorithm.
The selection problem
The selection problem finds the k-th smallest element (k-th order statistic) of an array. The easiest cases extract the minimum (k = 1) or maximum (k = n); the hardest is the median (k = n/2). One approach sorts the list and selects the k-th element, so its time is determined by the sorting algorithm used.
Lomuto partitioning
Lomuto partitioning treats a subarray as three contiguous segments listed after the pivot p: a segment known to be smaller than p, a segment known to be greater than or equal to p, and a segment of elements not yet compared to p. Any of these segments can be empty.
Quickselect
Quickselect finds the k-th smallest element using partitioning. Let s be the split position of the pivot after partitioning: if s = k-1 the pivot is the answer; if s > k-1 the answer lies in the left part; if s < k-1 it is the (k-s)-th smallest in the right part, solved recursively. Partitioning an n-element array always needs n-1 key comparisons, giving a best case that is linear.
MODULE 5Ch 5 · Divide-and-Conquer
Divide a problem into smaller subproblems of the same type, solve recursively, and combine: the master-theorem recurrence, mergesort, quicksort, binary-tree traversals, Strassen's multiplication, and closest-pair.
The divide-and-conquer plan
Divide-and-conquer is the best-known general design technique. Its plan has three steps: divide the problem into several subproblems of the same type, ideally of about equal size; conquer the subproblems by solving them recursively; and combine the subproblem solutions into a solution to the original problem. The technique is well suited to parallel computation.
The divide-and-conquer recurrence
For an instance of size n divided into b instances of size n/b, with a of them needing to be solved (a at least 1, b greater than 1), the running time satisfies T(n) = a T(n/b) + f(n), where f(n) is the time spent dividing and combining. The order of growth of T(n) depends on a, b, and the order of growth of f(n).
The Master Theorem
The Master Theorem establishes the order of growth of the solution to T(n) = a T(n/b) + f(n), with analogous results for the O and Omega notations. For the sum-computation recurrence A(n) = 2 A(n/2) + 1, the solution is linear in n.
Mergesort
Mergesort sorts A[0..n-1] by splitting it into two halves, sorting each recursively, and merging the two sorted halves into one. The merge uses two pointers at the fronts of the arrays, repeatedly comparing the pointed-to elements, copying the smaller into a new array and advancing that pointer, until one array is exhausted, then copying the rest of the other.
Mergesort analysis
Mergesort's time efficiency is n log n in all cases, with the number of key comparisons very close to the theoretical minimum. Its principal drawback is a significant extra storage requirement.
Quicksort
Quicksort rearranges its elements by partitioning: it arranges the array so that all elements to the left of some A[s] are less than or equal to it and all to the right are greater than or equal to it. After a partition, A[s] is in its final sorted position, and the two subarrays to its left and right are sorted independently.
Quicksort analysis
In the best case all splits happen in the middle, giving an n log n number of comparisons; on average quicksort makes only about 39 percent more comparisons than in the best case. The worst case — for example a strictly increasing array with the first element as pivot — is quadratic. Quicksort is noted for superior efficiency among n log n sorting algorithms despite its quadratic worst case.
Binary trees and traversals
A binary tree is a finite set of nodes that is either empty or consists of a root and two disjoint binary trees, the left and right subtrees; it is a special case of an ordered tree. The three classic divide-and-conquer traversals are preorder (root before the subtrees), inorder (root between the left and right subtrees), and postorder (root after both subtrees).
Strassen's matrix multiplication
Strassen's key insight is that the product of two 2-by-2 matrices can be found with just seven multiplications instead of eight. Applied recursively via divide-and-conquer, it multiplies two n-by-n matrices with about n^2.807 multiplications, fewer than the n^3 of the brute-force algorithm, and its number of additions has the same order of growth.
Multiplication of large integers
Applications such as cryptography require manipulating integers over 100 decimal digits long, which motivates efficient algorithms for multiplying large n-digit integers represented as arrays of their digits.
Closest-pair by divide-and-conquer
The divide-and-conquer technique can be successfully applied to the closest-pair problem, which finds the two closest points among a set of points.
MODULE 6Ch 6 · Transform-and-Conquer I
Transform an instance into something easier to solve: instance simplification (presorting, Gaussian elimination), the searching taxonomy, binary search trees, and balanced AVL trees with their rotations.
The transform-and-conquer idea
Transform-and-conquer is a group of techniques based on transforming a problem into one that is easier to solve. It works as a two-stage procedure: a transformation stage modifies the problem instance to be more amenable to solution, and a conquering stage then solves it.
Three varieties of transformation
The transformation can be of three kinds: instance simplification (a simpler or more convenient instance of the same problem, such as a sorted list), representation change (a different representation of the same instance, such as a different data structure), and problem reduction (a different problem for which an algorithm is already available).
Presorting
Presorting is an instance-simplification technique: many list problems become easier once the list is sorted, including searching, computing the median, and checking element uniqueness. The efficiency of such algorithms depends on the efficiency of the sorting step.
The comparison-sorting lower bound
A theorem states that about n log2 n comparisons are necessary in the worst case to sort a list of size n by any comparison-based algorithm, and that about n log2 n comparisons are also sufficient — achieved by mergesort and quicksort.
Searching with presorting
To search for a key, the presorting-based algorithm first sorts the array with an efficient sorting algorithm, then applies binary search. Its overall efficiency is n log n for the sort plus log n for the search, giving n log n overall.
Element uniqueness with presorting
The presorting-based element-uniqueness algorithm sorts the array with an efficient sorting algorithm and then scans it once to check adjacent pairs, giving n log n overall. The brute-force alternative compares all pairs of elements and is quadratic.
Gaussian elimination
Gaussian elimination is an instance-simplification technique that transforms a system of n linear equations in n unknowns with an arbitrary coefficient matrix into an equivalent system with an upper-triangular coefficient matrix, then solves it by back substitution starting with the last equation and moving up. The elementary row operations used do not change the solution, and the overall efficiency is cubic.
Taxonomy of searching algorithms
Searching algorithms fall into three groups: list searching (sequential search, binary search, interpolation search), tree searching (binary search trees, balanced trees such as AVL and red-black, and multiway trees such as 2-3, 2-3-4, and B-trees), and hashing (open hashing or separate chaining, and closed hashing or open addressing).
Binary search trees
A binary search tree arranges keys so that, at every node, keys in the left subtree are smaller than the node's key and keys in the right subtree are larger. The efficiency of search, insertion, and deletion depends on the tree's height: their worst-case efficiency is linear and their average-case efficiency is logarithmic.
Balanced search trees
The attractiveness of a binary search tree is marred by its bad, linear worst-case efficiency. Two ideas keep a tree close to balanced: restructuring it to maintain balance after an unbalancing insertion (AVL trees, red-black trees), or allowing more than one key per node (2-3 trees).
AVL trees
An AVL tree is a binary search tree in which, for every node, the difference between the heights of its left and right subtrees — the balance factor — is at most 1, with the height of an empty tree defined as -1.
AVL rotations
When an insertion violates the balance requirement, the subtree rooted at the unbalanced node closest to the new leaf is transformed by one of four rotations: single right (R), single left (L), double left-right (LR), and double right-left (RL). The LR-rotation performs an L-rotation of the left subtree followed by an R-rotation of the new tree.
AVL tree analysis
On an AVL tree, search and insertion are logarithmic, and deletion — though more complicated — is also logarithmic. The disadvantages are frequent rotations and complexity. A related idea is the red-black tree, which allows the heights of subtrees to differ by up to a factor of two.
MODULE 7Ch 6 · Transform-and-Conquer II
Two more transform-and-conquer ideas: the heap data structure and heapsort (representation change), and problem reduction, which solves a problem via an algorithm already available for another.
What a heap is
A heap is a binary tree with one key per node such that it is essentially complete — all levels are full except possibly the last, where only some rightmost keys may be missing — and the key at each node is greater than or equal to the keys in its children and descendants (the parental-dominance requirement).
Properties of a heap
A heap has useful properties: for a given n there is a unique essentially-complete binary tree with n nodes, of height the floor of log2 n; the root contains the largest key; every subtree rooted at any node is also a heap; and a heap is normally represented as an array. Its elements are ordered top down along any root-to-leaf path, but not left to right.
Heap array representation
A heap is stored in an array indexed 1 to n in top-down, left-to-right order. For node j the left child is at index 2j, the right child at 2j+1, and the parent at the floor of j/2. The parental (interior) nodes occupy the first floor of n/2 locations.
Bottom-up heap construction
Bottom-up heap construction initialises the array with the given keys, then starting from the last (rightmost) parental node fixes the heap rooted at it — repeatedly exchanging it with its larger child until the heap condition holds (the heapify step) — and repeats this for each preceding parental node.
Inserting into a heap
To insert a new element (a top-down operation) it is placed at the last position and the heap size increased, then compared with its parent and exchanged if it violates the heap condition, continuing up the tree until the heap condition is satisfied. The efficiency of an insertion is logarithmic.
Heapsort
Heapsort has two stages: construct a heap for the n keys, then repeat root removal n-1 times — exchange the root with the last leaf, decrease the heap size by one, and sift the new root down to restore the heap condition. Both worst- and average-case efficiency are n log n; it is in-place but not stable.
Problem reduction
Problem reduction solves a problem by transforming it into a different problem for which an algorithm is already available: to solve P, solve Q and use its solution as part of the solution to P. To be of practical value, the combined time of the transformation plus solving the other problem should be smaller than solving the original problem by another method.
Reducing LCM to GCD
A classic reduction computes the least common multiple via the greatest common divisor: LCM(x, y) = (x times y) / GCD(x, y). Here P is LCM and Q is GCD, and the notation P arrow Q means P reduces to Q.
More reduction examples
Other reductions include solving puzzles via state-space graphs, transforming a maximisation problem into a minimisation problem and vice versa, linear programming, and counting the number of paths of length n in a graph by raising the graph's adjacency matrix to the n-th power.
MODULE 8Ch 7 · Space & Time Trade-Offs I
Trading space for time through input enhancement: comparison-counting sort and the input-enhanced string-matching algorithms — Horspool's and Boyer-Moore.
Space-for-time trade-offs
Two varieties of space-for-time algorithms exist. Input enhancement preprocesses part of the input and stores extra information to be used later — counting sorts and string-searching algorithms are examples. Prestructuring preprocesses the input to make accessing its elements easier — hashing and indexing schemes such as B-trees are examples.
Comparison-counting sort
Comparison-counting sort is a first example of input enhancement applied to sorting: for each element it counts the total number of elements smaller than it and records this in a table, and those counts indicate the elements' positions in the sorted list, which is built by copying each element to its position. It makes the same number of key comparisons as selection sort and uses a linear amount of extra space.
Brute-force string matching revisited
In string matching a pattern of m characters is searched for in a text of n characters. The brute-force algorithm aligns the pattern at the start of the text, compares characters left to right until all match or a mismatch occurs, and on a mismatch realigns the pattern one position to the right. Its worst-case time complexity is the product of m and n.
String matching by preprocessing the pattern
Several string-searching algorithms preprocess the pattern. Knuth-Morris-Pratt (KMP) preprocesses the pattern left to right; Boyer-Moore preprocesses it right to left and stores information in two tables; Horspool's algorithm simplifies Boyer-Moore using just one table. These achieve worst-case time proportional to m plus n.
Horspool's algorithm
Horspool's algorithm, a simplified Boyer-Moore, preprocesses the pattern to build a shift table that says how far to shift when a mismatch occurs. It always shifts based on the text character aligned with the last compared character of the pattern, using that character's entry in the shift table.
Horspool's four shift cases
When a mismatch occurs at text character c, Horspool's shift table covers four cases. If c does not occur in the pattern, shift by the whole pattern length. If c occurs in the pattern but is not its last character, align the rightmost occurrence of c with the text's c. If c is the pattern's last character with no other c among the first m-1, shift by the whole length. If c is the last character and other c's appear among the first m-1, align the rightmost of those with the text's c.
Boyer-Moore algorithm
Boyer-Moore compares the pattern to the text from right to left and precomputes shift sizes in two tables: the bad-symbol table, which gives a shift based on the text character causing a mismatch, and the good-suffix table, which gives a shift based on the matched suffix of the pattern. Its worst-case time complexity is proportional to n plus m.
Trading space for time
As an algorithm design technique, trading space for time is much more prevalent than trading time for space. Distribution counting is a special method for sorting lists of elements drawn from a small set of possible values.
MODULE 9Ch 7 · Space & Time Trade-Offs II
More space-for-time techniques: hashing as a dictionary implementation with its two collision-resolution schemes, and B-trees for indexing data on disk.
Hashing
Hashing is a very efficient method for implementing a dictionary — a set with the operations find, insert, and delete. It is based on the representation-change and space-for-time trade-off ideas, and its important applications include symbol tables and databases.
Hash tables and hash functions
Hashing maps keys of a file of size n into a table of size m, the hash table, using a predefined hash function — for example h(K) = K mod m, with m typically prime. A good hash function should be easy to compute and should distribute keys about evenly throughout the table.
Collisions and the two schemes
A collision occurs when two distinct keys hash to the same cell; good hash functions reduce but cannot eliminate collisions. The two principal schemes handle them differently: open hashing makes each cell the header of a linked list of all keys hashed to it, while closed hashing stores one key per cell and, on a collision, finds another cell using linear probing or double hashing.
Open hashing (separate chaining)
In open hashing, or separate chaining, keys are stored in linked lists outside the hash table whose cells serve as the lists' headers. If the hash function distributes keys uniformly, the average list length is the load factor, the ratio of n to m, which is kept small (ideally about one). Open hashing still works when n exceeds m, and its operations are constant-time on average when n is about equal to m.
Closed hashing (open addressing)
In closed hashing, or open addressing, keys are stored inside the hash table itself without linked lists, so the table size m must be at least the number of keys n. With linear probing, on a collision the next cell is checked, then its successor, and so on, wrapping to the start as a circular array. Closed hashing avoids pointers, but deletions are not straightforward and the number of probes rises sharply as the load factor approaches one.
B-trees
A B-tree, introduced by Bayer and McCreight, is the most important index organisation for structured records. It permits more than one key per node: in the B-tree version all data records (or record keys) are stored at the leaves in increasing order, while the parental nodes hold ordered keys used for indexing, interposed with pointers to the children.
B-tree structural properties
A B-tree of order m (at least 2) satisfies three structural properties: the root is either a leaf or has between 2 and m children; every node except the root and the leaves has between the ceiling of m/2 and m children; and the tree is perfectly balanced, with all its leaves at the same level.
Searching a B-tree
Searching a B-tree starts at the root and follows a chain of pointers down to the leaf that may contain the search key, then searches among that leaf's keys; because keys are stored in sorted order at both parental nodes and leaves, binary search can be used within a node when there are enough keys. The tree height is logarithmic in the number of keys, so searches need only a few disk accesses even for very large files.
MODULE 10Ch 8 · Dynamic Programming
Solving problems with overlapping subproblems by recording sub-solutions in a table: the DP idea and rules, knapsack by DP, Warshall's and Floyd's algorithms, and optimal binary search trees.
What dynamic programming is
Dynamic programming is a general algorithm design technique for problems defined by recurrences with overlapping subproblems. It was invented by Richard Bellman in the 1950s for optimisation problems; here 'programming' means 'planning'. Its main idea is to set up a recurrence relating a larger instance to smaller ones, solve each smaller instance once, record the solutions in a table, and extract the answer to the original instance from that table.
Dynamic programming versus divide-and-conquer
Like divide-and-conquer, dynamic programming divides a problem into subproblems, but in divide-and-conquer the subproblems are independent of each other, whereas in dynamic programming they overlap. A recursive formulation is formed, then the problem is usually solved bottom up, storing each subproblem's solution in a table so it can be reused instead of recomputed.
Fibonacci example
The Fibonacci numbers F(n) = F(n-1) + F(n-2), with F(0) = 0 and F(1) = 1, illustrate dynamic programming. Computing F(n) recursively top-down recomputes the same values many times, whereas a bottom-up iteration computes each value once and records the results.
Dynamic programming rules
Dynamic programming follows three rules. Bellman's principle of optimality states that an optimal solution to any instance of an optimisation problem is composed of optimal solutions to its subinstances. The problems have overlapping subproblems, and dynamic programming computes in a bottom-up fashion, combining subproblem solutions into the solution of the original problem.
Examples of DP algorithms
Dynamic-programming algorithms include computing a binomial coefficient, Warshall's algorithm for transitive closure, Floyd's algorithm for all-pairs shortest paths, and constructing an optimal binary search tree. Some difficult discrete optimisation problems, such as the travelling salesman and knapsack problems, also have dynamic-programming solutions.
Knapsack by dynamic programming
The knapsack problem is solved by dynamic programming by filling a table: for items and capacities greater than zero, F(i, j) is the maximum of the entry in the previous row and the same column, and the sum of the current item's value and the entry in the previous row at the column reduced by the item's weight. The table can be filled row by row or column by column.
Transitive closure
A binary relation u R v between vertices represents a path from u to v. A transitive relation means that if there is a relation from u to v and from v to w, then there is one from u to w. The adjacency matrix of the set of transitive relations is called the reachability, connectivity, or path matrix.
Warshall's algorithm
Warshall's algorithm computes the transitive closure of a relation — the existence of all nontrivial paths in a digraph. On the k-th iteration it determines, for every pair (i, j), whether a path exists using only the first k vertices as intermediates. It starts from the adjacency matrix and ends at the transitive closure, running in cubic time, and its matrices can be written over their predecessors to save space.
Floyd's algorithm
Floyd's algorithm finds the shortest paths between every pair of vertices in a weighted graph. Using the same idea as Warshall's, it builds a series of matrices that allow increasing subsets of vertices as intermediates: the k-th matrix entry for (i, j) is the smaller of the previous value and the path through vertex k. It runs in cubic time, its matrices can overwrite their predecessors, and the shortest paths themselves can also be recovered.
Optimal binary search trees
An optimal binary search tree implements a dictionary: given n keys and their search probabilities, it is the binary search tree with the minimum average number of comparisons in a successful search. Because the total number of binary search trees on n nodes grows exponentially, brute force is inefficient, so dynamic programming fills a table diagonal by diagonal using a recurrence over possible roots.
MODULE 11Ch 9 · Greedy Technique
Building an optimal solution through feasible, locally optimal, irrevocable choices: change-making, Prim's and Kruskal's MST algorithms, Dijkstra's shortest paths, and Huffman codes.
The greedy technique
The greedy technique constructs a solution to an optimisation problem piece by piece through a sequence of choices, each of which must be feasible, locally optimal, and irrevocable. For some problems it yields an optimal solution for every instance; for most it does not, but it can be useful for fast approximations.
Applications of the greedy strategy
Greedy yields optimal solutions for change-making with normal coin denominations, the minimum spanning tree, single-source shortest paths, simple scheduling problems, and Huffman codes. It provides only approximations for the travelling salesman problem, the knapsack problem, and other combinatorial optimisation problems.
Change-making problem
The change-making problem gives change for an amount n using the least number of coins from unlimited supplies of denominations. The greedy solution is optimal for any amount with a typical set of denominations, but it is not optimal for all sets — for example, with denominations 1, 3, and 4 it can fail.
Minimum spanning tree
A spanning tree of a connected graph is a connected acyclic subgraph that includes all of the graph's vertices. The minimum spanning tree of a weighted connected graph is a spanning tree of minimum total weight, and the minimum-spanning-tree problem is to find one for a given weighted connected graph.
Prim's algorithm
Prim's algorithm finds a minimum spanning tree by starting with a tree of one arbitrary vertex and growing it one vertex at a time through expanding subtrees: on each iteration it adds the vertex not yet in the tree that is closest to those already in it — the greedy step — stopping when all vertices are included. It needs a priority queue (a min-heap) to locate the closest fringe vertex. Its efficiency is quadratic in the number of vertices with a weight-matrix graph and an array-based priority queue, and O(m log n) with an adjacency-list graph (n vertices, m edges) and a min-heap.
Kruskal's algorithm
Kruskal's algorithm views a minimum spanning tree as an acyclic subgraph with one fewer edge than the number of vertices whose total edge weight is smallest. It sorts the edges in nondecreasing order of weight and grows the tree one edge at a time through expanding forests, adding the next edge unless doing so would create a cycle — in which case the edge is skipped.
Cycle checking and union-find
Kruskal's algorithm looks simpler than Prim's but is harder to implement because of cycle checking: a cycle is created exactly when an added edge connects two vertices already in the same connected component. Checking this efficiently uses one of the union-find algorithms.
Dijkstra's algorithm
Dijkstra's algorithm solves the single-source shortest-paths problem: given a weighted connected graph, it finds shortest paths from a source vertex to every other vertex. It resembles Prim's but, among vertices not yet in the tree, it selects the vertex u minimising the sum of the shortest-path length already found to a tree vertex v plus the weight of the edge from v to u. Its efficiency is O(|V| squared) with a weight-matrix graph and an array-based priority queue, and O(|E| log |V|) with an adjacency-list graph and a min-heap.
Notes on Dijkstra's algorithm
Dijkstra's algorithm does not work for graphs with negative weights, but it is applicable to both undirected and directed graphs. The course warns explicitly not to mix it up with Prim's algorithm.
Coding and prefix-free codes
Coding assigns bit strings (codewords) to alphabet characters. There are two types: fixed-length encoding such as ASCII, and variable-length encoding such as Morse code. A prefix-free code is one in which no codeword is a prefix of another. The coding problem asks, given the character frequencies, for the best binary prefix-free code.
Huffman codes and algorithm
Any binary tree with edges labelled 0 and 1 yields a prefix-free code for the characters at its leaves; the optimal such tree minimises the expected codeword length. Huffman's algorithm, one of the most important file-compression methods, initialises one-node trees weighted by the characters' frequencies and then, n-1 times, joins the two trees of smallest weight into one whose weight is their sum, labelling the edges 0 and 1. The result is a Huffman tree.
MODULE 12Ch 11 · Limitations of Algorithm Power
How good an algorithm can possibly be, and which problems are hard: lower bounds and decision trees, lower bounds by reduction, and the classes P, NP, and NP-complete.
Lower bounds
A lower bound is an estimate of the minimum amount of work needed to solve a given problem — for example, the number of comparisons needed to find the largest element, to sort an array, or to search a sorted array, or the number of multiplications to multiply two n-by-n matrices.
Tight lower bounds
A lower bound can be given as an exact count or as an efficiency class. A lower bound is tight when there exists an algorithm with the same efficiency as the lower bound. For example, sorting has a tight lower bound of n log n, searching a sorted array log n, and element uniqueness n log n; the lower bounds for n-digit integer multiplication (n) and n-by-n matrix multiplication (n squared) are not known to be tight.
Methods for establishing lower bounds
Four methods establish lower bounds: trivial lower bounds, information-theoretic arguments (decision trees), adversary arguments, and problem reduction.
Trivial lower bounds
Trivial lower bounds are based on counting the number of items that must be processed in the input and generated as output. Examples include finding the maximum element, polynomial evaluation, sorting, element uniqueness, and Hamiltonian-circuit existence. They may or may not be useful, and one must be careful in deciding how many items must be processed.
Decision trees
A decision tree models algorithms that use comparisons: internal nodes represent comparisons and leaves represent outcomes. Any comparison-based sorting algorithm can be represented by a decision tree.
Decision trees and sorting
Any comparison-based sorting algorithm corresponds to a decision tree with at least n! leaves (the orderings), so a binary tree with n! leaves has height at least the ceiling of log2 n!. This gives a worst-case lower bound of about n log2 n comparisons for any comparison-based sorting algorithm, a bound that is tight and achieved by mergesort.
Lower bounds by problem reduction
Lower bounds can be established by reduction: if a problem P is at least as hard as a problem Q, then a lower bound for Q is also a lower bound for P. So one finds a problem Q with a known lower bound that can be reduced to the problem P in question. For example, reducing element uniqueness (known to be n log n) to finding the minimum spanning tree of points in the plane shows MST is also n log n.
Tractability and problem types
Complexity theory classifies problems as tractable or intractable, into optimisation and decision problems, and into the classes P, NP, and NP-complete. A problem is tractable if a polynomial-time algorithm solves it. Some problems are provably unsolvable by any algorithm, such as Turing's halting problem, and others provably require exponential time.
Optimisation versus decision problems
An optimisation problem finds a solution that maximises or minimises an objective function, while a decision problem answers a question yes or no. Many problems have both versions — for the TSP, the optimisation version finds a minimum-length Hamiltonian cycle and the decision version asks whether one of length at most m exists. Decision problems are more convenient for the formal study of complexity.
Class P
P is the class of decision problems that are solvable in polynomial time, where the polynomial is in the problem's input size. Examples include searching, element uniqueness, graph connectivity, graph acyclicity, and primality testing, which was finally proved to be in P in 2002.
Class NP
NP, nondeterministic polynomial, is the class of decision problems whose proposed solutions can be verified in polynomial time, equivalently solvable by a nondeterministic polynomial algorithm. Such an algorithm is an abstract two-stage procedure: it generates a random string that may solve the problem, then checks in polynomial time whether the solution is correct.
CNF satisfiability
CNF satisfiability asks whether a Boolean expression in conjunctive normal form is satisfiable — whether there are values of its variables that make it true. It is in NP: a nondeterministic algorithm guesses a truth assignment and substitutes the values into the formula to see if it evaluates to true.
Problems in NP and P versus NP
Problems in NP include Hamiltonian-circuit existence, the partition problem (splitting n integers into two subsets of equal sum), and the decision versions of TSP, knapsack, and graph colouring; a few problems such as MST and shortest paths are exceptions that are easier. Every problem in P is also in NP, so P is contained in NP, and the big open question is whether P equals NP.
NP-complete problems
A decision problem D in NP is NP-complete if it is as hard as every problem in NP: D is in NP, and every problem in NP is polynomial-time reducible to D. NP-complete problems are the hardest problems in NP.
Cook's theorem
Proving that every NP problem reduces to a given problem is not easy. Cook's theorem of 1971 established that CNF-satisfiability is NP-complete — the first problem proved NP-complete. Other problems, such as TSP, knapsack, partition, and graph colouring, are then proved NP-complete by polynomial-time reductions from a known NP-complete problem.
The P = NP question
If P equals NP, then every problem in NP, including all NP-complete problems, could be solved in polynomial time. Indeed, discovering a polynomial-time algorithm for just one NP-complete problem would imply P equals NP. Most, but not all, researchers believe that P is a proper subset of NP, and the question is the most important unresolved issue in theoretical computer science.