Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 30

The author discusses fast fourier transform (FFT). The author defines a polynomial of variable $x$ over a field $F$. The author defines coefficients of the polynomial and degree of a polynomial. The author defines two operations; polynomial addition and multiplication.

The author describes two ways to present polynomials:

• Co-efficient representation
• Point-value representation

The author proves uniqueness of an interpolating polynomial theorem and and provides a method for fast multiplication of polynomial in co-efficient form.

The author then defines complex roots of unity, study their properties, define the Discrete Fourier Transform, (DFT) and then show how the FFT computes the DFT and its inverse in $O(n \lg n)$.

The author then proves cancellation Lemma, halving Lemma and summation Lemma. The author also define and prove Convolution theorem.

The author then provides two efficient FFT implementations, an iterative FFT implementation and a parallel FFT circuit.

Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 29

The authors start with a discussion of linear programming. The authors define the concepts of linear function, linear equality and linear inequality and linear programming problem. The author defines feasible region, feasible solution, objective solution and objective value.

The author then describes simplex algorithm which takes linear program as an input and generates an optimal solution.

The author then describes uses of linear programming ranging from operations research, solving graph and combinatorial problems. The author then discusses algorithms for linear programming like ellipsoid algorithm, interior-point methods, and integer linear program.

The author then describes two formats:

• Standard Form
• All the constraints in this form are inequalities. The author provides the description of the problem in standard form and then provides a method to convert linear program to a standard form.
  
• Slack Form
• All the constraints in this form are equalities. The author provides a method to convert linear program to a slack form.

The author then formulates following four problems as linear program:

1. Shortest paths
2. Maximum flow
3. Minimum cost flow
4. Multicommodity flow

The author then describes simplex algorithm and prove some lemmas.

The author then discusses about linear programming duality. The author then prove some lemmas and theorem and prove them.

The author then describes a method to find a basic feasible solution to test that a linear program is feasible. The author then defines and proves some lemmas.

The author then defines fundamental theorem of linear programming as follows:
Any linear program L, given in standard form, either

1. has an optimal value with a finite objective value.
2. is infeasible or
3. is unbounded.

The author also provides a proof for it.

Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 26

The authors discuss about flow networks in this chapter. A flow network is a directed graph $ G = (V, E) $ in which every edge $(u,v) \in E$ has a nonnegative capacity $ c(u,v) $ associated with it. If $(u,v) \notin E $ then $ c(u,v) = 0 $. There are two distinguished vertices source $s$ and sink $t$. For every vertex $v$, there is a path $ s \leadsto v \leadsto t $. A flow in $G$ is defined as follows:

* Capacity constraint: For all $u,v \in V$, $ f(u,v) \le c(u,v) $.
* Skew symmetry: For all $u,v \in V$, $ f(u,v) = -f(v,u) $.
* Flow conservation: For all $u \in V - {s,t}$, we require $ \displaystyle\sum\limits_{v \in V} f(u,v) = 0 $.

The value of a flow $f$ is defined as $ |f| = \displaystyle\sum\limits_{v \in V} f(s, v) $. In the maximum flow problem, given a flow network $G$ with source $s$ and sink $t$, our aim is to find flow of maximum value.

The authors describe networks with multiple sources and sinks and provides a way to convert it to a single source single sink problem. The authors then prove some properties of flow.

The authors first define residual flow between a set of vertices $ u,v \in V $ as
$ c_f (u,v) = c(u,v) - f(u,v) $.
The residual network of $G$ introduced by $f$ is $G_f = (V,E_f) $ where $ E_f = { (u,v) \in V \times V : c_f(u,v) > 0} $. Each edge that is part of residual network is called residual edge and as per the definition has a positive residual flow. The author points out that the residual network $G_f$ is also a flow network with capacities given by $c_f$. The authors define augmenting path $p$ as a simple path in the residual network from $s$ to $t$ in the residual network $G_f$ such that each edge $(u,v)$ admits an additional positive flow from $u$ to $v$ without violating the capacity constraint on the edge.

The authors then prove some lemmas and theorems on the property of residual network which are as follows:

• Let $f$ be a flow in a flow network $G$ with source $s$ and sink $t$ and $(S,T)$ be a cut of $G$. Then the net flow across $(S,T)$ is $f(S,T) = |f|$.
• Max-flow min-cut theorem: If $f$ is a flow in a flow network $G=(V,E)$ with source $s$ and sink $t$, then the following conditions are equivalent:
  
  • $f$ is a maximum flow in $G$.
  • The residual network $G_f$ contains no augmenting paths.
  • $|f| = c(S,T)$ for some cut $(S,T)$ of $G$.

The authors then descibe Ford-Fulkerson algorithm for finding the maximum flow of a flow network. The authors also derive that the running time of the algorithm is $O(E |f*|)$ where $f*$ is the maximum flow found by the algorithm.

The authors then describe Edmonds-Karp algorithm and prove its running time to be $O(V \times E^2)$.

The authors then discuss the problem of maximum-bipartite-matching. A matching for a given undirected graph $G = (V,E)$ is a subset of edges $M \subset E$ such that for all vertices $v \in V$, at most one edge of $M$ is incident on $v$. A maximum matching is a matching with the maximum cardinality. The authors provide a way to transform a bipartite graph to a network flow graph and show how solution obtained by application of Ford-Fulkerson method to such graph is a solution to maximum matching problem.

The authors then discuss push-relabel algorithms which, unlike Ford-Fulkerson method, do not maintain the flow-conservation property throughout their execution. The authors also define the concept of excess flow and an overflowing vertex. The authors then describe the basic intuition behind push-relabel algorithm and define the two main operations PUSH and RELABEL for the algorithm.

The authors then prove many lemmas and theorems to prove the correctness of the push-relabel method and prove the running time of the algorithm to be $O(V^2 \times E)$.

The authors then discuss the relabel-to-front algorithm. The authors define the concept of admissible edge and admissible network. The authors then prove some lemmas proving properties of admissible network including that the admissible network is acyclic. The authors introduce the concept of neighbour-list for a vertex. The authors then describe operation DISCHARGE which uses neighbour-list as well as PUSH and RELABEL operations.

The authors then describe RELABEL-TO-FRONT algorithm and proves its running time to be $O(V^3)$.

Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 28

The authors discuss some common definitions related to matrix, e.g. transpose, vector, column vector, row vector, unit vector, zero matrix, diagonal matrix, square matrix, identity matrix, tridiagonal matrix, upper-triangular matrix, unit upper-triangular matrix, lower-triangular matrix, unit lower-triangular matrix, permutation matrix, symmetric matrix, matrix addition, scalar multiple of a matrix, negative of a matrix, matrix subtraction, matrix multiplication, inner product, outer product, inverse, determinant, positive definite matrix.

The authors then describe Strassen's algorithm for matrix multiplication. The authors then discuss solving systems of linear equations and the use of matrix in solving them. The authors also discuss the concept of LUP decomposition of a matrix A. The authors also discuss forward-substitution and back-substitution to solve lower triangular system. The authors first describe a method in which $P=I_n$ and $A$ is decomposed into two matrices $L$ and $U$. The authors provide an algorithm to do it and proves its running time to be $\Theta(n^3)$. On the basis of this algorithm, the authors provide LUP-decomposition algorithm and proves its running time to be $\Theta(n^3)$.

The authors then prove that running time of matrix inversion and multiplication is of the same order.

Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 27

The authors define the concept of a comparator and a wire. The authors extend it to input wires and output wires and input sequence and output sequence. The authors also define the concept of comparison network and lines. The authors define the concept of depth of a wire as well as the time it takes for a comparison network to generate output. The author also defined the concept of sorting network.

The authors describe and prove Zero-one principal for sorting networks which says that if a sorting network works correctly when each input is drawn from set $\{0,1\}$, then it works correctly on arbitrary input numbers.

The authors then provide the concept of bitonic sequence, a sequence that monotonically increases and then monotonically decreases. A bitonic sorter is a comparison network that sorts bitonic sequence. Every stage of a bitonic sorter is called half-cleaner. The authors then prove some lemmas and describe how to build bitonic sorter from half-cleaner.

The authors then provide the design of a merge network.