Sorting Network

- A basic comparator
- Comparison network
- Depth of a sorting network
- Sorting network for insertion sort - $O(n^2)$ gates and $2n-1$ time units to sort n numbers

Zero-One Principle
A comparison network that can sort all binary inputs correctly can sort any input correctly
Proof:
Using the following lemma -
If a comparison network transforms input sequence $<a_1,\cdots ,a_n>$ to $<b_1,\cdots ,b_n>$, then for any monotonically increasing function $f$, the comparison network would transform $<f(a_1),\cdots , f(a_n)>$ to $<f(b_1),\cdots , f(b_n)> $

Given a sorting network with $n$ inputs which sorts all binary strings of length $2^n$ correctly, we need to show that it sorts all sequences correctly. We prove this by contradiction.

Let the network sort $a_1, \cdots, a_n$ incorrectly, i.e, $\exists \; a_i, a_k$ such that $a_i < a_k$ but $a_k$ proceeds $a_i$ in the output sequence (sorting being in ascending order). We define a monotonically increasing function $f$ as follows

\[
f(x) = \left\{
\begin{array}{ll}
0 & x\leq a_i \\
1 & x>a_i \\
\end{array}
\right.
\]

Now using the above lemma if the input is a binary string defined by $<f(a_1),\cdots , f(a_n)>$, then the output string would also be a binary string but with $f(a_k)$ appearing before $f(a_i)$. This is a contradiction to our hypothesis that the network sorts every binary string correctly. 

Hence proved by contradiction.

Definition: Bitonic Sequence

A sequence which first increases and then decreases or can be converted to such form by circular shifting. A binary bitonic sequence is either of the form $0^i1^j0^k$ or $1^i0^j1^k$

Definition: Half Cleaner

A comparison network which connects $i^th$ line with $(i+\frac{n}{2})^th$ line. For binary bitonic sequences it results in two possible cases:

- Top $\frac{n}{2}$ is $0$s and bottom half is a bitonic sequence

- Bottom $\frac{n}{2}$ is $1$s and top half is a bitonic sequence

Note- This provides a recursive way of sorting binary bitonic sequences. Also given two sorted sequences, a bitonic sequence can be easily obtained by flipping and concatenating the second sequence to the first sequence. This gives us the construction of Merge network whose components are listed below.  

Sorting Network

- Sort top $\frac{n}{2}$

- Sort bottom $\frac{n}{2}$

- Merge

      - Flip-Cleaner$[n]$

      - Top Bitonic Sorter$[n]$

      - Bottom Bitonic Sorter$[n]$

Number of Comparators required in Merge Circuit: $O(\frac{n}{2}log \;n)$

Number of Comparators required in the sorting network:

\begin{align}
G(n) &= 2G(\frac{n}{2}) + O(\frac{n}{2}log \;n) \\
\implies G(n) &= O(n \; log^2 \; n)
\end{align}

Depth of Merge Circuit: $O(log\; n)$

Depth of sorting network:

\begin{align}
D(n) &= D(\frac{n}{2}) + O(log\; n) \\
\implies D(n) &= O(log^2 \; n)
\end{align}

Yeah!! This is significantly better than $O(n \; log \; n)$ time taken by programmatic sorting algorithms. 

Fast Polynomial Multiplication using FFT

• Point Value Representation of Polynomial
• Linear time polynomial multiplication in point value form
• Collapsible Set ($n$ $n^{th}$ roots of unity)
• Computing a polynomial in $O(nlogn)$ time on a collapsible set of size $n$
• Converting from point value form to standard polynomial form in $O(nlogn)$ time using the fact that Inverse of the Vandermonde matrix is just a permutation of the rows of the Vandermonde matrix 

Rasterization

Definition: Discretization of a shape, line or polygon specified by continuum of vector coordinates into pixel coordinates used to render it.

Line Rasterization: Bresenham Line Algorithm
Assumption: The start and end point lie on integer pixel coordinate

Problem: Which pixels to render while drawing a line joining $(x_0,y_0)$ and $(x_1,y_1)$

Step 1:
Project the line into first octant such that $(x_0,y_0)$ is projected to origin and $(x_1,y_1)$ is mapped to $(x',y')$ such that
- $x' \geq 0$
- $y' \geq 0$
- $x' \geq y$

Step 2:
$P \rightarrow $ the start pixel
$M \rightarrow $ the first midpoint
$M_{E} \rightarrow $ the next midpoint given we choose to render E
$M_{NE} \rightarrow $ the next midpoint given we choose to render NE pixel

Define $f(x,y) = mx + b - y$ where $y = mx + b$ is the equation of the line projected in first octant.
$f(M) = f(P_x + 1, P_y + \frac{1}{2}) = f(P) + m - \frac{1}{2}$
$f(M_E) = f(M) + m$
$f(M_{NE}) = f(M) + m - 1$

Now, $m = \frac{\Delta y}{\Delta x} \geq 0$. So define
$F(M) = 2 \Delta x f(M)$
$F(M_E) = 2 \Delta x f(M_E) = F + 2 \Delta y $
$F(M_{NE}) = 2 \Delta x f(M_{NE}) = F + 2 \Delta y - 2 \Delta x$
$F(M_{init}) = 2 \Delta y - \Delta x$

Final Algorithm:
$y = y_0$
$F = 2 \Delta y - \Delta x$
for $x=x_0:x_1$
  Render $(x,y)$
  if$(F \leq 0 )$     \* Take the East *\
      $F = F + 2 \Delta y$
  else$(F > 0)$     \* Take the North East *\
      $F = F + 2 \Delta y - 2 \Delta x$
end

Polygon Rasterization
First enforce consistent set of rules for when does a pixel belong to a polygon. The ambiguous case is when the edge passes through the pixel center. The other case is trivial.

The polygon will be rasterized one scanline at a time where the scanline progressively moves up.

Each edge is represented by coordinates $(x_{lower},y_{lower}),(x_{upper},y_{upper})$.

Maintain an Active Edge data structure with the following three fields
- $x$ coordinate where a scan line intersects the edge
- $\frac{dx}{dy}$
- $y_{upper}$
The entries (basically edges and their properties) in this data structure are sorted in order of $x$ first and $\frac{dx}{dy}$ next.

Algorithm:
- Add edges with $y = y_{lower}$ along with their attributes in the Active Edge data structure
- For every pair $(2i-1,2i)$ render pixels in the range $\lceil x_i \rceil$ to $\lceil x_{i+1} \rceil  - 1 $
- Remove edges with $y_{upper} = y$
- Update $x$ by $x = x + \frac{dx}{dy}$

Gouraud Interpolation
While rasterizing polygons, we need to interpolate vertex attributes such as colors to get the colors at the rendered pixels.
To do this:
- Maintain the attribute value along the edges of the  polygon in the Active Edge data structure
- Whenever we move the scan line up, update the attribute by $val = val + \frac{val_{upper}-val_{lower}}{y_{upper}-y{lower}}$
- When scanning from left to right the pixels are assigned attributes by $val = val + \frac{val_{right}-val_{left}}{x_{right} - x_{left}}$

Applications of Network Flow

Circulation with Demands

Given:
- Graph $G(V,E)$
- Capacities on the edges
- Demands for each vertex ${d_v}$ such that
    - $d_v > 0 \implies$ Net flow into vertex (Source)
    - $d_v < 0 \implies$ Net flow out of vertex (Sink)
    - $d_v = 0 \implies$ Inflow equals outflow (Normal Node)

Definition: Circulation
Circulation is a function $f: E \rightarrow \mathbb{R}^+$ which satisfies the following
- Bounded by capacity: $f(e) \leq c(e)$
- Conservation condition: $f^{in}(v) - f^{out}(v) = d_v$

Lemma: Necessary condition for Feasible circulation $\rightarrow \sum_v d_v = 0$ 
Proof:
\begin{align}
\sum_v d_v & = \sum_v f^{in}(v) - f^{out}(v) \\
                  & = \sum_v f^{in}(v) - \sum_v f^{out}(v) \\
                  & = 0
\end{align}
Since flow on every edge appears twice once as inflow on a vertex and other time as outflow on the other vertex on that edge.
In other words, there is a feasible solution only if $D = \sum_{v>0}d_v = \sum_{v<0} {- d_v}$

Algorithm: Finding Circulation 
- Check necessity condition
- Connect all vertices with $d_v < 0$ to a super source via edges with capacity $-d_v$
- Connect all vertices with $d_v > 0$ to a super source via edges with capacity $d_v$
- On this flow network $H$, compute max-flow
- If flow value is $D$, then we have a valid circulation
- Else, circulation is infeasible

Correctness:
If there is a valid circulation in $G$, then in $H$ there is a $s-t$ max flow with value $D$ obtained by pushing full capacities from source to the vertices with negative demand.

Conversely, a max-flow with value $D$ in $H$ is possible only when full capacities of the subordinate sources are used which implies that both capacity constraint and conservation condition are maintained. Hence there is a valid circulation in $G$.

Circulation with Demands and Lower bounds

Given:
- Graph $G(V,E)$
- Capacities on the edges
- Demands for each vertex ${d_v}$
- Lower bound for each edge $\ni l(e) \leq c(e)$

Now, a valid circulation is one where $l(e) \leq f(e) \leq c(e)$.

Algorithm: Get rid of the lower bound somehow and then solve the circulation with demands
- Push a flow equal to the lower bound on each edge
- It satisfies the bounds
- Does not satisfy the conservation of flow
- Let $L_v = f^{in}(v) - f^{out}(v)$ be the residual demand
- Set the new $d'_v = d_v - L_v$ and reduce the capacities to $c'(e) = c(e) - l(e)$ to get new graph $G'$
- The lower bounds vanish
- Solve the circulation problem in $G'$
- Add the circulation to the lower bounds $f = f_0 + f'$

Correctness:
Want to show that $G$ has valid circulation with demands and lower bounds if and only if $G'$ has a valid circulation with demands.
First we show, $(f \text{ is valid } \implies f' \text{ is valid } )$
- $f(e) - l(e) \leq c(e) - l(e) \implies f'(e) \leq c'(e) \rightarrow$ hence bounded by capacity
- $\sum_{e \; into \; v } (f(e) - l(e)) - \sum_{e \; out \; of \; v} (f(e) - l(e)) = d_v - L_v \rightarrow$ hence flow is conserved

Now we show, $(f '\text{ is valid } \implies f \text{ is valid } )$
- Clearly $l(e) \leq f_0(e) + f'(e) \leq l(e) + c'(e) = c(e) \rightarrow $ hence satisfies the bounds
- $\sum_{e \; into \; v } (l(e) + f'(e)) - \sum_{e \; out \; of \; v} (l(e) + f'(e)) = L_v + (d_v - L_v) = d_v \rightarrow$ hence the flow is conserved

Hence proved.

Survey Design

Problem Statement:
Given:
- Set of consumers
- Set of products
- List of products that each consumer has consumed

Want:
- To ask questions to the consumer about a subset of the products that the consumer used
- $i^{th}$ consumer would answer only questions in the range $[c_i, c'_i]$
- For the $i^{th}$ product we want to ask question in the range $[p_i, p'_i]$

Question:
How to assign questions to the consumers so that we get required information about each product while keeping the consumers happy?

Algorithm:
- Form a Bipartite graph with consumers on one side and products on the other
- Connect the consumers with the products that they used by an edge with capacity $1$
- Connect the consumers to a source $S$ with edges of capacities with lower $(c_i)$ and upper $(c'_i)$ bound
- Connect the products to a sink $T$ with edges of capacities with lower $(p_i)$ and upper $(p'_i)$ bound
- We want to get a flow from $S$ to $T$
- But we only know how to compute a circulation
- So connect $T$ to $S$ by an edge of infinite capacity
- Demands on all the vertices including source and sink is 0
- Happily compute a circulation with lower bounds on this network

Time Complexity: 
- $n$ consumers
- $u$ products
- $m \leftarrow$ sum of the number of products used by the consumers
- $|E| = m$
- $|V| = n + u$
- $O(|V||E|^2) = O((n+u) m^2)$

Applications of Network Flow

Edge Disjoint Paths Problem

Given:
- Directed or undirected graph $G$
- Vertices $s$ and $t$
- Parameter k

Task: Compute $k$ edge disjoint paths from $s$ to $t$

Directed Graph

Lemma: Number of edge disjoint paths equals max flow
- Construct a network flow $H$ where all edges have capacity $1$
- Since capacities are integral, the max-flow would have either $0$ or $1$ unit of flow on each edge
- Such a flow is called $0/1$ flow
- $|f_H| = \text{number of edge disjoint paths in G}$

Proof: Unclear

Algorithm:
- Start walking from $s$ along an edge with flow $1$
- If reach $t$, then add the path to the set of edge disjoint paths
- Else if reached a vertex a second time (a cycle!), then remove the edges that form the cycle
- Since $|f| \leq |V|$, Ford-Fulkerson outputs the flow in $O(|V||E|)$ time
- Extracting the paths from the flow takes $O(|E|)$ time
- Hence edge disjoint paths can be found in $O(|V||E|)$ time

Lemma: Maximum number of edge disjoint paths equals the minimum number of edges whose removal separates s from t
Proof:
$U \leftarrow$  set of edge disjoint paths
$F \leftarrow$ set of removed edges such that $s$ and $t$ are disconnected
First show $|U| \leq |F|$
- $F$ must contain at least one edge from each path in $U$
- Hence $|U| \leq |F|$

Now,
- $S = \{v \in V | \exists \text{ path from } s \text{ to } t \text{ which does not use any edge in } F \}$
- $T = V \setminus S$
- $F$ defines a cut $(S,T)$
- Clearly $|F| \geq c(S,T)$
- Any edge in $F$ that is not in the cut can be discarded to get $F_{minimal}$
- $|F_{minimal}| = c(S,T)$
- The smallest such set has size, $|F^*| = $ min-cut in $G$
- By Max-Flow Min-Cut theorem $|F^*| = |f_{max}|$, i.e max-flow in $G$
- By previous lemma $|F^*| = $ number of edge disjoint paths

Undirected Graph

- Double every edge to give 2 directed edges

- Repeat the algorithm for directed case

- Again $f$ might push flow along both $(u\rightarrow v)$ and $(v\rightarrow u)$ 

- But this is a cycle!

- Remove cycle and get on with life

Texture Mapping

Set of mappings from Model Coordinates (Object Space) to Texel Values 

- Object space $(x,y,z) \rightarrow $ Parameter space $(u,v)$

- Parameter space $(u,v) \rightarrow $ Texture Image space

- Texture Image space $ \rightarrow $ Texel Values

- Transformation of Texel Values /*optional*/

Resolving mismatch between number of pixels required for rasterizing geometry and the number of texels it maps to

Issues:

- Magnification Aliasing:

  - Source of Jaggies

  - Occurs when texture image is smaller than the rasterization

  - Multiple screen pixels map to the same texture image coordinates

  - Solution: Bilinear Interpolation is required to pick the value from the inverse mapping from screen pixel coordinates onto the texture image coordinates

- Minification Aliasing:

  - Occurs when texture image is larger than rasterization

  - Multiple texture image coordinates map to the same screen pixel

  - It is inefficient to compute the average of all these texels

  - Solution: MIP mapping

MIP (multum im parvo) Mapping:

- Generate a precomputed image pyramid where each lower resolution image is half the dimension of its predecessor

- While doing texture mapping, choose the texture image resolution whose projected texel size closely matches the pixel size

Choosing MIP map level:

$(x,y)$ be the screen pixel coordinates and $(u,v)$ be the texel coordinates. Compute the change in the $u,\; v$ along $x,\; y)$. Choose the resolution for which the $\text{max}(\frac{\partial u}{\partial x},\frac{\partial u}{\partial y},\frac{\partial v}{\partial x},\frac{\partial v}{\partial y})$ is closest to $1$.

Bump Mapping
- Store the height field in a texture
- Perturb the geometric normal by the slopes in the height field along the directions of the tangent and bi-tangent
- Use this normal for lighting computation
Alternatively: Store the normals themselves

Environment Mapping
- An environment map stores the view in every direction from a single point
- It assumes that the objects environment is infinitely distant from the object
- While rendering a point on the object
    - Compute the reflection direction
    - Look up the color stored in that direction in the environment map
    - Use this color to render the point

Sphere Map
A sphere map is a technique that allows us to store the precomputed view in every direction  from a point. It is basically, a photograph of a reflective sphere placed in the environment.
Issues: Distortion towards the edge of the sphere
Solution: Use Cube mapping instead of Sphere

Other uses of texture mapping
- Can implement shading as texture mapping
- Can implement Seeliger lighting model for more realistic skin color rendering

Network Flow

A flow network comprises of :

- A directed graph $G(V,E)$

- Non-negative capacities on each edge $c(u,v)$

- A source $s$

- A sink $t$

Definition: Flow

Flow is a function $f:E\rightarrow \mathbb{R}$ such that the following properties hold

- Bounded by Capacity: $f(u,v) < c(u,v)$

- Anti-Symmetry: f(u,v) = -f(v,u)

- Conservation of flow: For any node $u$ that is neither source nor sink, $\sum_{v\in V} f(u,v) = 0$

- Special vertices $s$ and $t$ such that all flow starts from $s$ and ends at $t$ 

Definition: Value of Flow

$\text{Value of flow} = |f| = \sum_v f(s,v)$

Definition: Residual Capacity

Given the capacity $c$ and flow $f$, the residual capacity of an edge $u \rightarrow v$ is 

\begin{align}
c_f(u,v) = c(u,v) - f(u,v)
\end{align}

Note - Even if there is no directed edge $u \rightarrow v$ in the graph, i.e $c(u,v) = 0$ it might still have a non-zero residual capacity.

Definition: Residual Graph

For a flow $f$ in a graph $G(V,E)$ the residual graph $G_f(V,E_f)$ is the graph with all edges with positive residual capacity, i.e

\[
E_f = \{(u,v)\in \left(V \times V\right)| c_f(u,v)>0\}
\]

Note - Because of the note above $|E_f|<2|E|$ because each edge in $G$ can induce at most 2 edges in $G_f$.

Lemma: 
The flow generated by adding the flows in the graphs $G(V,E)$ and $G_f(V,E_f)$ is also a valid flow in $G$ with a higher flow value
\[

|f+h| = |f| + |h|

\]

Note - $(f+h)(u,v)$ is defined as $f(u,v) + h(u,v)$.

Definition: Augmenting Path
For graph $G$ and a flow $f$, any directed path, $\pi$ from $s$ to $t$ in $G_f$ is called an augmenting path. The maximum flow that can be pushed through $\pi$ is denoted by $c_f(\pi)$ where
\[
c_f(\pi) = \max_{(u\rightarrow v)\in \pi} c_f(u,v)
\]
Note - $c_f(\pi)$ is always positive by definition of Residual Graph.

Lemma: Improving the flow in $f$ using an Augmenting Path
Let $f$ be a flow in $G$ and $f_{\pi}$ be a flow on an augmenting path, $\pi$, in $G_f$. The $f+f_{\pi}$ is a better flow in $G$ since $|f+f_{\pi}| = |f| + |f_{\pi}| > |f|$.

Problem: Max Flow
Given a network flow, find the maximum flow, i.e, maximum possible value of $|f|$.

Algorithm: Ford Fulkerson Method
1. Initialize $f(u,v) = 0 \; \forall \; (u,v) \in E$
2. Compute residual graph $G_f$
3. Find an augmenting path, $\pi$, in $G_f$
4. Update flow in $G$ by $f \leftarrow f + f_{\pi}$
5. Repeat 2-5 until there are no augmenting paths left in $G_f$

Definition: Directed Cut
A directed cut $(S,T)$ in a flow network is a partitioning of $V$ into disjoint sets $S$ and $T = V\setminus S$ such that $s\in S$ and $t\in T$. Standard terminology -
- Net flow of $f$ across a cut $(S,T)$, is $f(S,T) = \sum_{u\in S, v\in T}f(u,v)$
- Capacity of cut $(S,T)$ is $c(S,T) = \sum_{u\in S, v\in T}c(u,v)$
- Minimum cut is the cut with the minimum capacity (*\ important \*)

Lemma: Value of flow in network is the flow across any cut
$f(S,T) = |f| \; \forall \; \text{cuts} \; (S,T)$
(*\Proof is a one liner but worth looking at\*)

Lemma: Flow is bounded above by capacity of any cut $(S,T)$ in G
$|f| \leq c(S,T) \; \forall \; \text{cuts} \; (S,T)$

Theorem: Max-flow Min-cut 
If $f$ is flow in a flow network $G(V,E)$ with source $s$ and sink $t$, then the following statements are equivalent
A. $f$ is the Max-flow
B. $\nexists$ augmenting path in $G_f$
C. $\exists \; \text{cut} \; (S,T) \ni |f| = c(S,T)$ and $(S,T)$ is a Min-cut

Proof:
$(A \implies B)$
If augmenting path $\pi$ did exist in $G_f$ then we could have further improved the flow in $G$ by the amount $|f_{\pi}| = c_f(\pi)$. Hence a contradiction

$(B \implies C)$
Define $S = \{v | v \in V \; and \; \exists \; \text{a path from s to v in} G_f\}$. Let $T = V \setminus S$. Then,
\[
|f| = f(S,T) = \sum_{x\in S, y\in T}f(x,y) = \sum_{x\in S, y\in T}c(x,y) = c(S,T)
\]
Note - If $f(x,y) \neq c(x,y)$, then $c_f(x,y) > 0 \implies (x \rightarrow y)$ is an edge in $G_f$. This would further have implied that $y \in S$ which contradicts the construction of S.

Also, $(S,T)$ has to be a Min-cut because if it were not then it would have implied that $\exists \; cut (S', T') \ni c(S',T') < c(S,T) = |f|$. But we know that $|f| \leq c(S,T) \; \forall (S',T')$. Hence a contradiction.

$(C \implies A)$
Since $|f|$ is bounded above by the capacity of any cut and we have $|f| = c(S,T)$ for some cut, implies that $|f|$ is the max-flow.

Hence proved.

Conclusion
By Max-cut Min-Flow theorem, it follows that if Ford-Fulkerson terminates then it would be a max-flow. But does Ford-Fulkerson terminates?

Claim: Ford-Fulkerson terminates for integral edge capacities
- Ford Fulkerson only performs additions, subtractions and min operations.
- So if it finds an augmenting path, $\pi$, then $c_f(\pi)$ is a positive integer, i.e, $c_f(\pi) \geq 1$.
- In every iteration we would be improving the flow by at least 1.
- If the value of max-flow is $|f^*|$ then in at most $|f^*|$ steps the algorithm will terminal
- In every iteration calculating the augmenting path takes $O(|E|)$ time (BFS or DFS).
- Hence, the algorithm run in $O(|f^*| |E|) $

Integrality Theorem
If all capacities are integral, then the flow $|f|$ generated by Ford-Fulkerson is integral since max-flow equals min-cut which is integral. Also the flow $f(u,v)$ on every edge is integral.

Algorithm: Edmonds - Karp
It is an efficient implementation of Ford-Fulkerson using BFS to find the shortest augmenting path in each iteration. It is meant to deal with the situation where $|f^*|$ is very large.

Definition: 
For a flow $f$, $\delta_f(v)$ is the length of the shortest path from $s$ to $v$ given that each path is of unit length.

Lemma: $\delta_f(v)$ increases monotonically with every flow augmentation

Lemma: Bound on the number of disappearances of an edge in residual graph
The number of times an edge can disappear (and reappear) in the residual graph is at most $|V|/2$.

Proof:
- Let $f$ be the flow in the iteration when edge $(u\rightarrow v)$ disappears from $G_f$
- $(u\rightarrow v)$ must have been in the augmenting path $\pi_f$
- $\delta_f(v) = \delta_f(u) + 1$
- Let $g$ be the flow in the iteration when edge $(u\rightarrow v)$ reappears in in $G_g$
- $(v\rightarrow u)$ must have been in the augmenting path $\pi_g$
- $\delta_g(u) = \delta_g(v) + 1$
- By monotonicity of $\delta$, $\delta_g(u) \geq \delta_f(u) + 2$
- But $\delta_g \leq |V|$
- This can happen at most $|V|/2$ times
Hence proved

Time Complexity of Edmonds - Karp
- In every iteration, at least one edge (namely the one which realizes the residual capacity of the augmenting path in the residual graph) will disappear.
- Total number of disappearances is $\frac{|V||E|}{2}$
- In each iteration finding the shortest path takes $O(|E|)$ time
- Algorithm runs in $O(\frac{|V||E|^2}{2})$ time

Applications of Max-Flow
- Maximum Bipartite Matching can be solved in $O(|V||E|)$ time
- There is a simple extension for multiple sources and sinks by simply connecting them with a Super source and sink with edges of infinite capacity