CS341

Professor: Armin Jamshidpey | Term: Winter 2025

Lecture 1

Syllabus

• Divide-and-conquer, master theorem
• Breadth-first and depth-first search
• Greedy algorithms
• Dynamic Programming
• NP-completeness

Cost of Algorithms

Inputs are parameterized by an integer $n$, called the size.

Runtime of an instance: $T(I)=$ runtime on input $I$

Worst-case Runtime: $T(n)={\max }_{I\text{of size }n}T(I)$

Average Runtime: $T_{\text{avg}}(n)=\frac{{\Sigma }_{I\text{ of size }n}T(I)}{\text{number of inputs of size }I}$

We will sometimes use more than one parameter (i.e. number of rows and columns in a matrix)

Asymptotic Notation - CS240 Review

Consider two functions $f(n),g(n)$ with values in ${\mathbb{R}}_{>0}$

We say that $f(n)\in O(g(n))$ if

$$\begin{array}{r}\exists C>0\text{ and }{n}_0,\text{ such that for }n\ge n_0,f(n)\le Cg(n)\end{array}$$

We say that $f(n)\in \Omega (g(n))$ if

$$\begin{array}{r}\exists C>0\text{ and }{n}_0,\text{ such that for }n\ge n_0,f(n)\ge Cg(n)\end{array}$$

This is equivalent to $g(n)\in O(f(n))$

We say that $f(n)\in \Theta (g(n))$ if

$$\begin{array}{r}\exists C,C^{\prime }>0\text{ and }{n}_0\text{ such that for }n\ge n_0,C^{\prime }g(n)\le f(n)\le Cg(n)\end{array}$$

This is equivalent to $f(n)\in O(g(n))$ and $f(n)\in \Omega (g(n))$

In particular, true if ${\lim }_{\infty }\frac{f(n)}{g(n)}=C$ for some $0<C<\infty$

We say that $f(n)\in o(g(n))$ if

$$\begin{array}{r}\forall C>0,\exists n_0\text{ such that for }n\ge n_0,f(n)\le Cg(n))\end{array}$$

This is equivalent to ${\lim }_{n\to \infty }\frac{f(n)}{g(n)}=0$

We say that $f(n)\in \omega (g(n))$ if

$$\begin{array}{r}\forall C>0,\exists n_0\text{ such that for }n\ge n_0,f(n)>Cg(n)\end{array}$$

This is equivalent to ${\lim }_{n\to \infty }\frac{f(n)}{g(n)}=\infty$

This is also equivalent to $g(n)\in o(f(n))$

Example

$n^k+c_{k-1}{n}^{k-1}+\cdots +c_0\in \Theta (n^k)$

$n^{O(1)}$ means (at most) polynomial in $n$

$n\log (n)$ is in $O(n^2)$ and $\Omega (n)$

Question

$2^{n-1}\in \Theta (2^n)$?

Yes, ${\lim }_{n\to \infty }\frac{2^{n-1}}{2^n}=\frac{1}{2}$

Question

$(n-1)!\in \Theta (n!)$?

${\lim }_{n\to \infty }\frac{(n-1)!}{n!}={\lim }_{n\to \infty }\frac{1}{n}=0$.

Thus, $(n-1)!\in o(n!)$

Consider $f(n,m),g(n,m)$ with values in ${\mathbb{R}}_{>0}$

$$\begin{array}{rl}& f(n,m)\in O(g(n,m))\text{ if }\exists C,n_0,m_0\text{ such that }\\ & f(n,m)\le Cg(n,m)\text{ for }n\ge n_0\text{ or }m\ge m_0\end{array}$$

Less strict definition: $\exists C,n_0,m_0$ such that $f(n,m)\le Cg(n,m)$ for $n\ge n_0$ and $m\ge m_0$

Computational model: word RAM

Rough definition:

• Memory locations contain integer words of $b$ bits each
• Assume $b\ge \log (n)$ for input size $n$
• Random Access Memory: Can access any memory location at unit cost
• Basic operations on words have unit costs

Question

What is the cost of the following?

Sum(A[1...n])
s = 0
for i = 1, ..., n
	s ← s + A[i]

$\in O(n)$

Question

What is the cost of the following?

Product(A[1..n])
s = 1
for i = 1, ..., n
s = s x A[i]

$\in O(n^2)$

1. Big-$O$ is only an upper bound

Typical example: $1$ is in $O(n^2)$ and $n$ is in $O(n)$. Try to give $\Theta$‘s if possible

2. Big-anything hides constants

A $\Theta (n^2)$ will beat a $\Theta (n^3)$ algorithm eventually

3. We use a simplified model

We focus on operations, forget memory requirements.

Lecture 2

Question

Given an array $A[\mathrm{1..}n]$, find a contiguous subarray $A[i..j]$ that maximizes the sum $A[i]+\cdots +A[j]$

Example

Given $A=[10,-5,4,3,-5,6,-1,1]$, the subarray $A[\mathrm{1..6}]$ is the maximal sum.

Brute force algorithm

BruteForce(A)
opt = 0
for i = 0 to n do
	for j = i to n do 
		sum = 0
		for k = i to j do
			sum = sum + A[k]
		if sum > opt
			opt = sum
return opt

Runtime: $\Theta (n^3)$

We can improve the brute force algorithm (since we are recomputing the same sum many times)

BetterBruteForce(A)
opt = 0
for i = 1 to n do
	sum = 0
	for j = 1 to n do
		sum = sum + A[j]
		if sum > opt
			opt = sum
return opt

Runtime: $\Theta (n^2)$

Divide-and-conquer: solve the problem twice in size $n/2$ (we assume $n$ is a power of $2$).

The optimal subarray

1. Is completely in the left half $A[\mathrm{1..}n/2]$
2. Or is completely in the right half $A[n/2+\mathrm{1..}n]$
3. Or contains both $A[n/2]$ and $A[n/2+1]$

To find the optimal subarray in case $3$, write

$$\begin{array}{r}A[i]+\cdots +A[j]=A[i]+\cdots +A[n/2]+A[n/2+1]+\cdots +A[j]\end{array}$$

More abstractly: $F(i,j)=f(i)+g(j)$ for $i$ in $1,\dots ,n/2$ and $j$ in $n/2+1,\dots ,n$

To maximize $F(i,j)$, maximize $f(i)$ and $g(j)$ independently.

Maximize half-sums

MaximizeLowerHalf(A)
opt = A[n/2]
sum = A[n/2]
for i = n/2 -1, ..., 1 do
	sum = sum + A[i]
	if sum > opt
		opt = sum
return opt

$n/2$ operations $⟹\Theta (n)$

MaximizeUpperHalf(A)
opt = A[n/2 + 1]
sum = A[n/2 + 1]
for i = n/2 + 2, ..., n do
	sum = sum + A[i]
	if sum > opt
		opt = sum
return opt

Same thing as above, just for the right half of the array.

Main algorithm

DivideAndConquer(A[1...n])
if n = 1 return max(A[1], 0)
opt_lo = DivideAndConquer(A[1..n/2])
opt_hi = DivideAndConquer(A[n/2+ 1 .. n])
opt_middle = MaximizeLowerHalf(A) + MaximizeUpperHalf(A)
return max(opt_lo, opt_hi, opt_middle)

Runtime: $T(n)=2T(n/2)+\Theta (n)$ so $T(n)\in \Theta (n\log (n))$

This is the same as MergeSort.

Dynamic Programming

Idea: Solve the problem in subarrays $A[\mathrm{1..}j]$ of sizes $1,\dots ,n$

1. Is either a subarray of $A[\mathrm{1..}n-1]$
2. Or contains $A[n]$

Translation: write $M(j)=\max$ sum for subarrays of $A[\mathrm{1..}j]$. Then

$$\begin{array}{r}M(n)=\max (M(n-1),\bar{M}(n))\end{array}$$

with $\bar{M}(j)=\max$ sum for subarrays of $A[\mathrm{1..}j]$, that include $j$.

Each cell of this array keeps the answer of its cell.

Question

How can we compute $\bar{M}(1),\dots ,\bar{M}(n)$?

Idea: As before, the optimal subarray that contains $A[n]$

1. is of the form $A[i..n-1,n]$, for some $i\le n-1$
2. or is exactly $[A[n]]$

$\bar{M}(1)$ should be simple. Must be $A[1]$.

Translation: $\bar{M}(n)=\max (\bar{M}(n-1)+A[n],A[n])=A[n]+\max (\bar{M}(n-1),0)$

Can eliminate recursive calls, and write as a loop.

M = A[1]
for i = 2, ... n do
	M = A[i] + max(M, 0)

DP(A)
Mbar = A[1]
M = max(Mbar, 0)
for i = 2, ..., n do
	Mbar = A[i] + max(Mbar, 0)
	M = max(M, Mbar) 
return M

Runtime: $\Theta (n)$

Design Idea for MergeSort

Input: Array $A$ of $n$ integers

1. Split $A$ into two subarrays: $A_L$ consists of the first $\lceil \frac{n}{2}\rceil$ elements in $A$ and $A_R$ consists of the last $\lfloor \frac{n}{2}\rfloor$ elements in $A$
2. Recursively run MergeSort on $A_L$ and $A_R$
3. After $A_L$ and $A_R$ have been sorted, use a function Merge to merge them into a single sorted array.

The following is a sloppy recurrence.

$$\begin{array}{r}T(n)=\{\begin{array}{ll}2T(\frac{n}{2})+\Theta (n)& \text{if }n>1\\ \Theta (1)& \text{if }n=1\end{array}\end{array}$$

We can make it simpler.

$$\begin{array}{r}T(n)=\{\begin{array}{ll}2T(\frac{n}{2})+cn& \text{if }n>1\\ d& \text{if }n=1\end{array}\end{array}$$

Exact and sloppy are identical when $n$ is a power of $2$. We solve the sloppy recurrence when $n=2^j$ using the recursion three method.

Tree Method:

• Start with a one-node tree, $N$, which receives the value $T(n)$
• Grow two children of $N$. These children, $N_1$ and $N_2$ receive the value of $T(n/2)$, and the value of $N$ is updated to be $cn$.
• Repeat this process recursively, terminating when a node receives the value $T(1)=d$
• Sum the values on each level of the tree, and then compute the sum of all these sums; the result is $T(n)$.

Note, this is not a proof. If a proof is required, it is necessary to use induction.

The Master Theorem provides a formula for the solution of many recurrence relations typically encountered in the analysis of divide-and-conquer algorithms.

Theorem

Suppose that $a\ge 1$ and $b>1$. Consider the recurrence $T(n)=aT(\frac{n}{b})+\Theta (n^y)$ in sloppy or exact form. Denote $x={\log }_{b}a$. Then

$$\begin{array}{r}T(n)\in \{\begin{array}{ll}\Theta (n^x)& \text{if }y<x\\ \Theta (n^y\log n)& \text{if }y=x\\ \Theta (n^y)& \text{if }y>x\end{array}\end{array}$$

Suppose that $n=b^j,a\ge 1,b\ge 2$ are integers and

$T(n)=aT(\frac{n}{b})+c{n}^y,T(1)d$

Lecture 3

Computing $T(n)$ using the Master Theorem

$d{a}^j+c{n}^y{\sum }_{i=0}^{j-1}{\left(\frac{a}{b^y}\right)}^i$

$n=b^j⟹j={\log }_{b}n$ and $x={\log }_{b}a⟹a=b^x$

Let $r=\frac{a}{b^y}=\frac{b^x}{b^y}=b^{x-y}$

Our total is

$$\begin{array}{r}d{a}^{{\log }_{b}n}+c{n}^y\sum _{i=0}^{j-1}{r}^i=d{n}^{{\log }_{b}a}+c{n}^y\sum _{i=0}^{j-1}{r}^i\end{array}$$

We know that

$a^{{\log }_{b}n}=n^{{\log }_{b}a}$

Proof:

${\log }_{b}a=x⟹a=b^x$

$a^{{\log }_{b}n}=(b^x{)}^{{\log }_{b}n}=b^{x{\log }_{b}n}=b^{{\log }_b{n}^x}=n^x=n^{{\log }_{b}a}$

Case 1: $r=1$ (e.g. $x=y$): Balanced

${\sum }_{i=0}^{j-1}{r}_i={\sum }_{i=0}^{j-1}1=j={\log }_{b}n$

Total: $d{n}^x+c{n}^y{\log }_{b}n\in \Theta (n^y\log n)$

Case 2: $r<1$ (e.g. $x<y)$: Heavy Top

${\sum }_{i=0}^{j-1}{r}^i\in \Theta (1)⟹$ Total: $d{n}^x+c{n}^y\in \Theta (n^y)$

Case 3: $r>1$ (e.g. $x>y$): Heavy Leaves

${\sum }_{i=0}^{j-1}{r}^i=\frac{r^j-1}{r-1}\in \Theta (r^j)$

$r^j=r^{{\log }_{b}n}=n{n}^{{\log }_{b}r}=n^{{\log }_b{b}^{x-y}}=n^{x-y}$

Total: $d{n}^x+c{n}^y(n^{x-y})=d{n}^x+c{n}^x\in \Theta (n^x)$

The exist other methods - the substitution method

To solve a recurrence, do the following:

• Guess the solution (the form of the solution)
• Use induction to prove it

Example

$T(n)=2T(\lfloor \frac{n}{2}\rfloor )+nT(1)=1$

Want to show that $T(n)\in O(n\log n)$

So, we are trying to show that $T(n)\le c\cdot n\log n$ for $n\ge n_0$ where $c>1$, $n_0\ge 1$.

Induction Hypothesis: Assume the statement holds for $k\le \frac{n}{2}$

$$\begin{array}{rl}T(n)& \le 2T\left(\lfloor \frac{n}{2}\rfloor \right)+n\\ & \le 2\left(c\lfloor \frac{n}{2}\rfloor \log \left(\lfloor \frac{n}{2}\rfloor \right)\right)+n\\ & \le 2\left(c\frac{n}{2}\log \left(\frac{n}{2}\right)\right)+n\\ & \le cn\left(\log n-\log 2\right)+n\\ & \le cn\log n-cn+n\\ & \le cn\log n+(1-c)n\le cn\log n\end{array}$$

$1=T(1)\le c\log 1=0$. Not a good base case.

$T(2)=2T(1)+2=4\le c\cdot 2{\log }_{2}2=2c$

$T(3)=2T(1)+3=5\le c\cdot 3\log 3$

Let $n_0=2$ and $c\ge 2$

A general algorithmic paradigm

• Divide: Split a problem into several subproblems
• Conquer: Solve the subproblems (recursively) applying the same algorithm
• Combine: Use subproblem results to derive final result

Question

When do we use Divide and Conquer?

• Original problem is easily decomposable into subproblems
• Combining solutions is not too costly
• Subproblems are not overly unbalanced

Counting Inversions: Given an unsorted array $A[\mathrm{1..}n]$, find the number of inversions in it

Definition

$(i,j)$ is an inversion if $i<j$ and $A[i]>A[j]$

Example

$A=[1,5,2,6,3,8,7,4]$, we get $(2,3),(2,5),(2,8),(4,5),(4,8),(6,7),(6,8),(7,8)$

We show the indices were inversions occur.

Easy algorithm (two nested loops) in $\Theta (n^2)$

Idea:

• $c_{\ell }$ = number of inversions in $A[\mathrm{1..}n/2]$
• $c_r$ = number of inversions in $A[n/2+\mathrm{1..}n]$
• $c_t$ = number of transverse inversions with $i\le n/2$ and $j>n/2$
• Return $c_{\ell }+c_r+c_t$

From previous array, $A$.

• $c_{\ell }=1(2,3)$
• $c_r=3(6,7),(6,8),(7,8)$
• $c_t=4(2,5),(2,8),(4,5),(4,8)$

$c_{\ell }$ and $c_r$ are done recursively.

Question

What about $c_t$?

Goal: How many pairs $(i,j)$ with $i\le \frac{n}{2},j>\frac{n}{2},A[i]>A[j]$?

This number does not change if both sides are sorted.

Example: Starting from $[1,5,2,6,3,8,7,4]$, we get $[1,2,5,6,3,4,7,8]$

$c_t=$ Number of $i$‘s greater than $3$ + number of $i$‘s greater than $4$ + number of $i$‘s greater than $7$ + number of $i$‘s greater than $8$.

Option 1:

Take each $i\le \frac{n}{2}$ and binary-search its position in the right-hand side

• This is $O(\log (n))$ per $i$, so total $O(n\log (n))$
• Plus another $O(n\log (n))$ for sorting left and right
• Recurrence: $T(n)\le 2T(n/2)+O(n\log (n))$
• Gives $T(n)=O(n{\log }^2(n))$

Sketchy Proof:

$$\begin{array}{rl}T(n)& \le 2T(n/2)+n\log (n)\le 2\left(2T\left(n/4\right)+\frac{n}{2}\log (n/2)\right)\\ & \le 4T(n/4)+n\log (n/2)+n\log (n)\\ & \le 8T(n/8)+n\log (n/4)+n\log (n/2)+n\log (n)\\ & \le \cdots \le n(\log (n)+\log (n/2)+\cdots +\log (2))\\ & \le n\cdot lo{g}^2(n)\end{array}$$

Lecture 4

// Copy A into a new array S; c=0
i = 1; j = n/2 + 1;
for (k = 1; k <= n; k++) {
	if (i > n/2) A[k] = S[j++]
	else if (j > n) A[k] = S[i++]; c = c + n/2
	else if (S[i] < S[j]) A[k] = S[i++]; c = c + j - (n/2 + 1)
	else A[k] = S[j++]
}

Multiplying polynomials.

Goal: Given $F=f_0+\cdots +f_{n-1}{x}^{n-1}$ and $G=g_0+\cdots +g_{n-1}{x}^{n-1}$, compute

$$\begin{array}{r}H=FG=f_{0}g+0+(f_0{g}_1+f_1{g}_0)x+\cdots +f_{n-1}{g}_{n-1}{x}^{2n-2}\end{array}$$

for i = 0, ..., n-1 do
	for j = 0, ..., n-2 do
		h_{i+j} = h_{i+j} + f_{i}g_{j}

This is slow. How can we break up a polynomial into two.

$17+3x+666x^2+4x^3$ can be turned into $(17+3x)+(666+4x)x^2$.

Example

$F=17+742x+21x^2+61x^3+49x^4+6x^5+1728x^6+2x^6$

$n=8,n-1=7,n/2=4$

$=\underset{F_0}{\underbrace{(17+742x+21x^2+61x^3)}}+\underset{F_1}{\underbrace{(49+6x+1728x^2+2x^3)}}{x}^4$

Divide-and-conquer idea

$F=F_0+F_1{x}^{n/2}$, $G=G_0+G_1{x}^{n/2}$. Then

$$\begin{array}{r}H=F_0{G}_0+(F_0{G}_1+F_1{G}_0)x^{n/2}+F_1{G}_1{x}^n\end{array}$$

Analysis:

• 4 recursive calls in size $n/2$
• $\Theta (n)$: additions to compute $F_0{G}_1+F_1{G}_0$ and etc.

Recurrence: $T(n)=4T(n/2)+\Theta (n)$

• $a=,b=2,y=1$ so $T(n)=\Theta (n^2)$

Not better than naive algorithm.

Karatsuba’s algorithm

Idea: Use the identity

$(F_0+F_1{x}^{n/2})(G_0+G_1{x}^{n/2})=F_0{G}_0+((F_0+F_1)(G_0+G_1)-F_0{G}_0-F_1{G}_1)x^{n/2}+F_1{G}_1{x}^n$ Analysis:

• 3 recursive calls in size $n/2$
• $\Theta (n)$ additions to compute $F_0+F_1$ and $G_0+G_1$
• Multiplications by $x^{n/2}$ and $x^n$ are free
• $\Theta (n)$ additions and subtractions to combine the results

Recurrence: $T(n)=3T(n/2)+\Theta (n)$

• $a=3,b=2,c=1$ so $T(n)=\Theta (n^{{\log }_2(3)})$

Remark: Key idea $=$ a formula for degree-1 polynomials that does 3 multiplications

Toom-Cook:

• $T(n)=\Theta (n^{{\log }_k(2k-1)})$

FFT:

• $T(n)=2T(n/2)+\Theta (n)$

Multiplying Matrices:

Goal: Given $A=[a_{i,j}{]}_{1\le i,j\le n}$ and $B=[b_{j,k}{]}_{1\le j,k\le n}$ compute $C=AB$

Input and output size $\Theta (n^2)$, easy algorithm in $\Theta (n^3)$

Divide and Conquer: Divide the matrices into 4. More multiplications, but the size is smaller.

$$\left(\begin{array}{cc}{A}_{1,1}& A_{1,2}\\ A_{2,1}& A_{2,2}\end{array}\right)$$ $$\left(\begin{array}{cc}{B}_{1,1}& B_{1,2}\\ B_{2,1}& B_{2,2}\end{array}\right)$$ $$\left(\begin{array}{cc}{A}_{1,1}{B}_{1,1}+A_{1,2}{B}_{2,1}& A_{1,1}{B}_{1,2}+A_{1,2}{B}_{2,2}\\ A_{2,1}{B}_{1,1}+A_{2,2}{B}_{2,1}& A_{2,1}{B}_{1,2}+A_{2,2}{B}_{2,2}\end{array}\right)$$

Naively: 8 recursive calls in size $n/2+\Theta (n^2)$ additions $⟹T(n)=\Theta (n^3)$

This didn’t get better.

Strassen’s Algorithm: 7 multiplications and we can construct the entries of the matrix.

Analysis: 7 recursive calls in size $n/2+\Theta (n^2)$ additions $⟹T(n)=\Theta (n^{{\log }_2(7)})$. The constant hiding is large. Only makes sense to use on galactic algorithms.

Generalization: An algorithm that does $k$ multiplications for matrices of size $\ell$ gives $T(n)\in \Theta (n^{{\log }_{\ell }(k)})$

Closest Pairs

Goal: Given $n$ points ($x_i,y_i$) in the plane, find a pair $(i,j)$ that minimizes the distance

$$\begin{array}{r}{d}_{i,j}=\sqrt{(x_i-x_j{)}^2+(y_i-y_j{)}^2}\end{array}$$

Equivalent to minimize

$$\begin{array}{r}{d}_{i,j}^2=(x_i-x_j{)}^2+(y_i-y_j{)}^2\end{array}$$

All $x_i$‘s are pairwise distinct.

Idea: Separate the points into two halves $L,R$ at the median $x-$value (can use quick select to find this in $O(n)$)

• $L=$ all $n/2$ points with $x\le x_{\text{median}}$
• $R=$ all $n/2$ points with $x>x_{\text{median}}$
• The closest pair is either between points in $L$, or between points in $R$, or transverse.

Set $\delta =\min ({\delta }_L,{\delta }_R)$

We only need to consider transverse pairs $(P,Q)$ with $dist(P,R)\le \delta$ and $dist(Q,L)\le \delta$.

Lecture 5

For the transverse case, we only need to search from $x-\delta$ to $x+\delta$. Assume the points are ordered by the $y-$coordinate and only find distance upwards (don’t look downwards).

For any $P=(x_P,y_P)$, enough to look at points with $y_P\le y<y_P+\delta$. It is enough to check distances $d(P,Q)$ for $Q$ in the rectangle.

Claim

There are at most 8 points from our initial set (including $P$) in the rectangle.

Initialization: Sort the points, with respect to $x$

Cost: $O(n\log (n))$, before recursive calls.

Note: Merge based on the $y-$coordinate so that the result is sorted in $y-$coordinate.

Then: Recursion

• Finding $x-$median is easy: $O(n)$
• For the next recursive calls, split the sorted lists: $O(n)$
• Remove the points at distance $\ge \delta$ from the $x-$splitting line: $O(n)$
• Inspect all remaining points in increasing $y-$order. For each, compute the distance to the next $8$ points and keep the min: $O(n)$

We are splitting by $x$ value, and then merging by $y$ value.

Runtime: $T(n)=2T(n/2)+\Theta (n)$ so $T(n)\in \Theta (n\log (n))$

Median of medians

Median: Given $A[0\dots n-1]$, find the entry that would be at index $\lfloor n/2\rfloor$ if $A$ was sorted

Selection: Given $A[0\dots n-1]$ and $k$ in $\{0,\dots ,n-1\}$, find the entry that would be at index $k$ if $A$ was sorted.

Known results: Sorting $A$ in $O(n\log (n))$, or a simple randomized algorithm in expected time $O(n)$

Question

How do we find a good pivot for quick select such that both $i$ and $n-i-1$ are not too large.

Sketch of the algorithm:

• Divide $A$ into $n/5$ groups, $G_1,\dots ,G_{n/5}$ of size $5$.
• Find the medians $m_1,\dots ,m_{n/5}$ of each group: $O(n)$
• Pivot $p$ is the median of $[m_1,\dots ,m_{n/5}]$: $T(n/5)$

With this choice of $p$, the indices $i$ and $n-i-1$ are at most $7n/10$.

Proof:

• Half of the $m_i$‘s are greater than $p$ ($n/10$)
• For each $m_i$, there are 3 elements in $G_i$ greater than or equal to $m_i$
• So at least $3n/10$ elements greater than $p$
• So at most $7n/10$ elements less than $p$
• So $i$ is at most $7n/10$. Same thing for $n-i-1$

The runtime $T(n)$ satisfies

$$\begin{array}{r}T(n)\le T(n/5)+T(7n/10)+O(n)\end{array}$$

This gives $T(n)\in O(n)$

$$\begin{array}{r}T(n)\le \{\begin{array}{ll}O(1)& n<120\\ T(n/5)+T(7n/10+6)+O(n)& n\ge 120\end{array}\end{array}$$

We show that $T(n)\le c\cdot n$ for a large enough $c$ and all $n>0$

We know that if $c$ is large enough then $T(n)\le c\cdot n$ for all $n<120$

Also choose a constant $a$ to write $O(n)$ as $a\cdot n$

Assume the statement $(T(m)\le c\cdot m)$ is correct for all $0<m<n$. We have

$$\begin{array}{rl}T(n)& \le c\left(\frac{n}{5}\right)+c\left(\frac{7n}{10}+6\right)+an\le c\frac{n}{5}+\frac{7cn}{10}+6c+an\\ & \le 9\frac{cn}{10}+6c+an\le cn+\underset{\ast }{\underbrace{(-c\frac{n}{10}+6c+an)}}\end{array}$$

Show that $\ast$ is $=0$

We will have

$T(n)\le cn$, if

$$\begin{array}{rl}& -c\frac{n}{10}+6c+an\le 0\\ & ⟺c\left(6-\frac{n}{10}\right)+an\le 0\\ & ⟺c\left(6-\frac{n}{10}\right)\le -an⟺c\left(\frac{n}{10}-6\right)\ge an\\ & ⟺c\ge 10a\left(\frac{n}{n-60}\right)\end{array}$$

Now if $n>120$, then we have $\frac{n}{n-60}<2$ and we can choose $c\ge 20a\ge 10a(\frac{n}{n-60})$

Note: $n\ge 120⟹n-120\ge 0⟹2n-120\ge n⟹2(n-60)\ge n⟹2\ge \frac{n}{n-60}$

Lecture 6

• Basics on undirected graphs
• Undirected BFS and applications (shortest paths, bipartite graphs, connected components)
• Undirected DFS and applications
• Basics on directed algorithms
• Directed DFS and applications

Definition

Undirected Graphs: A graph $G$ is pair $(V,E)$:

• $V$ is a finite set, whose elements are called vertices
• $E$ is a finite set, whose elements are unordered pairs of distinct vertices, and are called edges

Convention: $n$ is the number of vertices, $m$ is the number of edges.

Data structures:

• Adjacency list: An array $A[\mathrm{1..}n]$ s.t. $A[v]$ is the linked list of all edges connected to $v$. $2m$ list cells (an edge is in 2 lists), total size $\Theta (n+m)$, but testing if an edge exists is not $O(1)$
• Adjacency matrix: A $(0,1)$ matrix $M$ of size $n\times n$, with $M[v,w]=1⟺\{v,w\}$ is an edge. Size is $\Theta (n^2)$, but testing if an edge exists is $O(1)$

Adjacency list of above:

• $1\to 2\to 5$
• $2\to 1\to 5\to 4\to 3$
• $3\to 2\to 4$
• $4\to 2\to 3\to 5$
• $5\to 1\to 2\to 4$

Array with corresponding linked list of edges.

Adjacency Matrix

$$\begin{array}{r}\left[\begin{array}{ccccc}0& 1& 0& 0& 1\\ 1& 0& 1& 1& 1\\ 0& 1& 0& 1& 0\\ 0& 1& 1& 0& 1\\ 1& 1& 0& 1& 0\end{array}\right]\end{array}$$

Definition

Path: A sequence $v_1,\dots ,v_k$ of vertices, with $\{v_i,v_{i+1}\}$ in $E$ for all $i$. $k=1$ is okay

Definition

Connected graph: $G=(V,E)$ such that for all $v,w$ in $V$, there is a path $v⇝w$

Definition

Cycle: A path $v_1,\dots ,v_k,v_1$, with $k\ge 3$ and $v_i$‘s pairwise distinct

Definition

Tree: A connected graph without any cycle

Definition

Rooted tree: A tree with a special vertex called root

Definition

Subgraph of $G=(V,E)$: A graph $G^{\prime }=(V^{\prime },E^{\prime })$, where

• $V^{\prime }\subseteq V$
• $E^{\prime }\subseteq E$, with all edges $E^{\prime }$ joining vertices from $V^{\prime }$

Definition

Connected component of $G=(V,E)$

• A connected subgraph of $G$
• That is not contained in a larger connected subgraph of $G$.

Let $G_i=(V_i,E_i),i=1,\dots ,s$ be the connected components of $G=(V,E)$.

• The $V_i$‘s are a partition of $V$, with ${\Sigma }_i{n}_i=n$. $n_i=|V_i|$
• The $E_i$‘s are a partition of $E$, with ${\Sigma }_i{m}_i=m.m_i=|E_i|$

Question

Assume we are looking for a person in a social network and we don’t want to use the usual search. What is a possible strategy?

BFS(G, s): 
G: a graph with n vertices, given be adjacency list
s: a vertex from G

let Q be an empty queue
let visited be an array of size n, with all entries set to false
enqueue(s, Q) // add s to Q
visited[s] = true
while Q not empty do: // s is inside Q
	v = dequeue(Q)
	for all w neighbours of v do:
		if visited[w] is false:
			enqueue(w, Q)
			visited[w] = true

A vertex is enqueued at most once. Nodes are dequeued at most once. Each adjacency list is read at most once.

For all $v$, write $d_v=$ number of neighbours of $v=$ length of $A[v]=$ degree of $v$.

Then total cost at step 7 is

$$\begin{array}{r}O\left(\sum _v{d}_v\right)=O(m)\end{array}$$

The adjacency array $A$ has 2$m$ cells (handshaking lemma from MATH239).

Total: $O(n+m)$

Question

For all vertices $v$, there is a path $s⇝v$ in $G$ if and only if $visited[v]$ is true at the end

Claim (first)

For all vertices $v$, if $visited[v]$ is true at the end, there is a path $s⇝v$ in $G$.

Proof: Let $s=v_0,\dots ,v_K$ be the vertices for which $visited$ is set to true, in this order. We prove: for all $i$, there is a path $s⇝v_i$, by induction.

This is OK for $i=0$.

Suppose it is true for $v_0,\dots ,v_{i-1}$.

Since $visited[v_i]$ is set to true, we are examining the neighbours of a certain $v_j,j<i$.

By assumption, there is a path $s⇝v_j$ because $\{v_j,v_i\}$ is in $E$, there is a path $s⇝v_i$

Claim (second)

For all vertices $v$, if there is a path $s⇝v$ in $G$, $visited[v]$ is true at the end.

Proof: Let $v_0=s,\dots ,v_k=v$ be a path $s⇝v$. We prove $visited[v_i]$ is true for all $i$, by induction.

$visited[v_0]$ is true.

If $visited[v_i]$ is true, we will examine all neighbours $u$ of $v_i$ so at the end of Step 7, all $visited[u]$ will be true, for $u$ neighbour of $v_i$ in particular, $visited[v_{i+1}]$ will be true.

Lemma: For all vertices $v$, there is a path $s⇝v$ in $G$ if and only if $visited[v]$ is true at the end.

Applications:

• Testing if there is a path $s⇝v$
• Testing if $G$ is connected in $O(n+m)$

For a connected graph, $m\ge n-1$. This can help us simplify our runtime.

BFS(G, s)
Q is an empty queue
parent is an array of size n, all entries set to NIL
level is an array of size n, with all entries to infinity
enqueue(s, Q)
parent[s] = s
level[s] = 0
while Q not empty do:
	v = dequeue(Q)
	for all w neighbours of v do:
		if parent[w] is NIL:
			enqueue(w, Q)
			parent[w] = v
			level[w] = level[v] + 1

Since $u$ was added first, we dequeue $u$ first and update its neighbours. Then once that happens we dequeue $w$.

Definition

The BFS tree $T$ is the subgraph made of:

• all $w$ such that $parent[w]\ne$ NIL
• all edges $\{w,parent[w]\}$, for $w$ as above (except $w=s$)

Claim

The BFS tree $T$ is a tree

Proof: By induction on the vertices for which $parent[v]$ is not NIL.

When we set $parent[s]\leftarrow s$, only one vertex, no edge.

Suppose true before we set $parent[w]\leftarrow v$. $v$ was in $T$ before, $w$ was not, so we add one vertex $w$ and one edge $\{v,w\}$ to $T$ so $T$ remains a tree

Remark: We make it a rooted tree by choosing $s$ as a root.

Lecture 7

Shortest path from the BFS tree.

Sub-claim 1

The levels in the queue are non-decreasing

Sub-claim 2

For all vertices $u,v$, if there is an edge $\{u,v\}$, then $level[v]\le level[u]+1$

Proof:

If we dequeue $v$ before $u$, $level[v]\le level[u]$

If we dequeue $u$ before $v$, the parent of $v$ is either $u$, or was dequeued before $u$. In any case, $level[parent[v]]\le level[u]$, but $level[parent[v]]=level[v]-1$, so OK.

Claim

For all $v$ in $G$:

• There is a path $s⇝v$ in $G⟺$ there is a path $s⇝v$ in $T$
• If so, the path in $T$ is a shortest path and $level[v]=dist(s,v)$

Proof of second item:

$dist(s,v)\le level[v]$ (follow the path on $T$). $dist$ is the shortest path.

For all $i$, for all $v$, if there is a path $s⇝v$ of length $i$, then $level[v]\le i$

• True for $i=0$
• Suppose true for $i-1$ and take $v$, a path $s⇝v$ of length $i$ and let $u$ be the vertex before $v$. Induction assumption: $level[u]\le i-1$, so $level[v]\le i$

So $level[v]\le dist(s,v)$

Since $dist(s,v)\le level[v]\wedge level[v]\le dist(s,v)⟹level[v]=dist(s,v)$

Definition

A graph $G=(V,E)$ is bipartite if there is a partition $V=V_1\cup V_2$ such that all edges in $V_1$ and one end in $V_2$

Claim

Suppose $G$ connected, run BFS from any $s$, and set

• $V_1=$ vertices with odd level
• $V_2=$ vertices with even level

Then $G$ is bipartite if and only if all edges have one end in $V_1$ and one end in $V_2$ (testable in $O(m)$)

Proof: $⟸$ obvious

For $⟹$, let $W_1,W_2$ be a bipartition. Because paths alternate between $W_1,$W_2$:

• $V_1$ ($=$ vertices with odd level) is included in $W_1$
• $V_2$ ($=$ vertices with even level) is included in $W_2$

So $V_1=W_1$ and $V_2=W_2$

Computing the connected components

Idea: add an outer loop that runs BFS on successive vertices

Each pass of BFS $O(n_i+m_i)$, if $G_i(V_i,E_i)$ is the $i$th connected component.

Total $O(n+m)$

Going depth-first

• Travel as deep as possible, as long as you can
• When you can’t go further, backtrack

DFS implementations are based on stacks, either implicitly (recursion) or explicitly (as with queues for BFS).

DFS(G):
// G: a graph with n vertices, given by adjacency lists
// Let visited be an array of size n, with all entries set to false
for all v in G
	if visited[v] is false
		explore(v)
 
explore(v):
	visited[v] = true
	for all w neighbour of v do
		if visited[w] = false
			explore (w)
 

Claim

”White path lemma” - When we start exploring a vertex $v$, any $w$ that can be connected to $v$ by an unvisited path will be visited during $explore(v)$

Proof: Let $v_0=v,\dots ,v_k=w$ be a path $v⇝w$, with $v_1,\dots ,v_k$ not visited. We prove all $v_i$‘s are visited before $explore(v) is finished.

True for $i=0$. Suppose true for $i<k$. When we visit $v_i$, $explore(v)$ is not finished, and $v_{i+1}$ is one of its neighbours.

• If $visited[v_{i+1}]$ is true when we reach step 3 (OK, means we visited it)
• Else: We will visit it just now (OK, will be done before $explore(v)$ is finished)

Claim

If $w$ is visited during $explore(v)$, there is a path $v⇝w$

Proof: Same as BFS

Previous properties: After we call explore at $v_1,\dots ,v_k$ in DFS, we have visited exactly the connected components containing $v_1,\dots ,v_k$

Shortest paths: No

Runtime: Still $O(n+m)$

Previous observation:

• $DFS(G)$ gives a partition of $G$ into vertex-disjoint rooted trees $T_1,\dots ,T_k$ (DFS forest)

Definition

Suppose the DFS forests is $T_1,\dots ,T_k$ and let $u,v$ be two vertices.

• $u$ is an ancestor of $v$ if they are on the same $T_i$ and $u$ is on the path root $⇝v$
• equivalent: $v$ is a descendant of $u$

Claim

All edges in $G$ connect a vertex to one of its descendants or ancestors (statement does not hold for BFS)

Proof: Let $\{v,w\}$ be an edge, and suppose we visit $v$ first.

Then we visit $v,(v,w)$ is an unvisited path between $v$ and $w$, so $w$ will become a descendant of $v$ (white path lemma)

Definition

A back edge is an edge in $G$ connecting an ancestor to a descendant, which is not a tree edge.

Observation: All edges are either tree edges or back edges.

Set a variable $t$ to 1 initially, create two arrays start and finish, and change explore:

explore(v)
visited[v] = true
start[v] = t
t++
for all w neighbour of v do
	if visited[w] = false
		explore(w)
finish[v] = t
t++

Intervals are either completely inside each other or completely disjoint.

Lecture 8

Observation:

if $start[u]<start[v]$, then either $finish[u]<start[v]$ or $finish[v]<finish[u]$. Proof:

Let $start[u]<start[v]$. If $finish[u]<finish[v]$, we are done.

Assume $finish[u]>start[v]$ then we have:

Cut vertices

Definition

For $G$ connected, a vertex in $G$ is a cut vertex if removing $v$ (and all edges that contain it) makes $G$ disconnected.

Also called articulation points.

Find the cut vertices ($G$ connected)

Setup: We start from a rooted DFS tree $T$, knowing parent and level.

Warm-up: The root $s$ is a cut vertex if and only if it has more than one child

Proof:

If $s$ has one child, removing $s$ leaves $T$ connected. So $s$ is not a cut vertex.

Suppose $s$ has subtrees $S_1,\dots ,S_k,k>1$.

Key property: No edge connecting $S_i$ to $S_j$ for $i\ne j$. So removing $s$ creates $k$ connected components.

Definition

For a vertex $v$, let

• $a(v)=\min \{level[v],\{v,w\}\text{ edge}\}$
• $m(v)=\min \{a(w),w\text{ descendent of }v\}$

$a(v)$ is the lowest level of an edge to $v$.

$m(v)$ is the lowest level of any edge from the subtree rooted at $v$

For any $v$ (except the root), $v$ is a cut vertex if and only if it has a child $w$ with $m(w)\ge level[v]$. Intuitively: We can never go above $v$ from any child of $v$.

Proof:

Take a child $w$ of $v$, let $T_w$ be the subtree at $w$. Let also $T_v$ be the subtree at $v$.

If $m(w)<level[v]$, then there is an edge from $T_w$ to a vertex above $v$. After removing $v$, $T_w$ remains connected to the root. Number of connected components remains the same.

If $m(w)\ge level[v]$, then all edges originating from $T_w$ end in $T_v$.

Proof: any edge originating from a vertex $x$ in $T_w$ ends at a level at least $level[v]$, and connects $x$ to one of its ancestors or descendants (key property).

If $v$ has children $w_1,\dots ,w_k$, then $m(v)=\min \{a(v),m(w_1),\dots ,m(w_k)\}$

Conclusion:

• Computing $a(v)$ is $O(d_v)$ where $d_v=$ degree of $v$
• Knowing all $m(w_1),\dots ,m(w_k)$, we get $m(v)$ in $O(d_v)$
• So all values $m(v)$ can be computed in $O(m)$ (remember $O(n+m)=O(m)$ when $G$ connected
• Testing the cut-vertex condition at $v$ is $O(d_v)$
• Testing all $v$ is $O(m)$

Directed Graphs

Definition

$G=(V,E)$ as in the the undirected case, with the difference that edges are (directed) pairs $(v,w)$

• edges also called arcs
• $v$ is the source node, $w$ is the target A path is a sequence $v_1,\dots ,v_k$ of vertices, with $(v_1,v_{i+1})$ in $E$ for all $i$. $k=1$ is OK. A cycle is a path $v_1,\dots ,v_k,v_1,k\ge 2$ A directed acyclic graph (DAG) is a directed graph with no cycle.

Definition

The in-degree of $v$ is the number of edges of the form $(u,v)$

Info

The out-degree of $v$ is the number of edges of the form $(v,w)$

Data structures

• Adjacency lists
• Adjacency matrix (not symmetric anymore)

The DFS and BFS algorithms work without any change. We will focus on DFS.

Still true:

• We obtain a partition of $V$ into vertex-disjoint tees $T_1,\dots ,T_k$
• When we start exploring a vertex $v$, any $w$ with an unvisited path $v⇝w$ becomes a descendant of $v$ (white path lemma)
• Properties of start and finish times

But there can exist edges connecting the trees $T_i$.

Suppose we have a DFA forest. Edges of $G$ are one of the following:

• Tree edges
• Back edges: from descendant to ancestor
• Forward edges: from ancestor to descendant (but not tree edge)
• Cross edges: all others

explore(v):
visited[v] = true
start[v] = t, t++
for all w neighbour of v do
	if visited[w] = false
		explore(w)
finish[v] = t, t++

For a given edge $(v,w)$ we have four cases for start and finish times while we explore $v$:

0. $v$ starts and finishes, and then $w$ starts and finishes. This is not possible when we explore $v,w$ is unvisited and by white path lemma $w$ will be visited before the exploration of $v$ is over.
1. If we visit $w$ while we are checking neighbours of $v$ and this happens directly from $v$, then $v$ becomes the parent of $w$, and $(v,w)$ is a tree edge. Otherwise we have visited $w$ through another neighbour and this means that $w$ is a descendant of $v$. So, $(v,w)$ is a forward edge.
2. (same drawing as above but different $v$ and $w$ are swapped) $w$ was visited but not finished. This implies that we are visiting $v$, through a neighbour of $w$ and this means that $v$ becomes a descendant of $w$. Hence $(v,w)$ is a back edge.
3. In this case $w$ was visited and finished before we start $v$. In this case $v$ or $w$ are not descendants of each other and belong to two different subtrees. Hence $(v,w)$ is a cross edge.

So overall, if $w$ was visited:

• If $w$ not finished, $(v,w)$ back edge
• else if $start[v]<start[w]<finish[w]$, $(v,w)$ forward edge
• else $start[w]<finish[w]<start[v]$, $(v,w)$ cross edge

Lecture 9

Claim

$G$ has a cycle if and only if there is a back edge in the DFS forest

First direction. If $G$ has a back edge, then there $G$ has a cycle.

Suppose there is a back edge $(v,w)$. Then $v$ is a descendant of $w$, so there is a path $w⇝v$, and a cycle $w⇝v\to w$

Other direction: If $G$ has a cycle, then it has a back edge.

Suppose there is a cycle $v_1,\dots ,v_{k-1},v_k=v_1$. WLOG, we find $v_1$ first in the DFS.

Starting from $v_1$, we will reach $v_{k-1}$ (white path lemma). We check the edge $(v_{k-1},v_1)$, and $v_1$ is not finished. So back edge.

Acyclicity test in $O(n+m)$.

Topological ordering

Definition

Suppose $G=(V,E)$ is a DAG. A topological order is an ordering $<$ of $V$ such that for any edge $(v,w)$, we have $v<w$.

A DAG will always have an in-degree 0 node.

The start time from a DFS forest is not helpful. The finish times are helpful, but we have to reverse their order.

Claim

Suppose that $V$ is ordered using the reverse of the finishing order: $v<w⟺finish[w]<finish[v]$. This is a topological order.

Proof: Have to prove: For any edge $(v,w),finish[w]<finish[v]$.

If we discover $v$ before $w$, $w$ will become a descendant of $v$ (white path lemma), and we finish exploring it before we finish $v$.

If we discover $w$ before $v$, because there is no path $w⇝v$ ($G$ is a DAG), we will finish $w$ before we start $v$.

Consequence: Topological order in $O(n+m)$.

Definition

A directed graph $G$ is strongly connected if for all $v,w$ in $G$, there is a path $v⇝w$ (and thus a path $w⇝v$).

Observation: $G$ is strongly connected $⟺$ there exists $s$ such that for all $w$, there are paths $s⇝w$ and $w⇝s$.

Proof:

• $⟹$ is obvious
• For $⟸$, take vertices $v,w$. We have paths $v⇝s$ and $s⇝w$, so $v⇝w$. Same thing with $w⇝v$.

Testing strong connectivity:

• We call explore twice, starting from a same vertex $x$.
• Edges reversed the second time.

Correctness:

• First run tells whether for all $v$, there is a path $s⇝v$
• Second one tells whether for all $v$, there is a path $s⇝v$ in the reverse graph (which is a path $v⇝s$ in $G$).

Consequence: Test in $O(n+m)$

Definition

A strongly connected component of $G$ is

• A subgraph of $G$
• Which is strongly connected
• But not contained in a larger connected subgraph of $G$.

A directed graph $G$ can be seen as a DAG of disjoint strongly connected components.

Kosaraju’s algorithm for strongly connected components

Definition

For a directed graph $G=(V,E)$, the reverse (or transverse) graph $G^T=(V,E^T)$ is the graph with same vertices, and reversed edges.

SCC(G)
run DFS on G and record finish times
run DFS on G^T, with vertices ordered in decreasing finish time
return the trees in the DFS forest of G^T

Complexity: $O(n+m)$.

We want to prove: $v$ and $w$ belong to the same SCC of $G⟺v$ and $w$ belong to the same tree in DFS forest of $G^T$.

Proof of ($⟹$) (Order of vertices does not matter)

Assume $C$ is the SCC containing $v$ and $w$.

When we run DFS on $G^T$, there is a first node of $C$ which we visit. Call it $s$.

All vertices on this path are in $C$.

Otherwise we could enlarge $C$. This is a white path from $s$ to $v$. So, by white path lemma, $v$ becomes a descendant of $s$. So, $v$ and $s$ belong to the same tree in DFS forest of $G^T$. With a similar argument for $w$, we get $v,s,w$ belong to the same tree.

Proof of ( $⟸$ )

Show that for eery vertex $t\in T$ (including $v$ and $w$), $s$ and $t$ are in the same connected component of $G$.

Since there is a path from $s$ to $t$ in $T$ (which is in $G^T$), there exists a path from $t⇝s$ in $G$.

Now it is enough to show that $\forall t\in T,t$ is a descendant of $s$ in the DFS forest of $G$. Which means that there is a path from $s$ to $t$.

Inductive argument: Assume the statement is true for $t\in T$ and show that it is true for children of $t$.

Let $u$ be a child of $t$.

• $t$ is a descendant of $s$, so, ($t$ starts after $s$ starts and $t$ finishes before $s$ finishes)
• We visited $s$ before $u$ here and based on our ordering in the first run of DFS we had $finish[u]<finish[s]$

Two cases:

1. (Good) We start $u$ after we start $s$, and we finish $u$ before we finish $s$.
2. (Bad) The finish time of $u$ is before the start time of $s$. $t$ starts after $s$ starts and $t$ finishes before $s$ finishes.

Bad case is not possible:

$(t,u)\in T\in G^T$, so $(u,t)\in G$. By the white path lemma we visit $t$ before the exploration of $u$ is over (since $u⇝t$ is a white path). Hence we have ($t$ starts after $u$ starts and $t$ finishes before $u$ ends. $s$ starts after $u$ ends. $t$ starts after $s$ starts and $t$ finishes before $s$ ends).

Lecture 10

$G=(V,E)$ a directed graph with a weight function: $w:E\to \mathbb{R}$

The weight of path $P=⟨v_0,\dots ,v_k⟩$ is: $w(P)={\sum }_{i=1}^{k}w(v_{i-1},v_i)$

Question

Do shortest path exists in any directed weighted graph?

No, we have negative-weight cycles, can keep looping.

Assuming $G$ has no negative-weight cycles, then there does exist a shortest path.

The shortest path weight from $u$ to $v$:

$$\begin{array}{r}\delta (u,v)=\{\begin{array}{ll}\min \{w(P):u\stackrel{P}{\overbrace{⇝}}v\}& \text{if there exists a path from }u\text{ to }v\\ \infty & \text{otherwise}\end{array}\end{array}$$

Single-Source Shortest Path Problem

Input: $G=(V,E),w:E\to \mathbb{R}$ and a source $s\in V$

Output: A shortest path from $s$ to each $v\in V$

True/False: If $⟨v_0,v_1,\dots ,v_k⟩$ is a shortest path from $v_0$ to $v_k$, then $⟨v_0,v_1,\dots ,v_i⟩$ is a shortest path from $v_0$ to $v_i$ for any $0\le i\le k$.

This is true.

Dijkstra’s algorithm: Explanation.

Dijkstra’s algorithm is a greedy algorithm.

Input: A weighted directed graph with non-negative wedge weights.

For all vertices, maintain quantities:

• $d[v]$: a shortest-path estimate from $s$ to $v$
• $\pi [v]$: predecessor in the path (a vertex or NIL)

Initialize $C=\varnothing$, repeat the following until $C=V$:

• Add $u\in V-C$ with smallest $d$-value to $C$
• Update $d$-values of vertices with $v$ with $(u,v)\in E$:
  • Relaxation: $d[v]\leftarrow \min \{d[v],d[u]+w(u,v)\}$
• Update $\pi [v]$ if $d[v]$ is changed

$$\begin{array}{rl}\delta (s,v)& \le \delta (s,u)+w(u,v)\\ d[v]& \le d[u]+w(u,v)\end{array}$$

Question

Which Abstract Data Type (ADT) should we use for vertices?

We will use a priority queue.

Cost of operations of a binary min-heap (of size $n$):

• Insert: $O(\log n)$
• Extract-Min: $O(\log n)$
• Update-key: $O(\log n)$

Dijkstra’s Algorithm: Pseudocode

Dijkstra(G, w, s)
for each vertex v \in V[G]
	d[v] = infty
	pi[v] = NIL
d[s] = 0
C = \emptyset
Q = V[G]
while Q != \emptyset:
	u = Extract-Min(Q)
	C = C union {u}
	for each vertex v \in Adj[u]
		if d[v] > d[u] + w(u,v)
			d[v] = d[u] + w(u,v)
			pi[v] = u

Complexity Analysis:

Entirely array implementation

1. 1-5: $O(|V|)$

2. 6: $O(|V|)$

3. 7: $O(|V|)$ iterations

4. 8-9: $O(|V{|}^2)$

5. 10: $O(|E|)$ iterations

6. 11-13: $O(|E|)$

7. Total: $O(|V{|}^2)$

8. 1-5: Array Imp: $O(|V|)$. Heap Imp: $O(|V|)$

9. 6: Array Imp: $O(|V|)$. Heap Imp: $O(|V|)$

10. 7: Array Imp: $O(|V|)$ iterations. Heap Imp: $O(|V|)$ iterations

11. 8-9: Array Imp: $O(|V{|}^2)$. Heap Imp: $O(|V|\log |V|)$

12. 10: Array Imp: $O(|E|)$ iterations. Heap Imp: $O(|E|)$ iterations

13. 11-13: Array Imp: $O(|E|)$. Heap Imp: $O(|E|\log |V|)$

14. Total: Array Imp: $O(|V{|}^2)$. Heap Imp: $O((|V|+|E|)\log |V|)$

Performance depends on density/sparsity of graph.

Proof of Correctness:

Claim

For each vertex $v\in V$, we have $d[v]=\delta (s,v)$ at the time when $v$ is added to set $C$. To prove the claim, we follow these steps.

1. Proof by contradiction: Assume the claim is not correct and $u\in V$ is the first vertex for which $d[u]\ne \delta (s,u)$ when it is added to $C$
2. Time $t$: Beginning of the iteration in which $u$ is added to $C$.
3. Use a shortest path $P$, from $s$ to $u$ (needs justification)*

On $P$, find $y$ (with predecessor $x$), the first vertex in $V-C$.

At the time $t$, we have $d[y]=\delta (s,y)$ (needs justification)**

Fact 1: $d[y]=\delta (s,y)\le \delta (s,y)\le d[u]$

Fact 2: At time $t$ the algorithm chose $u$. Hence

$$\begin{array}{r}d[u]\le d[y]\end{array}$$

From equations facts 1 and 2, we conclude: $d[y]=\delta (s,y)=\delta (s,u)=d[u]$

Justification 1: Use a shortest path $P$ from $s$ to $u$.

Proof:

• $s\ne u$, since $d[s]=\delta (s,s)=0$
• $s\in C⟹c\ne \varnothing$
• If there is no path from $s$ to $u$, then $\delta (s,u)=\infty$ and $d[u]=\infty$, so $d[u]=\delta (s,u)$
• There exists a path between $s$ and $u$. So there exists a shortest path. Name it $P$.

Justification 2: At time $t$, we have $d[y]=\delta (s,y)$

Proof:

• $x$ was added to $C$ before $u$. So, $d[x]=\delta (s,x)$.
• When $x$ was added to $C$, its edges were relaxed, including $(x,y)$
• $y$ is on the shortest path from $s$ to $u$, so the part of the path from $s$ to $y$ is a shortest path. Hence: $\delta (s,y)=\delta (s,x)+w(x,y)$
• For relaxing $(x,y),d[y]$ is compared to $\delta (s,x)+w(x,y)$ which is the minimum value for $d[y]$. So, at the time of relaxation $d[y]=\delta (s,x)+w(x,y)=\delta (s,y)$

Lecture 11

Definition

$G=(V,E)$ is a connected graph. A spanning tree in $G$ is a tree of the form $(V,A)$, with $A$ a subset of $E$.

In other words: a tree with edges from $E$ that covers all vertices. Examples: BFS tree, DFS tree.

Suppose edges have weights $w(e_i)$. The goal is to find a spanning tree with minimal weight.

$w(T)=37$

Kruskal’s algorithm

GreedyMST(G)
A = []
// sort edges by increasing weight - slow
for k = 1, ..., m do
	if e_k does not create a cycle in A then
		append e_k to A

Claim

Let $G$ be a connected, and let $A$ be a subset of the edges of $G$. If $(V,A)$ has no cycle and $|A|<n-1$, then one can find an edge $e$ not in $A$ such that $A\cup \{e\}$ still has no cycle.

Proof:

• In any graph, $|$vertices$|$ $-$ $|$connected components$|$ $\le$ $|$edges$|$
• For $(V,A)$, this gives $n-c<n-1$ so $c>1$
• Take any edge on a path that connects two components.

$({\sum }_{i=1}^c{n}_i)-c\le {\sum }_{i=1}^c(n_i-1)\le$ ${\sum }_{i=1}^c{m}_i\le m$

In $G^{\prime }=(V,A)$: $n-c\le |A|<n-1⟹c>1$

Which means that $G^{\prime }$ has at least two connected components which belong to $G$.

Take $e$ to be an edge on a path connecting two connected components of $G^{\prime }$ in $G$. $e$ does not create a cycle.

Claim

If the output is $A=[e_1,\dots ,e_r]$ then $(V,A)$ is a spanning tree (and $r=n-1$)

Proof:

Of course $(V,A)$ has no cycle. Suppose $(V,A)$ is not a spanning tree. Then, there exists an edge $e$ not in $A$, such that $(V,A\cup \{e\})$ still has no cycle.

Case 1: $w(e)<w(e_1$). Impossible, since $e_1$ is the element with the smallest weight.

Case 2: $w(e_i)<w(e)<w(e_{i+1})$. Impossible: At the moment we inserted $e_{i+1}$, we decided not to include $e$. This means that $e$ created a loop with $e_1,\dots ,e_i$.

Case 3: $w(e_r)<w(e)$. Impossible: We would have included it in $A$, since there is no loop in $A\cup \{e\}$.

Claim

Let $(V,A)$ and $(V,T)$ be two spanning trees, and let $e$ be an edge in $T$ but not in $A$. Then there exists an edge $e^{\prime }$ in $A$ but not in $T$ such that $(V,T+e^{\prime }-e)$ is still a spanning tree. Bonus: $e^{\prime }$ is on the cycle that $e$ creates in $A$.

Proof:

$e\in T,e\notin A$

$e=\{v,w\}$

Question

If we add $e$ to $A$, what happens?

$A$ will have a cycle. Let’s say the cycle is $C:v,w,\dots ,v$ in $A$.

$T$ splits into two subtrees after removing $e$.

$C$ starts in $A$, crosses over to $T$, so it contains another edge $e^{\prime }$ between $T$ and $A$.

We have that $e^{\prime }\in A$ and $e^{\prime }\notin T$

$(V,T^{\prime }=T\setminus \{e\}\cup \{e^{\prime }\})$ is a spanning tree.

Idea: Start with any spanning tree $T$ and make it step-by-step closer to $A$ while we make sure that at each step we get $T_i$ such that $w(T_{i+1})\le w(T_i)$

$w(\underset{\text{for some }i,A=T_i}{\underbrace{A}})\le \cdots \le w(T_1)\le w(T)$

Correctness: Exchange argument

• Let $A$ be the output of the algorithm
• Let $(V,T)$ be any spanning tree
• If $T\ne A$ let $e$ be an edge in $T$ but not in $A$
• So there is an edge $e^{\prime }$ in $A$ but not in $T$ such that $(V,T+e^{\prime }-e)$ is a spanning tree, and $e^{\prime }$ is on the cycle that $e$ creates in $A$.
• During the algorithm we considered $e$ but rejected it, because it created a cycle in $A$
• All other elements in this cycle have smaller (or equal) weight
• So $w(e^{\prime })\le w(e)$
• So $T^{\prime }=T+e^{\prime }-e$ has weight $\le w(T)$, and one more common element with $A$.

Lecture 12

Disjoint-set data structure. Stores partition of a set into disjoint subsets. We have operations to add sets, merge sets, and finding members of sets. This is used for Kruskal’s algorithm.

Operations on disjoint sets of vertices:

• Find: Identify which set contains a given vertex
• Union: Replace two sets by their union

T = []
U = {{v_1}, ..., {v_n}}
// sort edges by increasing weight
for k = 1,..., m do
	if U.Find(e_k.1) != U.Find(e_k.2) then
		U.Union(U.Find(e_k.1), U.Find(e_k.2))
		append e_k to T

We can use an array of linked lists.

Union process is straightforward. Combine linked list.

For find, we add an array of indices, $X[i]=$ set that contains $i$.

In the worst case:

• Find is $O(1)$
• Union traverses one of the linked lists, updates corresponding entries of $X$, concatenates two linked lists. Worst case $\Theta (n)$

Kruskal’s algorithm:

• Sorting edges $O(m\log (m))$
• $O(m)$ Find
• $O(n^2)$ Union

Worse case $O(m\log (m)+n^2)$

We can modify Union

• Each set in $U$ keeps track of its size
• Only traverse the smaller list
• Also add a pointer to the trail of the lists to concatenate in $O(1)$

Key observation: Worst case for one union is still $\Theta (n)$, but better total time.

For any given vertex $v$, the size of the set containing $v$ at least doubles when we update $X[v]$. So $X[v]$ is updated at most $\log (n)$ times. So the total cost of union per vertex is $O(\log (n))$

Conclusion: $O(n\log (n))$ for all unions and $O(m\log (m))$ total.

Greedy Algorithms

We are trying to solve a combinatorial optimization problem:

• Have a large, but finite, domain $\mathcal{D}$
• Want to find an element $E$ in $\mathcal{D}$ minimizes/maximizes a cost function

Greedy strategy:

• Build $E$ step by step
• Don’t think ahead
• Hard to prove correctness

Review from CS240: Huffman Tree

• Given frequencies $f_1,\dots ,f_n$ for characters $c_1,\dots ,c_n$
• We build a binary tree for the whole code

Greedy strategy: Build the tree bottom up

• Create many single-letter trees
• Define the frequency of a tree as the sum of the frequencies of the letters in it
• Build the final tree by putting together the smaller trees.

Claim

This minimizes ${\sum }_i{f}_i\times$ {length of encoding of $c_i$}

Interval Scheduling Problem

Input: $n$ intervals $[s_1,f_1],[s_2,f_2],\dots ,[s_n,f_n]$

Output: A maximal subset of disjoint intervals. By disjoint intervals we mean $[s_i,f_i]\cap [s_j,f_j]=\varnothing$

Example

A car rental company has the following requests for a given day:

• $I_1$: 2pm to 8pm
• $I_2$: 3pm to 4pm
• $I_3$: 5pm to 6pm Answer is $S=[I_2,I_3]$

Greedy strategies

• Consider the earliest starting time (Choose the interval with ${\min }_i{s}_i$)
• Consider shortest interval (choose the interval with ${\min }_i\{f_i-s_i\}$)
• Consider minimum conflicts (choose the interval that overlaps with the minimum number of other intervals)
• Consider earliest finishing time (Choose the interval with ${\min }_i{f}_i$)

Only the last one works.

Algorithm: Interval Scheduling

1. $S=\varnothing$
2. Sort the intervals such that $f_1\le f_2\le \cdots \le f_n$
3. For $i$ from 1 to $n$ do
   1. If Interval $i,[s_i,f_i]$, has no conflicts with intervals in $S$
      1. add $i$ to $S$
4. return $S$

Checking conflicts in $S$, we only need to check the last element in $S$. Thus it is possible in $O(n)$ for part 3.

Thus our total is $O(n\log n)$.

Correctness: The Greedy Algorithm Stays Ahead

Assume $O$ is an optimal solution. Our goal is to show $|S|=|O|$.

• Suppose $i_1,i_2,\dots ,i_k$ are the intervals in $S$ in the order they were added to $|S|$ by the greedy algorithm
• Similarly, let the intervals in $O$ be denoted by $j_1,\dots ,j_m$
  • Assume that the intervals in $O$ are ordered in the order of the start and finish times.
• We prove that $k=m$

Lemma: For all indices $r\le k$ we have that $f(i_r)\le f(j_r)$

Proof: We use induction

For $r=1$ the statement is true. The finish time of $i_1\le j_1$.

Suppose $r>1$ and the statement is true for $r-1$. We will show that the statement is true for $r$.

By induction hypothesis we have $f(i_{r-1})\le f(j_{r-1})$.

By the order on $O$ we have $f(j_{r-1})<s(j_r)$.

Hence we have that $f(i_{r-1})<s(j_r)$

Thus at the time the greedy algorithm chose $i_r$, the interval $j_r$ was a possible choice.

The greedy algorithm chooses an interval with the smallest finish time. So, $f(i_r)\le f(j_r)$

For the sake of contradiction, assume that the output $S$ is not optimal, then $|S|<|O|$.

$i_k$ is the last interval in $S$ and $O$ must have an interval $j_{k+1}$.

Apply the previous lemma with $r=k$, and we get $f(i_k)\le f(j_k)$.

We have $f(i_k)\le f(j_k)<s(j_{k+1})$.

So, $j_{k+1}$ was a possible choice to add to $S$ by the greedy algorithm. This is a contradiction.

Lecture 13

Interval Colouring Problem

Input: $n$ intervals $[s_1,f_1],[s_2,f_2],\dots ,[s_n,f_n]$

Output: Use the minimum number of colours to colour the intervals, so that each interval gets one colour and two overlapping intervals get two different colours.

Algorithm: Interval Colouring

Sort the intervals by starting time: $s_1\le s_2\le \dots \le s_n$

For $i$ from 1 to $n$ do:

Use the minimum available colour $c_i$ to colour the interval $i$. (i.e. use the minimum number to colour the interval $i$ so that it doesn’t conflict with the colours of the intervals that are already coloured).

Can be done in $O(n^2)$ (and even $O(n\log n)$).

If the greedy algorithm uses $k$ colours, then $k$ is the minimum number of colours needed. In other words, no other algorithm can solve the problem with $k-1$ colours.

Idea: Show that there exists a time $t$ such that it is contained in $k$ intervals.

Assume $\ell$ is the first interval which uses colour $k$. This means that $k-1$ other colours have been used.

Since we have an increasing order on start times: $s_{i_j}\le s_{\ell }1\le j\le k-1$

On the other hand, all intervals have overlap with $[s_{\ell },f_{\ell }]$, hence:

$$\begin{array}{r}{s}_{\ell }\le f_{i_j},\text{for}1\le j\le j-1\end{array}$$

So $s_{\ell }$ is the time which is contained in $k$ intervals, so no colouring with less than $k$ colours.

Minimizing Total Completion Time Problem

Input: $n$ jobs, each requiring processing time $p_i$

Output: An ordering of the jobs such that the total completion time is minimized.

Note: The completion time of a job is defined as the time when it is finished.

Example

$n=5$, processing times [2, 8, 1, 10, 5]

2	8	1	10	5
2	2	2	2	2
	8	8	8	8
		1	1	1
			10	10
				5
2	10	11	21	26	70

Total completion time $\ne$ total processing time

Algorithm: Order the jobs in non-decreasing processing times.

1	2	5	8	10
1	1	1	1	1	$5\times 1$
	2	2	2	2	$4\times 2$
		5	5	5	$3\times 5$
			8	8	$2\times 8$
				10	$1\times 10$
1	3	8	16	26	54

Correctness: Exchange Argument

Assume that there is an optimal solution with a different ordering in comparison to the solution by the greedy algorithm.

Let $L=[e_1,\dots ,e_n]$ is an optimal solution and $L$ is not in a non-decreasing order of processing time. So there exists $i$ such that $t(e_i)>t(e_{i+1})$. Sum of the completion times of $L$ is $nt(e_1)+(n-1)t(e_2)+\cdots +t(e_n)$.

$e_1$	$e_2$	$\cdots$	$e_{i-1}$	$e_i$	$e_{i+1}$	$\cdots$	$e_n$
$t(e_1)$	$t(e_1)$	$\cdots$	$t(e_1)$	$t(e_1)$	$t(e_1)$	$\cdots$	$t(e_1)$	$nt(e_1)$
	$t(e_2)$	$\cdots$	$t(e_2)$	$t(e_2)$	$t(e_2)$	$\cdots$	$t(e_2)$	$(n-1)t(e_2)$
			$⋮$	$⋮$	$⋮$	$\cdots$	$⋮$	$⋮$
			$t(e_{i-1})$	$t(e_{i-1})$	$t(e_{i-1})$	$\cdots$	$t(e_{i-1})$
				$t(e_i)$	$t(e_i)$	$\cdots$	$t(e_i)$	$(n-i+1)t(e_i)$
					$t(e_{i+1})$	$\cdots$	$t(e_{i+1})$	$(n-i)t(e_{i+1})$
							$⋮$	$⋮$
							$t(e_n)$	$1\times t(e_n)$

The contribution of $e_i$ and $e_{i+1}$ is $(n-i+1)t(e_i)+(n-i)t(e_{i+1})$.

After switching $e_i$ and $e_{i+1}$, we get another ordering, call it $L^{\prime }$ and the contribution of $e_i$ and $e_{i+1}$ in $L^{\prime }$ is: $(n-i+1)t(e_{i+1})+(n-1)t(e_i)$

$$\begin{array}{rl}T(L^{\prime })-T(L)& =(n-i+1)t(e_{i+1})+(n-1)t(e_i)-(n-i+1)t(e_i)+(n-i)t(e_{i+1})\\ & =t(e_{i+1})-t(e_i)<0\\ & ⟹T(L^{\prime })<T(L)\text{which is a contradiction}\end{array}$$

Dynamic Programming

Examples: Interval scheduling, longest increasing subsequence, longest common subsequence, all pairs shortest path.

Definition

Fibonacci Numbers

• $F_0=0,F_1=1$
• $F_n=F_{n-1}+F_{n-2}$ for $n\ge 2$

Slow recursive algorithm

Fib(n):
	if n == 0 return 0
	if n == 1 return 1
	return Fib(n-1) + Fib(n-2)

Assuming we count additions at unit cost, runtime is $T(0)=T(1)=0$, $T(n)=$T(n-1) + T(n-2) + 1$

This give $T(n)=F(n+1)-1$, so $T(n)\in \Theta ({\phi }^n)$, $\phi =(1+\sqrt{5})/2$

flowchart TD
Fn --- Fn-1
Fn-1 --- c[Fn-2]
c --- g[Fn-3]
c --- h[Fn-4]
Fn-1 --- d[Fn-3]
Fn --- Fn-2
Fn-2 --- e[Fn-3]
Fn-2 --- f[Fn-4]

Redundant computation.

To compute $F_n$, we only need the values of $F_0,\dots ,F_{n-1}$. The algorithm recomputes them many, many times.

Improved recursive algorithm

let T = [0, 1, x, y, ...]
Fib(n)
	if T[n] = x
		T[n] = Fib(n-1) + F(n-2)
	return T[n]

Iterative version

Fib(n)
	let T = [0,1, x, y, ...]
	for i = 2, ..., n
		T[i] = T[i-1] + T[i-2]
	return T[n]

These are DAGs.

Iterative version (enhanced)

Fib(n)
	(u,v) = (0,1)
	for i = 2, ..., n
		(u,v) = (v, u+v)
	return v

All these improved versions use $O(n)$ additions.

Main features: Solve “subproblems” bottom up, and store solutions if needed.

Recipe for designing a DP algorithms

1. Identify the subproblem
2. Establish DP-recurrence
3. Set values for the base cases
4. Specify the order of computation
5. Recovery of solution (if needed)

Key features:

• Solve problems through recursion
• Use a small (polynomial) number of nested subproblems
• May have to store results for all subproblems
• Can often be turned into one or more loops

Dynamic programming vs divide-and-conquer

• Dynamic programming usually deals with all input sizes
• Divide and conquer may not solve subproblems

Lecture 14

Interval Scheduling Problem

Input: $n$ intervals $I_i=[s_1,f_1],\dots ,I_n=[s_n,f_n]$ where each interval has weight $w_i$

Output: A choice $T$ of intervals that do not overlap and maximizes ${\sum }_{i\in T}{w}_i$. Greedy algorithm in the case $w_i=1$.

Example

A car rental company has the following requests for a given day:

• $I_1=[2,8],w_1=6$
• $I_2=[2,4],w_2=2$
• $I_3=[5,6],w_3=1$
• $I_4=[7,9],w_4=2$

Answer is $T=[I_1],W=6$

Basic idea: Either we choose $I_n$ or not.

• Then the optimum $O(I_1,\dots ,I_n)$ is the max of two values:
  • $w_n+O(I_{m_1},\dots ,I_{m_s})$, if we choose $I_n$, where $I_{m_1},\dots ,I_{m_s}$ are the intervals that do not overlap with $I_n$
  • $O(I_1,\dots ,I_{n-1})$, if we don’t choose $I_n$

In general, we don’t know what $I_{m_1},\dots ,I_{m_s}$ look like.

Goal:

• Find a way to ensure that $I_{m_1},\dots ,I_{m_s}$ are of the form $I_1,\dots ,I_s$, for some $s<n$ (and so on for all indices $<n$)
• Then it suffices to optimize over all $I_1,\dots ,I_j,j=1,\dots ,n$

Sort $I_j$‘s by increasing order of end time: $f_i\le f_{i+1}$

Define $p_j$ for interval $I_j$ to be the largest index less than $j$ such that the interval $I_{p_j}$ and $I_j$ are disjoint.

Claim: for all $j$, the set of intervals $I_k\le I_j$ that do not overlap $I_j$ is of the form $I_1,\dots ,I_{p_j}$ for some $0\le p_j\le j$ ($p_j=0$ if no such interval)

The algorithm will need the $p_i$‘s

• If $-\infty \le s_i<f_1,p_i=0f_1=$ earliest finish time
• If $f_1\le s_i<f_2,p_i=1$

Let $A$ be a permutation of $[1,\dots ,n]$ such that

$$\begin{array}{r}{s}_{A[1]}\le s_{A[2]}\le \cdots \le s_{A[n]}\end{array}$$

FindPj(A, s_1,...,s_n,f_1,...,f_n)
f_0 = -infty
i = 1
for k = 0, ..., n
	while i <= n and f_k <= s_{A[i]} < f_{k+1}
		p_{A[i]} = k
		i++

Runtime: $O(n\log (n))$ (sorting) and $O(n)$ (loops)

Main procedure:

Definition

$M[i]$ is the maximal weight we can get with intervals $I_1,\dots ,I_i$

Recurrence: $M[0]=0$ and for $i\ge 1$

$$\begin{array}{r}M[i]=\max (M[i-1],M[p_i]+w_i)\end{array}$$

Runtime: $O(n\log (n))$ (sorting twice) and $O(n)$ (finding the $M[i]$‘s)

0/1 Knapsack Problem

Input: Items $1,\dots ,n$ with weights $w_1,\dots ,w_n$ and values $v_1,\dots ,v_n$ and a capacity $W$.

Output: A choice of items $S\subset \{1,\dots ,n\}$ that satisfies the constraint ${\sum }_{i\in S}{w}_i\le W$ and maximizes the value ${\sum }_{i\in S}{v}_i$

Lecture 15

Continuing with the 0/1 Knapsack problem.

Basic Idea: Either we choose item $n$ or not

Then the optimum $O[W,n]$ is the max of two values

• $v_n+O[W-w_n,n-1]$, if we choose $n$ (and $w_n\le W$)
• $O(W,n-1]$ if we don’t choose $n$

$O[w,i]:=$ maximum value achievable using a knapsack of capacity $w$ and items $1,\dots ,i$.

Initial conditions: $O[0,i]=0$ for any $i$ and $O[w,0]$ for any $w$.

// 01KnapSack(v_1, ..., v_n, w_1 ..., w_n, W):
// initialize an array O[0..W,0..n]
for i = 1,...,n
	for w = 1,...,W
		if w_i > w:
			O[w,i] = O[w, i-1]
		else:
			O[w,i] = max(v_i + O[w-w_i, i-1], O[w, i-1])

The runtime of this algorithm is $\Theta (nW)$

This is called a pseudo-polynomial algorithm. In our word RAM model, we have been assuming all $v_i$‘s and $w_i$‘s fit in a word. So input size is $\Theta (n)$ words. But the runtime also depends on the values of the inputs.

01-knapsack is NP-complete, so we don’t really except to do much better.

The next problem is the longest increasing subsequence problem.

Input: An array $A[1,\dots ,n$] of integers.

Output: A longest increasing subsequence of $A$ (or just its length) (does not need to be contiguous).

Example

$A=[7,1,3,10,11,5,19]$ gives $[1,3,10,11,19]$

Remark: There are $2^n$ subsequences (including an empty one, which doesn’t count).

Tentative subproblems

Attempt 1:

• Subproblems: The length $\ell [i]$ of a longest increasing subsequence of $A[1\dots i]$
• For the example above, $\ell [6]=4$. Not enough to deduce $\ell [7]$

Attempt 2:

• Subproblems: The length $\ell [i]$ of a longest increasing subsequence of $A[1\dots i]$, together with its last entry
• Example: $\ell [6]=4$, with last element $11$. This is OK if we can add $A[i+1]$, but what if not?

Attempt 3:

• Let $L[i]$ be the length of a longest increasing subsequence of $A[1\dots i]$ that ends with $A[i]$, for $i=1,\dots ,n$. So $L[1]=1$

Idea:

A longest increasing subsequence $S$ ending at $A[i]$ looks like

$$\begin{array}{r}S=[\dots ,A[j],A[i]]=S^{\prime }\cup [A[i]]\end{array}$$

$S^{\prime }$ is a longest increasing subsequence ending at $A[j]$ (or it is empty). Don’t know $j$, but we can try all $j<i$ for which $A[j]<A[i]$.

Iterative Algorithm

// LongestIncreasingSubsequence(A[1..n])
L[1] = 1
for i = 2, ..., n do
	L[i] = 1
	for j = 1, ..., i-1 do
		if A[j] < A[i] then
			L[i] = max(L[i], L[j] + 1)
	return the maximum entry in L

The runtime is $\Theta (n^2)$

Remark: The algorithm does not return the sequence itself, but could be modified to do so.

Lecture 16

Longest Common Subsequence Problem

Input: Arrays $A[1\dots n]$ and $B[1\dots m]$ of characters.

Output: Maximum length $k$ of a common subsequence to $A$ and $B$ (not necessarily contiguous).

Example

$A=$ “blurry”, $B=$ “burger”, longest common subsequence is “burr”

$i/j$	0	1	$\cdots$	$j$	$\cdots$	$m$
0	0	0	$⋮$	0	$\cdots$	0
1	0
$⋮$	$⋮$
$i$	0			*
$⋮$	$⋮$
$n$	0					**

* = length of the longest common subsequence. Thus, the longest common subsequence exists in cell **.

In $A[1\dots i]$ and $B[1\dots j]$ 3 cases may happen:

1. $B[j]$ does not appear in the longest common subsequence. Then the sequence is contained in $A[1\dots i]$ and $B[1\dots j-1]$
2. $A[i]$ doesn’t appear in the longest common subsequence. Then the sequence is contained in $A[1\dots i-1]$ and $B[1\dots j]$
3. $A[i]=B[i]$ appears in the sequence, and the rest of the sequence is contained in $A[1\dots i-1]$ and $B[i\dots j-1]$

Definition

Let $M[i,j]$ be the longest subsequence between $A[1\dots i]$ and $B[i\dots j]$

• $M[0,j]=0$ for all $j$
• $M[i,0]=0$ for all $i$
• $M[i,j]$ is the max of up to three values
  • $M[i,j-1]$ (don’t use $B[j]$)
  • $M[i-1,j]$ (don’t use $A[i]$)
  • if $A[i]=B[j],1+M[i-1,j-1]$

Algorithm computes all $M[i,j]$ using two nested loops, so runtime $\Theta (nm)$

	1	2	3	4	5	6
A	b	l	u	r	r	y
B	b	u	r	g	e	r

$i/j$	0	1	2	3	4	5	6
0	0	0	0	0	0	0	0
1	0	1	1	1	1	1	1
2	0	1	1	1	1	1	1
3	0	1	2	2	2	2	2
4	0	1	2	3	3	3	3
5	0	1	2	3	3	3	4
6	0	1	2	3	3	3	4

Italics represent the path taken.

Walk back from the solution at $(6,6)$, each diagonal arrow adds a character.

Bellman-Ford Algorithm: Single source shortest path (with negative weights).

• If no negative cycle, computes all distances $\delta (s,v)$
• Can detect negative cycles

Definition

For $i=0,\dots ,n-1$ set ${\delta }_i(s,v)=$ length of the shortest path $s⇝v$ with at most $i$ edges if no such path, ${\delta }_i(s,v)=\infty$

This sets us up for a dynamic programming approach for shortest paths.

• This gives ${\delta }_0(s,s)=0$ and ${\delta }_0(s,v)=\infty$ for $v\ne s$.
• If there is no negative cycle, ${\delta }_{n-1}(s,v)=\delta (s,v)$.
• In any case, $\delta (s,v)\le {\delta }_i(s,v)$ for all $i$ and for all $v$.

Assume there are no negative cycles.

• $\delta (s,v)\le {\delta }_i(s,v)$

If ${\delta }_i(s,v)=\infty$, this is obvious. If ${\delta }_i(s,v)$ is a finite number, it means $\exists$ a path from $s$ to $v$. So, $\delta (s,v)$ is either the weight of that path or a shorter path. Hence, $\delta (s,v)\le {\delta }_i(s,v)$.

• ${\delta }_{n-1}(s,v)=\delta (s,v)$

If $\delta (s,v)=\infty$, then it is obvious. If $\delta (s,v)$ is a finite number, it is the weight of a shortest path $p$ from $s$ to $v$. We claim that $p$ has at most $n-1$ edges. If our claim is not true, then $p$ has at least $n$ edges, which means that one of the nodes appears at least twice in the path. Hence $p$ contains a cycle. The cycle cannot be negative by our assumption. Hence, it is a positive cycle which contradicts with $p$ being a shortest path. (remove the cycle from $p$, and we get a shortest path).

Recurrence: ${\delta }_i(s,v)=\min ({\delta }_{i-1}(s,v),{\min }_{(u,v)\in E}{\delta }_{i-1}(s,u)+w(u,v))$

Assume ${\delta }_i(s,v)<\infty$. This means that ${\delta }_i(s,v)$ is the length of a shortest path with at most $i$ edges which has a finite weight. The path either has exactly $i$ edges or at most $i-1$ edges. If it has at most $i-1$ edge, we use ${\delta }_{i-1}(s,v)$. If it has exactly $i$ edges, we decompose the path to one last edge $(u,v)$ and a path with $i-$ edges to $u$.

So we use ${\delta }_{i-1}(s,u)+w(u,v)$.

However, for finding the shortest path we need to consider all edges $9u,v)$ as the path may pass through any neighbours of $v$. Hence:

$$\begin{array}{r}{\delta }_i(s,v)={\delta }_i(s,v)=\min ({\delta }_{i-1}(s,v),\underset{(u,v)\in E}{\min }{\delta }_{i-1}(s,u)+w(u,v))\end{array}$$

// BellmanFord(G,s)
d_0 = [0, \infty, ..., \infty] // (s is the first index)
parent = [s, x, ..., x] // (s is the first index)
for i = 1, ..., n-1 do
	for all v in V do
		d_1[v] = d_{i-1}[v]
		for all (u,v) in E do
			if d_{i-1}[u] + w(u,v) < d_i[v] then
				d_i[v] = d_{i-1}[u] + w(u,v)
				parent[v] = u

Correctness: $d_i[v]={\delta }_i(s,v)$, so $d_{n-1}[v]=\delta (s,v)$ if no negative cycles.

//BellmanFord2.0
d = [0, \infty, ..., \infty] // (s is the first index)
parent = [s, x, ..., x] // (s is the first index)
for i = 1, ..., n-1 do
	for all (u,v) in E do
		if d[u] + w(u,v) < d[v] then
			d[v] = d[u] + w(u,v)
			parent[v] = u

Runtime is: $O(mn)$

Lecture 17

Plan to show correctness of the improved version. Show that for $i=0$ to $n-1$ after $i-th$ iteration.

$$\begin{array}{r}\delta (s,v)\le d[v]{\delta }_i(s,v)=d_i[v]\forall v\end{array}$$

If this is true, then after $n-1$ iterations:

$$\begin{array}{r}\delta (s,v)\le d[v]\le {\delta }_{n-1}(s,v)=d_{n-1}[v]=\delta (s,v)\end{array}$$

Claim

For all $i$, after iteration $i$, we have $d[v]\le d_i[v]$ for all $v$

Proof: By induction

True for $i=0$, so we suppose true at index $i-1$ and prove true at $i$. At the beginning of the loop, for all $v$, $d[v]\le d_{i-1}[v]$. $d[v]$ can only decrease, so this stays true throughout the loop. $d[v]$ is replaced by $\min (d[v],{\min }_{(u,v)\in E}(X+w(u,v)))$, where $X\le d_{i-1}[u]$. So at the end of iteration $i$, $d[v]\le d_i[v]$.

The operation $d[v]\leftarrow \min (d[v],d[u]+w(u,v))$ is called a relaxation.

Claim

$d[v]$ can only decrease through a relaxation, and if $\delta (s,u)\le d[u]$ and $\delta (s,v)\le d[v]$ before relaxation, then $\delta (s,v)\le d[v]$ post relaxation.

Proof: First item is obvious.

Second item: $\delta (s,v)\le \delta (s,u)+w(u,v)$ (triangle inequality). So $\delta (s,v)\le d[u]+w(u,v)$. But also, $\delta (s,v)\le d[v]$.

Consequence: If all $d[v]$ satisfy $\delta (s,v)\le d[v]$, and we apply any number of relaxations, all inequalities stay true.

Claim

For $i=0,\dots ,n-1$, after iteration $i$, $\delta (s,v)\le d[v]\le {\delta }_i(s,v)$ for all $v$.

Proof: We have proved this via the previous two claims.

Summary:

If there is no negative cycle

• At the end, $d[v]=\delta (s,v)$ for all $v$
• In particular, for any edge $(u,v)$, $d[v]\le d[u]+w(u,v)$

If there is a negative cycle $⟹$ there exists an edge $(u,v)$ such that $d[v]>d[u]+w(u,v)$.

Proof: There exists a negative cycle: $v_0,v_1,\dots ,v_k=v_0$ and ${\sum }_{i=1}^{k}w(v_{i-1},v_i)<0$

Assume for all $i$‘s we have $d[v_i]\le d[v_{i-1}]+w(v_{i-1},v_i)$ sum the previous inequality around the cycle:

$$\begin{array}{rl}\sum _{i=1}^{k}d[v_i]& \le \sum _{i=1}^k(d[v_{i-1}]+w(v_{i-1},v_i))\\ & \le \sum _{i=1}^{k}d[v_{i-1}]+\sum _{i=1}^{k}w(v_{i-1},v_i)\end{array}$$

Since we have ${\sum }_{i=1}^{k}d[v_i]={\sum }_{i=1}^{k}d[v_{i-1}]$ (as $v_0=v_k$), we conclude ${\sum }_{i=1}^{k}w(v_{i-1},v_i)\ge 0$ which is a contradiction.

So, if there is a negative cycle $v_1,v_2,\dots ,v_k$ with $v_k=v_1$

• Claim: There must be an edge $(v_1,v_{i+1})$ with $d[v_{i+1}]>d[v_i]+w(v_i,v_{i+1})$
• Else: $d[v_{i+1}]\le d[v_i]+w(v_i,v_{i+1})$ for all $i$; sum and derive a contradiction.

Conclusion: For extra $O(m)$, can check the presence of a negative cycle.

Floyd-Warshall Algorithm: No fixed source, computes all distances $\delta (u,v)$

Negative weights are OK, but no negative cycles. Simple pseudo-code, but slower than other algorithms. Doing Bellman-Ford from all $u$ takes $O(m{n}^2)$

Subproblems for dynamic programming

• Bellman-Ford uses paths with fixed number of steps
• Floyd-Warshall restricts which vertices can be used

Bellman-Ford considers number of edges.

Floyd-Warshall considers intermediate vertices.

$D_0(v_j,v_k)$ is the length of a shortest path from $v_j$ to $v_k$ with no intermediate vertices.

$D_i(v_j,v_k)$ is the length of a shortest path from $v_j$ to $v_j$ with $\{1,\dots ,i\}$

• $D_0(v_j,v_j)=0$
• $D_0(v_j,v_k)=w(v_j,v_k)$ if there is an edge $(v_j,v_k)$
• $D_0(v_j,v_k)=\infty$ otherwise.

$D_n(v_j,v_k)=\delta (v_j,v_k)$

Claim

$D_i(v_j,v_k)=\min (D_{i-1}(v_j,v_k),D_{i-1}(v_j,v_i)+D_{i-1}(v_i,v_k))$

Proof: Either the shortest path does not go through $v_i$, or it does (and if it does, it’s only once).

DP recurrence for Floyd-Warshall.

Consider a shortest path from $v_j$ to $v_k$ with all intermediate vertices in $\{v_1,\dots ,v_i\}$ and call it $p$.

Case 1: $v_i$ is not on $p$. Then the intermediate path vertices on $p$ are in $\{v_1,\dots ,v_{i-1}\}$ so we can use $D_{i-1}(v_j,v_k)$

Case 2: $v_i$ is on $p$. Then we can decompose $p$ to $p_1$ and $p_2$. $p_1$ is a shortest path from $v_j$ to $v_k$. $p_2$ is a shortest path from $v_i$ to $v_k$. In both $p_1$ and $p_2$, all intermediate paths are in $\{v_1,\dots ,v_{i-1}\}$. So in both cases we can use $D_{i-1}$

//FloydWarshall(G)
// set up D_0 above
for i = 1, ..., n do
	for j = 1, ..., n do
		for k = 1, ..., n do
			D_i[v_j, v_k] = min(D_{i-1}[v_j, v_k], D_{i-1}[v_j, v_i] + D_{i-1}[v_i, v_k])

Runtime and memory: $\Theta (n^3)$

Lecture 18

Edit Distance

Input: Arrays $A[1\dots n]$ and $B[1\dots m]$ of characters.

Output: Minimum number of $\{$ add, delete, change $\}$ operations that turn $A$ into $B$.

Example

A = “snowy”, B = “sunny” There are multiple answers: 3C; 1A, 1C, 1D; 2A, 1C, 2D

There are three cases.

Case 1:

$$\begin{array}{r}\dots A_n\\ \dots B_m\end{array}$$

We write $A[n]$ on top of $B[m]$. The last column will add 1 to the cost if $A[n]\ne B[m]$ and adds zero if $A[n]=B[m]$. The edit distance of the remaining columns is based on the edit distance between $A[1\dots n-1]$ and $B[1\dots m-1]$

Case 2:

$$\begin{array}{r}\dots A_n\\ \dots \text{textemdash}\end{array}$$

In this case, the edit distance is 1 plus the edit distance between $A[1\dots n-1]$ and $B[1\dots m]$

Case 3:

$$\begin{array}{r}\dots \text{textemdash}\\ \dots B_m\end{array}$$

In this case, the edit distance is 1 plus the edit distance between $A[1\dots n]$ and $B[1\dots m-1]$

Generalize: Let $D$ be an array of sizes $(n+1)\times (m+1)$.

$D[i,j]=$ ED between $A[1\dots i]$ and $B[i\dots j]$

Definition

Let $D[i,j]$ be the edit distance between $A[1\dots i]$ and $B[1\dots j]$

• $D[0,j]=j$ for all $j$ (add $j$ characters)
• $D[i,0]=i$ for all $i$ (delete $i$ characters)
• $D[i,j]$ is the min of three values
  • $D[i-1,j-1]$ (if $A[i]=B[j]$) or $D[i-1,j-1]+1$ (otherwise)
  • $D[i-1,j]+1$ (delete $A[i]$ and match $A[1\dots i-1]$ with $B[1\dots j]$)
  • $D[i,j-1]+1$ (add $B[j]$ and match $A[1\dots i]$ with $B[1\dots j-1]$)

The algorithm computes all $D[i,j]$, using two nested loops, so runtime is $\Theta (mn)$

Optimal binary search trees

Input:

• Integers $1,\dots n$
• Probabilities of access $p_1,\dots p_n$ with $p_1+\cdots p_n=1$

Output:

• An optimal BST with keys $1,\dots ,n$
• Optimal: Minimizes ${\sum }_{i=1}^n{p}_i\cdot$(depth$(i)+1$) $=$ expected number of tests for a search.

Example

$p_1=p_2=p_3=p_4=p_5=1/5$

flowchart TD
a(3) --- b(2)
b --- c(1)
a --- d(5)
d --- e(4)

$(1/5\times 1)+(2\times (1/5\times 2))+(2\times (1/5\times 3))=2.2$

flowchart TD
a(1) --- b(2)
b --- c(3)
c --- d(4)
d --- e(5)

$1/5(1+2+3+4+5)=3$

A greedy strategy does not work here.

Assume it does, and we put the key with the highest probability in the root.

	1	2	3	4	5
$p_i$	$0.1$	$0.2$	$0.25$	$0.05$	$0.4$

flowchart TD
a(5) --- b(3)
b --- c(2)
b --- d(4)
c --- e(1)

$(0.4\times 1)+(0.25\times 2)+(0.2\times 3)+(0.05\times 3)+(0.1\times 4)=2.05$

However, there is a better cost.

flowchart TD
a(3) --- b(2)
a --- c(5)
b --- d(1)
c --- e(4)

$(0.25\times 1)+(0.2\times 2)+(0.4\times 2)+(0.1\times 3)+(0.05\times 3)+1.9$

Define $M[i,j]$ to be the minimal cost for the items $i$ to $j$. Take an item, say $k$, between $i$ and $j$ and put it in the root.

We chose just a $k$ between $i$ and $j$ and the cost will be

$$\begin{array}{rl}& M[i,k-1]+\sum _{\ell =i}^{k-1}{p}_{\ell }+p_k+M[k+1,j]+\sum _{\ell =k+1}^j{p}_{\ell }\\ & =M[i,k-1]+M[k+1,j]+\sum _{\ell =i}^j{p}_{\ell }\end{array}$$

Recurrence

$$\begin{array}{r}M[i,j]=\underset{i\le k\le j}{\min }\left(M[i,k-1]+M[k+1,j]\right)+\sum _{\ell =i}^j{p}_{\ell }\end{array}$$

An independent set of a graph $G=(V,E)$, is $S\subseteq V$ if there are no edges between elements of $S$.

Given a tree as the input, either the root appears in a maximum independent set $S$ or not.

Case 1: $r\in S$

Since $r\in S$, none of the children of $r$ can be in $S$. So, the remaining part of $S$ should come from subtrees rooted at grandchildren of $r$.

Case 2: $r\notin S$

In this case all elements of $s$ are from subtrees rooted at children of $r$.

Lecture 19

Decision Problem: Given a problem instance $I$, answer a certain question “yes” or “no”.

Problem Instance: Input for the specified problem.

Problem solution: Correct answer (“yes” or “no”) for the specified problem instance. $I$ is a yes-instance if the correct answer for the instance $I$ is “yes”. $I$ is a no-instance if the correct answer for the instance $I$ is “no:.

Size of the problem instance: $Size(I)$ is the number of bits required to specify (or encode) the instance $I$.

The goal is to find a polynomial time algorithm to convert (transform) inputs of a problem $A$ to inputs of a problem $B$.

Polynomial Time Reduction: A decision problem $A$ is polynomial time reducible to a decision problem $B$, if there is a polynomial time algorithm $F$ that transforms any instance $I_A$ of $A$ to an instance $I_B$ of $B$ such that $I_A$ is a YES-instance of $A$ $⟺$ $F(I_A)=I_B$ is a YES-instance of $B$.

We write $A{\le }_{P}B$, if such a polynomial time reduction exists. We also write $A{=}_{p}B$ if $A{\le }_{P}B$ and $B{\le }_{P}A$.

Assume $A$ and $B$ are decision problems and we are given:

• An algorithm $Al{g}_B$, which solves $B$ in polynomial time,
• A polynomial reduction $F$, which gives $A{\le }_{P}B$

Design a polynomial time algorithm to solve $A$.

Input: An instance $I_A$ of $A$

Output: Whether $I_A$ is a YES-Instance

$p(n):$ Use $F$ to transform $I_A$ into $I_B=F(I_A)$, which is an instance of the problem $B$

$q(n)$: Return $Al{g}_B(I_B)$

If the running time of $F$ is $p(n)$, then the output of $F$ which is $F(I_A)$ has the property: $|F(I_A)|\le p(n)$ (Since the algorithm $F$ has to return $F(I_A)$). The total running time: If $Al{g}_B$ has runtime $q(n)$ then the total running time is $O(q(p(n)))$

Transitivity of Polynomial time reductions

Lemma: $A{\le }_{P}B$ and $B{\le }_{P}C⟹A{\le }_{P}C$

$A{\le }_{P}B⇝$ There exists a polynomial time algorithm $F$ which maps instance of $A$ to $B$

$B{\le }_{P}C⇝$ There exists a polynomial time algorithm $H$ which maps instances of $B$ to $C$.

Question

What does $H\circ F$ (Composition of $H$ and $F$) do?

$H\circ F$ maps the instances of $A$ to $C$ in polynomial time. It also respects the property on yes/no instances.

Assume problem $A$ is known to be impossible to be solved in polynomial time.

It is true that $A{\le }_{P}B⟹B$ cannot be solved in polynomial time.

Assume the contrary statement. $B$ can be solved in polynomial time with an algorithm $Al{g}_B$. Then we use $Al{g}_B$ for solving $A$ be reducing it to $B$, which is a contradiction.

Now looking at the notation again: $A{\le }_{P}B$. $B$ is at least as hard as $A$, in other words, if we could solve $B$ in polynomial time, then we could solve $A$ in polynomial time.

The following three problems are equivalent in terms of polynomial-time solvability.

Maximum Clique:

$S\subseteq V$ is a clique if, $\{u,v\}\in E$ for all $u,v\in S$.

Input: $G=(V,E)$ and an integer $k$

Output: Is there a clique in $G$ with at least $k$ vertices.

Maximum Independent set (IS):

$S\subseteq V$ is an independent set if, $\{u,v\}\notin E$ for all $u,v\in S$.

Input: $G=(V,E)$ and an integer $k$

Output: Is there an independent set in $G$ with at least $k$ vertices.

Minimum Vertex Cover (VC):

$S\subseteq V$ is a vertex cover if, $\{u,v\}\cap S\ne \varnothing$ for all $\{u,v\}\in E$

Input: $G=(V,E)$ and an integer $k$

Output: Is there a vortex cover in $G$ with at most $k$ vertices.

Clique ${\le }_P$ IS

For the Clique problem, we must find a set of size at least $K$ of vertices with all edges in between.

For the IS problem, we must find a set of at least $k$ vertices with no edges in between.

$(V,E)=G,k⇝\bar{G},k=(V,\bar{E})$

Idea: Change edges into no edges (Find the complement of $G$). $F$ is the algorithm to construct the complement of input $G$ for the clique. Clearly it can be done in polynomial time and one can check that $S\subseteq V$ is a clique in $G$ if and only if $S$ is an independent set in $G$. Hence $\{G,k\}$ is a YES-instance for clique if and only if $\{\bar{G},k\}$ is a YES-instance for IS.

Assume $G=(V,E)$ is a graph.

Lemma: $S\subseteq V$ is a vertex cover $⟺$ $V-S$ is an independent set in $G$.

($⟹$) Assume $S$ is a vertex cover in $G$. If $V\setminus S$ is not an IS in $G$, then there must exist $x,y\in V\setminus S$ such that $(x,y)\in E$. By definition of a vertex cover, one of $x$ or $y$ must be in $S$ which is a contradiction

( $⟸$ ) Assume $V\setminus S$ is an IS in $G$. If $S$ is not a vertex cover in $G$, then there exists an edge $(x,y)\in E$ such that $x\notin S$ and $y\notin S$. This means that $x,y\in V\setminus S$ and there is an edge between them, which is a contradiction.

We want to show that VC ${\le }_P$ IS and IS ${\le }_P$ VC

The previous lemma shows that: $G$ has a vertex cover of size at worst $k⟺G$ has an IS of size at least $n-k$.

So our reduction algorithm maps $\{G,k\}$ for CV to $\{G,n-k\}$ for IS.

It runs in polynomial time and maps yes/no instances of VC to yes/no instances for IS respectively. The above results and transitivity shows that Clique ${=}_P$ IS ${=}_P$ VC.

More Simple Reductions

Hamiltonian Cycle (HC):

A cycle is a Hamiltonian Cycle if it touches every vertex exactly once.

Input: Undirected graph $G=(V,E)$

Output: Does $G$ have a Hamiltonian Cycle.

Hamiltonian Path (HP):

A path is a Hamiltonian Path if it touches every vertex exactly once.

Input: Undirected graph $G=(V,E)$

Output: Does $G$ have a Hamiltonian path.

Proposition: HP ${=}_P$ HC

Proof of HP ${\le }_P$ HC

Given $G=(V,E)$ for HP we have to transform it to $G^{\prime }=(V^{\prime },E^{\prime })$ for HC.

We construct $G^{\prime }$ in the following way:

• Add a vertex $s$ to $V$: $V^{\prime }=V\cup \{s\}$
• Add edges $(s,x)$ for all $x\in V$

Claim: $G$ has a HP $⟺G^{\prime }$ has a HC

($⟹$) Assume $P$ is a HP in $G$, with endpoints $a$ and $b$. Then $P+\{s,a\}+\{b,s\}$ is a HC in $G^{\prime }$

($⟸$) Assume $C^{\prime }$ is a HC in $G^{\prime }$. There must be two incident edges on $s$, call them $\{a,s\}$ and $\{b,s\}$. Then by removing $\{a,s\}$ and $\{b,s\}$ from $C^{\prime }$, we get $C$ which is a HP in $G$.

Lecture 20

Proof of HC ${\le }_P$ HP

Assume $G=(V,E)$ is given for HC. We construct $G^{\prime }=(V^{\prime },E^{\prime })$ in the following way:

Choose an arbitrary vertex $x\in V$

• Add a duplicate $x^{\prime }$ of $x$
• Add vertices $t$ and $t^{\prime }$ with degree one and edges $\{t,x\}$ and $\{t^{\prime },x^{\prime }\}$

It is a polynomial time computation.

Claim: $G$ has a HC $⟺$ $G^{\prime }$ has a HP

($⟹$) Assume there a HC in $G$

($⟸$) Assume there is a HP in $G^{\prime }$, it should have the form:

The two end points must be $t$ and $t^{\prime }$ (degree 1 nodes). $x^{\prime }$ has two neighbours, $t^{\prime }$ and a node called $y$. We also know that $\{x,y\}$ is an edge in $G$ as $x^{\prime }$ is a copy of $x$. So, by removing $\{t^{\prime },x^{\prime }\},\{x^{\prime },y\},\{t,x\}$ and adding $\{x,y\}$, we get a H which is in $G$.

Review:

$X=\{x_1,\dots ,x_n\}$ where $x_i$‘s are Boolean variables. A literal term is either $x_i$ or ${\bar{x}}_i$. A clause is a disjunction of distinct literals, $t_1\vee t_2\vee \cdots \vee t_{\ell }$, where $t_i\in \{x_1,\dots ,x_n,{\bar{x}}_1,\dots ,{\bar{x}}_n\}$. We say that the clause is of length $\ell$.

An assignment satisfies a clause $C$ if it causes $C$ to evaluate to true. A conjunction of a finite set of clauses, $C_1\wedge C_2\wedge \cdots \wedge C_k$ is called a formula in CNF CS245.

3-SAT Problem

Input: A CNF-formula in which each clause has at most three literals.

Output: Is there a truth assignment to the variables that satisfies all the clauses.

Theorem

3-SAT ${\le }_P$ IS

$(x\vee y\vee z)\wedge (\bar{x}\vee y\vee \bar{z})$

A CNF with at most 3 literals per clause is given.

For each clause we form a triangle with vertices labeled as the literals of the clause

$(x\vee \bar{y}\vee z)⇝$ Graph with edges $(x,\bar{y}),(x,z),(z,\bar{y})$

A clause with 2 literals will be an edge joining the literals.

A clause with one literal is easy to deal with, we don’t include them.

To force exactly one choice from each clause, we set $k$ to the number of clauses.

We have to make sure that we are not choosing opposite literals $x,\bar{x}$ in different clauses.

So, we put an edge between any two vertices that correspond to opposite literals.

This construction takes polynomial time.

Claim

Suppose the formula has $k$ clauses. Then the formula is satisfiable $⟺$ there is an independent set (IS) of size $k$ in the graph.

Note: We only have two types of edges:

1. Type 1: Edges in the clauses
2. Type 2: Edges between two clauses

Proof:

($⟹$) Assume the formula is satisfiable. Then we have at least one literal per clause which is set to true. For each clause choose one literal which is true and add its corresponding node to the set $S$.

Since we picked one node per clause $|S|=k$. The set $S$ is an independent set. Between any two nodes in $S$, there are no type 1 edges (by construction). Also we don’t choose nodes with type 2 edges between them.

($⟸$) Now assume there is an IS of size $k$ in $G$. Any independent set can have at most one node in each clause, since there are edges between all nodes in a clause.

As $G$ has only $k$ clauses, our IS has exactly one vertex from each clause.

Moreover, because of the second type edges, we do not have $x$ and $\bar{x}$ at the same time in our IS.

For each $x_i$ in the IS we set $x_i$ to be true. Otherwise we set $x_i$ to be false.

This assignment satisfies every clause $■$

For a problem $X$, we represent an instance of $X$ as a binary string $S$.

Definition

A problem $X$ is in NP, if there is a polynomial time verification algorithm $AL{G}_X$ such that the input $S$ is a yes-instance $⟺$ there is a proof (certificate) $t$ which is a binary string of length $poly(|S|)$ so that $AL{G}_X(S,t)$ returns yes.

Vertex Cover

• $S$ here is an input graph $G=(V,E)$ and an integer $k$
• $t$ here is a subset of $U$ of $V$ with $|U|\le k$ $Al{g}_v(S,t)$: go through all $E$ and check if $t$ covers the edges and $t\le k$.

3-SAT

• $S$ here is a 3-SAT formula
• $t$ here is a truth assignment $Al{g}_v(S,t)$: check whether $t$ satisfies all clauses

Clique, IS, HC, HP, Subset-Sum are all in NP.

Question

Are all problems in NP?

No.

Definition

co-NP is the set of decision problems whose no-instances can be certified in polynomial time.

Every polynomial time solvable decision problem is in NP.

Definition

$P$ is the set of decision problems that can be solved in polynomial time.

P $\subseteq$ NP.

The most important open problem in theoretical computer science.

Question

Is P equal to NP?

The name NP comes from Non-deterministic Polynomial time. A non-deterministic machine, has the power to correctly guess a solution.

Informally, we say a problem is NP-complete if it is the hardest problem in NP.

Definition

A problem $X\in$ NP is NP-complete if $Y{\le }_{P}X$ for all $Y\in$ NP

Fact

P $=$ NP $⟺$ an NP-complete problem can be solved in polynomial time.

Theorem (Cook-Levin)

3-SAT is NP-complete

Lecture 21

If we can prove 3-SAT ${\le }_{P}X$ , then $X$ is NP-complete. For example IS $\in$ NPC, since 3-SAT ${\le }_P$ IS

To prove that a problem $X\in$ NP is NP-complete, we just need to find a NP-complete problem $Y$, and prove that $Y{\le }_{P}X$

Circuit-SAT

• Instance: A circuit $=$ DAG with labels on the vertices
• Inputs labelled by boolean variables $x_1,\dots ,x_n$
• Internal vertices labelled by and, or, not
• There is a marked vertex $v$ for the output
• Problem: Is there a choice of boolean $x_i$ that makes $v$ true?

Plan to prove Cook-Levin Theorem

1. Show that Circuit-SAT is NP-complete
2. Show that Circuit-SAT ${\le }_P$ 3-SAT

Circuit-SAT is NP-complete (sketch)

Given: instance $S$ of $A\in$ NP

Want: proof (certificate) $t$ such that $AL{G}_A(S,t)=$ true

Verification algorithm $AL{G}_A(S,t)$ can be turned into a circuit with $t$ as input. We call Circuit-SAT to find $t$

Example

Problem $A$: IS Instance $S$ complete graph with 3 vertices, $k=2$ Certificate $t$: 3 bits $y_1,y_2,y_3$

$V=\{v_1,v_2,v_3\}$

All possible subsets:

$$\begin{array}{rl}{y}_1& y_2{y}_3\\ \{\}\to & 000\\ \{v_1\}\to & 100\\ \{v_2\}\to & 010\\ \{v_3\}\to & 001\\ \{v_1,v_2\}\to & 110\\ \{v_1,v_3\}\to & 101\\ \{v_2,v_3\}\to & 011\\ \{v_1,v_2,v_3\}\to & 111\end{array}$$

Circuit for $AL{G}_A(S,t)$ computes the formula

$(y_1+y_2+y_3\ge 2)\wedge \overline{y_1\wedge y_2}\wedge \overline{y_1\wedge y_3}\wedge \overline{y_2\wedge y_3}$

We have shown that all problems in NP are reducible to Circuit-SAT. In order to be NP-complete, we must also show that this problem is in NP (not hard).

We will now show that Circuit-SAT is reducible to 3SAT.

From logic we know that we have the following $(p⟺q)\equiv (p\vee \bar{q})\wedge (\bar{p}\vee q)$

$$\begin{array}{rl}& (g⟺h_1\wedge h_2)\\ & \equiv (g\vee \overline{(h_1)\wedge h_2)})\wedge (\overline{g}\vee (h_1\wedge h_2))\\ & \equiv (g\vee \overline{h_1}\vee \overline{h_2})\wedge (\overline{g}\vee h_1)\wedge (\overline{g}\vee h_2)\end{array}$$

$$\begin{array}{rl}& (g⟺h_1\vee h_2)\\ & \equiv (\overline{g}\vee (h_1\vee h_2))\wedge (g\vee (\overline{h_1\vee h_2}))\\ & \equiv (\overline{g}\vee h_1\vee h_2)\wedge (g\vee \overline{h_1})\wedge (g\vee \overline{h_2})\end{array}$$

$$\begin{array}{rl}& (g⟺\overline{h})\\ & \equiv (\overline{g}\vee \overline{h})\wedge (g\vee h)\end{array}$$

We add a variable ($o$) for the output.

gives $(y_1⟺(x_1\wedge x_2))\wedge (y_2⟺(x_2\vee x_3))\wedge (v⟺(y_1\wedge y_2))\wedge v$ and

$$\begin{array}{r}F=(y_1\vee \overline{x_1}\vee \overline{x_2})\wedge (\overline{y_1}\vee x_1)\wedge (\overline{y_1}\vee x_2)\wedge \\ (y_2\vee \overline{x_2})\wedge (y_2\vee \overline{x_3})\wedge (\overline{y_2}\vee x_2\vee x_3)\wedge \\ (v\vee \overline{y_1}\vee \overline{y_2})\wedge (\overline{v}\vee y_1)\wedge (\overline{v}\vee y_2)\wedge v\end{array}$$