Page: https://cs.uwaterloo.ca/~lapchi/cs341/index.html

Instructor: Lap Chi LAU

Time: W,F 11:20am-12:50pm EST

• Week 1. May 11
• Week 2. May 19
• Week 3. May 26
• Week 4. June 2
• Week 5. June 9
• Week 6. June 16
• Week 7. June 23
• Week 8. June 30
• Week 9. July 7
• Week 10. July 14
• Week 11. July 21
• Week 12. July 28

Week 1. May 11

• assn * 5 (50%)
• mt June 28 9am-9am (20%)
• final Aug 14 (30%)

computation model

• Word-RAM model
  • access an arbitrary position of an array in constant time
  • each word operation (add, mul, rw) done in constant time

eg. graph problem on n vertices -> use $\log_2n$ bits to label vertices (assume they fit into a word)

eg. binary search done in $O(\log_2n)$ assumes constant random access

eg. (3-sum) have n numbers $a_1,a_2,...,a_n$ and a target number c, find indices i, j, k such that $a_i+a_j+a_k=c$ or report that such triples do not exist.

algo1: observe this can be rewritten as $c-a_i-a_j=a_k$, idea: enumerate all pairs $a_i,a_j$ and check whether $c-a_i-a_j=a_k$ for some k.

sort(a)
for i = 1, n:
    for j = 1, n:
        if binary_search(a, c-a[i]-a[k]) is not nullptr:
            report them

runtime: $O(n\log n)+O(n^2\log n)=O(n^2\log n)$

(in worst case, hashing does not guarantee constant retrieval)

algo2: this can be rewritten as $a_i+a_j=c-a_k$ idea: enumerate all pairs $a_k$ and check whether $a_i+a_j=c-a_k$ for some pair i, j.

sort(a)
for k = 1, n:
    // solve 2-sum problem in O(n) given a sorted array

runtime: $O(n^2)$

eg. (2-sum) have n numbers $a_1\le a_2\le...\le a_n$ (sorted!) and a target number b, find indices i, j such that $a_i+a_j=b$ or report that such pairs do not exist.

b = 19:
|1 |4 |6 |8 |9 |11|14|20|
 ^                    ^
 L                    R

auto L = 1
auto R = n
while L <= R: // allow equal
    auto sum = a[L] + a[R]
    if sum == b:
        report L, R
    else if sum > b:
        --R
    else:
        --L
nope

runtime: each iteration R-L decreases by 1, hence at most n iterations => O(n).

proof of correctness:

• if no such pairs exist - we won't find them
• if such a pair $i \le j$ exists. assume by contradiction that the algo missed it. at this time L > R. before the end, there exists a time such that L=i or R=j.
  consider the first time that it happens, wlog assume L=1, then R>j. then $a_L+a_R=a_i+a_R>a_i+a_j=b$ (sum is too big). hence for the next iterations right R pointer will move left and until the sum is b, the left L pointer will freeze. but then i, j are found. $\square$

solving recurrence

mergesort

see CS240 (recursion tree)

lecture this time says T(n) = cnlogn (tree has logn levels) - why?

eg. $T(n)=4T(\frac{n}{2})+n=O(n^2)$
in the recursion tree, each level has $n$, $4\frac{n}{2}=2n$, $16\frac{n}{4}=4n$, $64\frac{n}{8}=8n$, ..., $4^{\log n}\cdot1=n^2$ (increasing). the order is dominated by the leaf level. $\square$

eg. $T(n)=2T(\frac{n}{2})+n^2=O(n^2)$
in the recursion tree, each level has $n^2$, $2(\frac{n}{2})^2=\frac{n^2}{2}$, $4(\frac{n}{4})^2=\frac{n^2}{4}$, ... (decreasing). the order is dominated by the root level. $\square$

eg. mergesort $T(n)=2T(\frac{n}{2})+n$, the sequence is non-changing. order is the sum of all levels. $\square$

Week 2. May 19

recursion tree in general setting

theorem. (master theorem) consider $T(n)=aT(\frac{n}{b})+n^c$ where constant $a\ge1,b>0,c\ge0$ (a is integer). then let $r:=\frac{a}{b^c}$

• if $r=1$, then $T(n)=O(n^c\log_bn)$.
• if $r<1$, then $T(n)=O(n^c)$.
• if $r>1$, then $T(n)=O(n^{\log_ba})$.

proof. at the root level, work done is $n^c$, next level: $a(\frac{n}{b})^c$, next level: $a^2(\frac{n}{b^2})^c$, ....
at the leaf level, the problem size should be bounded by constant ie $\frac{n}{b^i}\le K$ for the level number i. we then have $i\ge\log_bn-\log_bK$. eg we can let $i=\log_bn$. the number of leaves is $a^{\textrm{\# levels}}=a^{i}= a^{\log_bn}=n^{\log_ba}$.
the work done on each level is a geometric sequence with ratio $\frac{a}{b^c}=r$.

1. if $\frac{a}{b^c}=1$, then every level has the same work. total work = (# levels)(work at each level) = $n^c\log_bn$.
2. if $\frac{a}{b^c}<1$, then root level dominates, total work =$\sum_{i=0}^{\log_ba}n^c(\frac{a}{b^c})^i<n^c\sum_{i\ge0}(\frac{a}{b^c})^i=n^c\frac{1}{1-\frac{a}{b^c}}$.
3. if $\frac{a}{b^c}>1$, note the sequence diverges, leaf level dominates, total work = $O(n^{\log_ba})$. $\square$

eg. $T(n)=T(\sqrt{n})+1$.
note $T(n)=(T(n^{\frac{1}{4}})+1)+1=...$. the work done on each level is 1, so the total work = # levels. at bottom level i we have $n^{\frac{1}{2^i}}\le K\Rightarrow \frac{1}{2^i}\log n\le \log K\Rightarrow\log n\le2^i\log K\Rightarrow i\ge\log\log n$ for bound $K$. this means as long as i is this large the problem size is bounded to this constant. we have $T(n)=O(\textrm{\# levels})=O(\log\log n)$. $\square$

eg. $T(n)=T(n-1)+T(n-2)+n^c=O(1.618...^n\cdot n^c)$.

divide & conquer

counting inversion pairs

eg. given n distinct numbers $a_1,...,a_n$, give the number of "inversion" pairs with $i\le j,a_i>a_j$.

• naive: list all pairs, O(n^2)
• eg. array is [3, 7, 5, 1, 4], then pairs are (3, 1), (7, 5), (7, 1), (7, 4), (5, 1), (5, 4) -> 6 pairs.
• (assume n is a power of two) break the array into two half, and suppose I already know the counts of each half.

  |3|7|2|5| |9|1|6|4|
   ^           ^
   i           j      -- crossing pair
  

• then we only need to count the "crossing" pairs whose left value (i) appears in the left subarray, and right value (j) on the right.
  • idea 1: sort left half
    • for all numbers on the right, find in left how many numbers are bigger than it <- use binary search
    • this step uses O(nlogn + nlogn)=O(nlogn)
  • idea 2: merge two sorted arrays
    • this step uses O(n)
• then add the three counts

// idea 2
count_sort(A[n]):
    if n == 1:
        return 0
    int n1 = count_sort(A[1 : n/2])     // T(n/2)
    int n2 = count_sort(A[n/2+1 : n])   // T(n/2)
    int nm = merge_count(A)             // T(n)
    return n1 + nm + n2

merge_count(A[n]):
    int sum = 0
    // same as merge_sort's merge function
    // there are two ptrs l and r at the start of each sub array
    // whenever we put one value from right array at r, this means on the left array,
    // elements from l to end are bigger than it. hence we add the # of these values
    // to sum.
    return sum

idea 1 in total uses $T(n)=2T(\frac{n}{2})+O(n\log n)=O(n\log^2n)$.

idea 2 in total uses $T(n)=2T(\frac{n}{2})+O(n)=O(n\log n)$.

maximum sum subarray

eg. given n numbers $a_1,...,a_n$, find i, j that maximizes $\sum_{k=i}^ja_k$.

• naive: try all i and j, O(n^3)
• slightly better:
  • for all i
    • compute partial sum $\sum_{k=i}^ja_k$ for all j from i to n. these partial sums can be computed in one go, then select the max. this step is O(n)
  • total time is O(n^2)
• (assume n is a power of two) break array into two and suppose the max sums of each are known.
• we only need to find the max "crossing" sum and compare it with the existing two
  • then for $i\le\frac{n}{2}<j$, [i, j] is a max sum subarray crossing the midpoint iff $[i,\frac{n}{2}]$ is a max sum subarray ending at the end of left half and $[\frac{n}{2}+1,j]$ is a max sum subarray starting from the start of right array.

  |1|-2|3|-4|5|4|   |2|3|1|-3|-2|-1|
            /////   ///////               -- max left & right sum
  

  • use partial sum method. this step uses O(2n).

runtime: $T(n)=2T(\frac{n}{2})+O(n)=O(n\log n)$. (this is not the best)

closest pair

eg. given n points $(x_1,y_1),...,(x_n,y_n)$ on the 2d plane, find a pair $i\le i<j\le n$ that minimizes $\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$.

• assumption: all x's are distinct
• naive: find all pairs: O(n^2)
• we find a line L that divides the points into two halves Q and R.
  • so find the mediam x-value.
• suppose we already know the minimums in Q and R, and the minimum distance so far is $\delta$.
  • now we only need to find the crossing pairs: $(x_i,y_j)\in Q,(x_j,y_j)\in R$ with distance $<\delta$.

       -δ    L    δ
           . |    .
      .  .   |   . .     .
   .       . |       .
       .     |   .
             |
  

  • they then must exist within $(L-\delta,L+\delta)$

   -δ    L     δ
         |
   +---+---|---+---+
   |   |   |   |   |
   +---+---|---+---+
   | . | . | . | . |
   +---+---|---+---+
   | . | . | . | . |
   +---+---|---+---+
   | . | p | . | . |       . are candidate points
   +---+---|---+---+
   |   |   |   |   |
   +---+---|---+---+
           |
  

  • we divide this region into squares of side length $\frac{\delta}{2}$.
    • obs1: each square has at most one point (otherwise the distance between 2 is less than $\delta$)
    • obs2: points that are two squares apart have distance $>\delta (=2\frac{\delta}{2})$
    • hence there are at most 11 other candidate points around with distance $<\delta$
      • constant

the algo:

1. base case: if there is 1 point, minimum distance is inf; if there are 2 points, distance is their distance
2. find the dividing line L by computing the median using the x-values. O(n)
3. solve two subproblems. 2T(n/2)
4. using a linear scan, remove all points not within the narrow region. O(n)
5. sort points in non-decreasing order by their y-values. O(nlogn)
   • stable sort?
6. for each point, compute its distance to the next 11 points in this y-ordering (imagine flatting the boxes). O(n)
7. return minium distance found, and the two points

runtime: $T(n)=2T(\frac{n}{2})+O(n\log n)=O(n\log^2n)$

• we can sort the points by y at the beginning, then $T(n)=2T(\frac{n}{2})+O(n)=O(n\log n)$.
• we can sort the points by x at the beginning so the median-finding in the recursion is easy in practice - overall analytical runtime does not change

where do we use the assumption x being distinct?

• if there are points on the median line - need to alter the algo to not let them be
  • what if all points are on the same line? - sort then find adjacent dist

integer multiplication

eg. given two n-bit binary numbers $a=a_1...a_n,b=b_1...b_n$, find ab.

• normal long mult: O(n^2)
• suppose we know how to multiply n-bit numbers, how tow multiply 2n-bit numbers?
  • let $x=x_1x_2,y=y_1y_2$ where $x_1,x_2,y_1,y_2$ are n-bits.
  • $xy=(x_1\cdot2^n+x_2)(y_1\cdot2^n+y_2)=x_1y_1\cdot2^{2n}+(x_1y_2+x_2y_1)2^n+x_2y_2$
  • so $T(2n)=4T(n)+O(n)\Rightarrow T(n)=O(n^2)$ (2^n done in constant by shift)
  • no speedup just using divide & conquer!

Karatsuba's algorithm

• instead of 4 subproblems, we do 3 subproblems
• $xy=x_1y_1\cdot2^{2n}+((x_1+x_2)(y_1+y_2)-x_1y_1-x_2y_2)2^n+x_2y_2$
• time: $T(2n)=3T(n)+O(n)\Rightarrow T(n)=O(n^{\log_23})$. (not the best, see fft)

matrix multiplication

eg. given matrices $A,B\in \mathbb{R}^{n\times n}$, find AB.

• normal multiplication: O(n^3)

Strassen's algorithm two multiply two matrices $\in\mathbb{R}^{2n\times 2n}$, we divide it into 4 submatrices $\in\mathbb{R}^{n\times n}$, and

$$AB= \begin{bmatrix} P_5+P_4-P_2+P_6 &P_1+P_2\\ P_3+P_4 &P_1+P_5-P_3-P_7 \end{bmatrix}$$

where

$$\begin{aligned} P_1&=A_{11}(B_{12}-B_{22})\\ P_2&=(A_{11}+A_{12})B_{22}\\ P_3&=(A_{21}+A_{22})B_{11}\\ P_4&=A_{22}(B_{21}-B_{11})\\ P_5&=(A_{11}+A_{22})(B_{11}+B_{22})\\ P_6&=(A_{12}-A_{22})(B_{21}+B_{22})\\ P_7&=(A_{11}-A_{21})(B_{11}+B_{12}) \end{aligned}$$

runtime: $T(2n)=7T(n)+O(n^2)\Rightarrow T(n)=O(n^{\log_27})$. if $n\ge5000$, it is faster than normal algorithm.

puzzle: determine whether a graph contains triangles. hint: for each entry in Adj^i, it is the # of i-length paths. check Adj with Adj^2.

Week 3. May 26

median-finding

eg. have n distinct numbers $a_1,...,a_n$, find the median.

• use sort: O(nlogn)

eg. relaxed: have n distinct numbers, find the k-th smallest number.

1. find a pivot $a_i$, put all smaller elements on the left, bigger elements on the right
2. let r be the rank of $a_i$
   • if r = k, we are done
   • if r > k, then find the k-th element on the left (T(r-1))
   • id r < k, then find the k-th element on the right (T(n-r))

runtime: $T(n)\le \max\{T(r-1), T(n-r)\}+O(n)$.

• worst case, eg r=n, then $T(n)\le T(n-1)+O(n)\Rightarrow T(n)=O(n^2)$
• best, $r=\frac{n}{2}$, then $T(n)\le T(\frac{n}{2})+O(n)+p(n)$ where p is time to find a pivot. if $p(n)=O(n)$ then $T(n)=O(n)$. but this happens when the pivot is the median.. we run into loop
• suppose we throw away 10% of elements every run, eg $\frac{n}{10}\le r\le \frac{9n}{10}$, then $T(n)\le T(\frac{9n}{10})+p(n)+O(n)$ then $T(n)=O(n)$ - this is a good pivot.

we use this method to find the pivot in linear time:

median of medians

1. divide n elements into $\frac{n}{5}$ groups, each group has 5 numbers (O(n))
2. compute median of each group, call them $b_1,b_2,...,b_{\frac{n}{5}}$ (O(n))
3. return median of these numbers
   • lemma: let r be the rank of this number, then $\frac{3n}{10}\le r\le \frac{7n}{10}$.
     proof. note all medians on the left $\frac{n}{10}$ groups are smaller than this median of medians. for each of these groups, the smallest 3 elements are smaller than individual group's median, thus smaller than the median of median. hence we eliminated $\frac{3n}{10}$ numbers on the left. similar for right side. $\square$

puzzle: what if we divide into groups of 3, 7, 9, ..., $\sqrt{n}$.

breath first search

graph connectivity

adjacency matrix vs. adjacency list

• can check edge in matrix for O(1)
• matrix uses $\Omega(n^2)$ space

defn. two vertices $u,v$ are connected if there is a path from $u$ to $v$.

defn. a subset of vertices $S\subseteq V$ is connected if $u,v$ are connected for all $u,v\in S$.

defn. a graph is connected if $u,v$ are connected for all $u,v\in V$.

defn. a connected component is maximally connected subset of vertices.

eg. determine whether a graph is connected.
pick s, run bfs. then graph is connected iff visited[v] = true for all v.

eg. find all connected components of a graph.
pick s, run bfs to find reachable vertices. this is one component. then do the same for remaining vertices. (O(n + m))

eg. determine whether two vertices u, v are connected.
run bfs from u, check visited[v] = true.

eg. find shortest path between two vertices u, v. see next!

breath first search

motivation: ask friend networks eg.

// G = (V, E), s ∈ V
// output: reachable vertices from v
reachable_vertices(G, s):
    auto visited = {v: false for v in G.V}
    auto Q = new queue
    Q.enqueue(s)
    visited[s] = true

    while Q is not empty:
        auto u = Q.dequeue()
        for each v in u:
            if not visited[v]:
                Q.enqueue(v)
                visited[v] = true
    return [v for v, b in visited if b]

runtime: each vertex is enqueued at most once, when we dequeue a vertex u, then the for loop is run deg(n) steps. total time: $O(n+\sum_{v\in V}\mathrm{deg}(v))=O(n+m)$. (recall handshake lemma: sum of degrees = 2*number of edges)

correctness:

• lemma: there is a path from s to v iff visisted[v] = true at the end.
  • suppose visited[v] = true, will use induction. base: visited[s] = true, and there is a path from s to s. inductive step: now suppose visited[v] = true and there is a path from s to v for checked v's, we want to show a newly visited[u] = true implies a path from s to u. since visited[u] = true, this step is run inside some for loop for some v (as a neighbor of it), as for that v, it is reachable from s, by extending this path to u, we have s reaches u.
  • suppose there is a path from s to v. its contrapositive is "if visited[v] = false, then there is no path from s to v". consider a set U of all vertices s.t. visited[v] = true for all vertices v. then there are no edges with one endpoint in U, and one endpoint in V-U (otherwise that endpoint in V-U would have visited=true in the for loop of the V-side endpoint otherwise). hence for all vertices in V-U, it is not reachable from s. $\square$

BFS tree

how to trace out from a path from s to v?

• in the loop of u, do parent[v] = u
• the edges (v, parent[v]) form a tree
• the path from root to s on a BFST is a shortest path from root to s

sproof.: use induction. base case is one vertex, clear. then in every for loop, we already have a tree (parent dict), we encounter a new unvisited child vertex, then we are just extending from a leaf vertex (as parent) to the current child, hence we maintain the tree. (|E|=|V|-1)
for shortest path: when we enqueue & dequeue vertices from the queue, the 1-distance vertices will always be in the front (because we discovered them early, and we are using a queue), and then 2-distance... (closer vertices always in the front) we are also building a tree in this order, so this tree-building traversal should reflect the shortest path. $\square$

eg.

// G = (V, E), s ∈ V
bfst(G, s):
    auto visited = {v: false for v in G.V}
    auto Q = new queue
    auto parent = {}
    auto distance = {}
    Q.enqueue(s)
    visited[s] = true
    parent[s] = nullptr
    distance[s] = 0  // not necessary

    while Q is not empty:
        auto u = Q.dequeue()
        for each v in u:
            if visited[v]:
                continue
            Q.enqueue(v)
            visited[v] = true
            parent[v] = u
            distance[v] = distance[u] + 1

bipartite graphs

defn. a graph $G=(V,E)$ is bipartite if there is a bipartition $(L,R)$ of $V$ such that all edges have one endpoint in $L$ and one endpoint in $R$.

eg. check whether a graph is bipartite.

• trivial: try all bipartition ($\Omega(n^2)$)
• idea: pick a vertex v, suppose it is lhs, then its neighbors must be on rhs, whose neighbors must be back to lhs... then this is a bipartite.

1. assume G is connected (otherwise run algo on all components)
2. let $L=\{v|\mathrm{dist}(s,v)\text{ is even}\}$,$R=\{v|\mathrm{dist}(s,v)\text{ is old}\}$ (use bfst)
3. if there is an edge with both endpoints in L, or both in R, then G is not a bipartite.
4. otherwise it is.

runtime: O(|V|+|E|).

correctness:

• if the algo says yes -> it is correct because we found a bipartite
• if the algo says no. it is sufficient to show there exists an odd cycle in G. wlog suppose there are two connected odd (even similar) vertices u, v with a least common ancestor w (which can be s). then regardless of the parity of w, length of $P_{uw}$ + length of $P_{vw}$ = even, plus the edge uv there is an odd cycle. $\square$
• (graph is bipartite iff it does not have odd cycles)

remark.

• this provides an algorithmic proof that a graph is bipartite iff it has no odd cycle
• this bfs algo is also linear time algo to find an odd cycle in an undirected graph
• having an odd cycle is a 'short' proof that a graph is non-partite

depth first search

motivation: find path from s to t in a maze

• bfs is not a good idea - because we have to go back and forth. it is more straightforward to stick to one path until dead ends
• (random walk is O(n^2))

dfs(G, s):
    auto visited = {v: false for v in G.V}
    visited[s] = true

    explore(u):
        for v in u:
            if not visited[v]
                visited[v] = true
                explore(v)

    explore(s)
    return [v for v, b in visited if b]

• runtime: each vertex v is called explore(v) at most once in the for loop, so there are deg(v) operations. total complexity O(n+m).
• dfs uses stack while bfs uses queue
• dfs can solve the same graph connectivity problems as bfs (except shortest path)

DFS tree

how to trace out from a path from s to v?

• in the loop of u, do parent[v] = u
• the edges (v, parent[v]) form a tree

defn. usual root, parent, ancestor, descendant

defn. a non-tree edge uv is called a back edge if either u is an ancestor or descendant of v. (in the graph)

theorem. in an undirected graph, all non-tree edges are back edges.
proof. it is sufficient to show it is impossible to have an edges that connects two leaf nodes in the tree (thus the only way is to connect back to the ancestor). suppose u and v are leaves, and u is in a subtree rooted at t. case 1: t is not done and we are at u, if we connect uv, then they have parent-child relation, and uv would be in-tree. case 2: t is done, then we backtrack to the node t and continue exploring its next child trees, then tv have parent-child relation. $\square$

Week 4. June 2

starting & finishing time

we can record the time when a vertex is first visited and when a vertex finished exploring:

auto visited = {v: false for v in G.V}
visited[s] = true
auto start = {}
auto finish = {}
auto time = 1

    explore(u):
        start[u] = time++
        for v in u:
            if not visited[v]
                visited[v] = true
                explore(v)
        finish[u] = time++
explore(s)

theorem. (parenthesis) the intervals [start[u], finish[u]] and [start[v], finish[v]] are either disjoint or one interval contains the other.
proof.

• case 1: u is an ancestor of v. then start[u] < start[v] is clear. we must finish v before backtracking to u, thus finish[v] < finish[u]. so start[u] < start[v] < finish[v] < finish[u]
• case 2: u and v do not have ancestor relation, but have common ancestor w. then we must start and finish one of them (say u) before we can go to the other one v, hence start[u] < finish[u] < start[v] < finish[v]. $\square$

cut vertices and cut edges

suppose $G$ is connected,

• a vertex $v$ is a cut vertex if $G-v$ is not a connected graph.
• an edge $e$ is a cut edge if $G-e$ is not a connected graph.

find all cut vertices and cut edges.

• naive: for all v, check whether G-v is connected (O(n(n+m))). edge similar.

claim. in the dfs, a subtree $T_i$ below $v$ is a connected component in $G-v$ iff there are no edges with one endpoint in $T_i$ and another endpoint in an ancestor of $v$.
proof:

• (forward) if $T_i$ is connected component, then it is clear it should not connect to any outer vertices.
• (backward) by the property of back edges, an off-tree edge going out from $T_i$ to some ancestor is the only possibility to check. $\square$

hence we only need to consider a few cases.

lemma. for a non-root vertex $v$ in a dfs tree, $v$ is a cut vertex iff there is a subtree below $v$ with no edges going to an ancestor of $v$.
proof:

• (forward) suppose v is cut vertex, then it is clear no edges from below v would go to any ancestors because that would cause the graph to be connected and v would not be cut vertex.
• (backward) by claim. $\square$

lemma. for the root vertex $v$ in a dfs tree, $v$ is a cut vertex iff $v$ has at least two children.
proof:

• case 1: v has degree 1. then it is clear that v is not a cut vertex (as the remaining graph is connected)
• case 2: v has degree >= 2. if i remove v, then the remaining parts must be disconnected to each other because subtrees have no ancestors at all. $\square$

idea: for each subtree $T_v$ rooted at v, find the vertex that is reached by back edges from $T_v$ that is closest to root.

• let low[v] := min {start[w] | all edges uw with $u\in T_v$} (this tracks the min depth)
• computeLow():
  • base case: v is leaf, then low[v] = min {start[w] | vw ∈ E} (O(deg(v)))
  • otherwise we have computed low[$u_i$] correctly for all direct child of v. then low[v] = min {low[$u_1$],...} U {start[w] | $vw\in E$} (O(deg(v)))
  • total runtime: $\sum_{v\in V}\mathrm{deg}(v)=O(n+m)$
• for every vertex v, to check whether it is a cut vertex, we check whether low[$u_i$] < start[v] for all i
  • if yes, then v is not a cut vertex
  • if no, then v is a cut vertex
  • runtime is also sum of degrees => O(n+m)

how to find cut edges? tree edge uv is cut edge iff low[v] > start[u]; back edges can never be cut edge.

directed graphs

defn. if $uv$ is a directed edge, then $u$ is the tail and $v$ is the head.

defn. the in-degree of a vertex $v$, $\mathrm{indeg}(v)$, is the number of edges with $v$ being the head. $v$ is source if indeg is 0.

defn. the out-degree of a vertex $v$, $\mathrm{outdeg}(v)$, is the number of edges with $v$ being the tail. $v$ is sink if outdeg is 0.

defn. a directed graph is a directed acyclic graph if there is no directed cycle.

defn. $t$ is reachable from $s$ if there is a directed path from $s$ to $t$.

defn. a directed graph $G=(V,E)$ is strongly connected if for every pair of vertices $u,v\in V$, $u$ is reachable from $v$ and $v$ is reachable from $u$.

defn. a subset $S\subseteq V$ is called strongly connected if for every pair of vertices $u,v\in S$, $u$ is reachable from $v$ and $v$ is reachable from $u$ (path can go outside)

defn. a subset $S\subseteq V$ is a strongly connected component if $S is a maximally strongly connected subset. ie S is strongly connected but S+v is not for any $v\in V-S$.

eg. determine if a graph is strongly connected.

eg. determine if a graph is a DAG.

eg. find all strongly connected components of a directed graph.

both DFS and BFS are same as undirected graphs, except that we only explore out-neighbors.

BFS tree

• by setting dist[v] = dist[u] + 1, we can compute all shortest path distances from s
• in undirected graphs, for all non-tree edges uv, dist[u]-1 <= dist[v] <= dist[u]+1
• in directed graphs, there could be non-tree edges uv with huge difference in dist[u] and dist[v], however they have to be 'backward edges'.

DFS tree

• in undirected graphs, all non-tree edges are back edges
• in directed graphs, there could be 'cross edges' (only goes from right left to left leaf) or 'forward edges'

strongly connected graphs

given a graph G=(V,E), return yes if G is strongly connected.

• naive: there are O(n^2) pairs to check. for each pair, do bfs/dfs, total: O(n^2(n+m))
• naive2: for each vertex v, check whether it can reach all other vertices. total: O(n(n+m))

claim. G is strongly connected iff every vertex $v\in V$ is reachable from s and s is reachable from every vertex $u\in V$, where s is arbitrary.
proof.

• (forward) definition
• (backward) combine the path from s to v and the path from u to s, then u and v are connected. because these u and v are arbitrary, we have result.$\square$

claim. given $G=(V,E)$, we reverse the direction of all edges to obtain $G^R=(V,E^R)$. then there is a path from v to s in G iff there is a path from s to v in $G^R$.

• so s is reachable from every $v\in V$ in G iff if every $u\in V$ is reachable from s in $G^R$.

algo:

• choose arbitrary vertex s.
• run bfs to check whether it can reach all other vertices
• reverse direction of all edges in G (linear)
• run bfs again from s
• both yes => graph is strongly connected

runtime: O(n+m)

eg. find shortest walk from s to t with odd length.
copy the graph and have odd vertices and even vertices. find path from even s to odd t.

DAG

given a graph G=(V,E), return yes if it is DAG.

prop. if a directed graph is acyclic, then one can find a vertex with indegree of 0.
proof. suppose otherwise that all vertices in G has indegree at least 1. to prevent a directed cycle, we must have vertices laid out like: $v_1\rightarrow v_2\rightarrow ...$, the middle ones have indegree >= 1. when we run out of vertices, we cannot extend this pattern further, so we could only go backward. as all vertices must have indegree >= 1, we have to go back to $v_1$ but that would form a directed cycle. $\square$

defn. a topological ordering is an ordering of vertices such that all edges go forward.

prop. a directed graph is acyclic iff there exists a topological ordering of the vertices.
proof.

• (backward) if such ordering exists, then all edges go forward, implying there are no cycles otherwise an edge would go backward.
• (forward) use induction. suppose G has exactly one vertex v, then there exists a topological ordering. now suppose for any smaller graph the statement is true, we want to show it is true for the bigger one too. consider G-v where v has indegree of 0, then it has a topological ordering. we put this v to the front of the ordering to get a topological ordering of G. $\square$

algo:

• repeatedly find a vertex v of indegree zero
  • remove v from the graph (remove the edges and thus possibly reduces some other vertices' indegree by 1), and put v to the beginning of the topological ordering
• if the only vertices left have indegree > 0, then G is not a DAG
• this also provides a topological ordering of G

runtime: O(n+m) (kahn's algo)

DAG (2)

theorem. (parenthesis) the intervals [start[u], finish[u]] and [start[v], finish[v]] are either disjoint or one interval contains the other.
proof. same as undirected. $\square$

lemma. if G is DAG, then for any edge uv, finish[v] < finish[u] for any dfs.
proof.:

• case 1: start[v] < start[u]. since G is dag, and u reaches v, we have v cannot reach u, so u cannot be a descendant of v in dfs tree, so [start[v], finish[v]] and [start[u], finish[u]] are disjoint. so finish[v] < finish[u].
• case 2: start[v] > start[u]. then v is descendant of u, so [start[u], finish[u]] contains [start[v], finish[v]], so finish[v] < finish[u]. $\square$

algo:

• run dfs on whole graph
  • means if for some root s, we do not cover all vertices, then do more dfs on remaining vertices (O(n+m))
• output the ordering with decreasing finishing time
• check if it is a topological ordering. if not, G is not acyclic.
  • if G is acyclic, then lemma implies all edges in this ordering go forward.

runtime: O(n+m)

Week 5. June 9

strongly connected components

find all strongly connected components of a directed graph.

claim. two strongly connected components must be vertex-disjoint.
proof. otherwise the common vertex reaches and is reachable from all vertices in both components, then the two 'components' are not maximal, and we actually only have one strongly connected component. $\square$

observation. contracting each strongly connected component results in a DAG (otherwise components are not maximal).

observation. suppose we start a bfs/dfs on a 'sink component', then we can identify the vertices in that sink component. (eg GHIJKL)

• idea: after finding the sink component, we can remove it from the graph.
• how to find a vertex in a sink component?
• idea: if we topologically sort, we can find vertices with small outdegs
  • if we do dfs on the whole graph, then the vertex with the smallest finishing time is a sink
  • does not work if first starting from E - this ordering is not good enough

lemma. if $C_1,C_2$ are strongly connected components and there are directed edges from $C_1$ to $C_2$, then the largest finishing time in $C_1$ is larger than the largest finishing time in $C_2$.
proof.

• case 1: first vertex v to be visited is in $C_2$, then every vertex in $C_2$ will be visited, and will be finished before any vertex in $C_1$ started because v does not go to $C_1$.
• case 2: first vertex v to be visited is in $C_1$, then v has to visit every vertex in both $C_1,C_2$ then finishes. $\square$

observation. if we have the topological ordering (decreasing finishing time), then do dfs again using this ordering, then we will always first visit an 'ancestor component' before visiting a 'descendant component'.

• we instead want to start from descendant components - reverse graph

algo

1. run dfs on whole graph and sort vertices by decreasing finishing time
2. let c = components
3. for i=1,n do:
   • if visited[i] = false (and i is not in any c)
     • dfs($G^R$, i)
     • mark all vertices reachable from i in $G^R$ in this iteration to be in component c
     • append them to c

runtime: O(m+n)

greedy algorithms

work by using simple and/or local rules to make decisions and then commit on them.

minimizing total completion time

have n jobs with processing times $p_1,...,p_n$, find an ordering of the jobs to finish so as to minimize the total completion time, where the completion time of a job is defined as time time when it is finished.

• total completion time implies average completion time
• eg. have 7, 2, 6, 5, 8.

  | 2 | 5 | 6 | 7 | 8 |
      2  7   13   20  28
  

  total completion time: 70
• sort the job by increasing process time.

correctness: if it is not in non-decreasing order, then we want to show the solution is not optimal. then there exists an adjacent inversion pair, p[i] > p[i+1]. if we flip these two jobs, we can know that the sum completion times of all other jobs are the same (and after because p[i]+[i+1] does not change). for these two jobs, the time for old ordering is p[i]+p[i]+p[i+1], in the new ordering, it is p[i+1]+p[i+1]+p[i]. the new ordering is better. $\square$

minimizing total completion time (2)

have n jobs, each with processing time $p_i$ and weight $w_i$. find an ordering of the jobs to finish so as to minimized to total weighted completion time, where weighted completion time of a job is defined as its weight * its completion time.

• eg. have p=3,7,2, w=1,3,1

  | 2 | 3 | 7 |
      2   5   36   total: 43
  
  | 7 | 2 | 3 |
      21  9   12   total: 42
  

• what is the answer?

interval scheduling

given n intervals $[s_1,f_1],...,[s_n,f_n]$, find the maximum subset of disjoint intervals.

there are multiple natural greedy algos:

• earliest start time
  • counterexample: if we have a long job that starts earlier
• earliest finish time
• shortest intervals: good approximation
  • counterexample: consider [1,5], [4,6], [5,10]
• minimum conflicts (choose interval which overlaps with fewest other intervals)
  • counterexample: consider [0,1], [1,5], [4,6], [5,10], [10,11], and many [0,2]'s and many [9,11]'s

algo:

1. sort the interval so that $f_1\le...\le f_n$. let initial solution $S=\varnothing$
2. for $1\le i\le n$, if interval $[s_i,f_i]$ is disjoint from all intervals in S, then add it to S
   • we only need to check with the previous one for overlapping (need proof)
3. return S

runtime: O(nlogn + n)

claim. there exists an optimal solution with $I_1=[s_1,f_1]$ chosen.
proof. suppose there exists an optimal solution S that does not include $I_1$. suppose further the first interval in S conflicts with $I_1$. because $I_1$ has smallest finishing time, it is earlier than the second interval in S. we can swap the first interval with $I_1$ and the result is still optimal. $\square$

lemma. there is an optimal solution using the first k intervals of the greedy solution for any k.
proof. use induction on k. when k=1, this is the above claim. otherwise since we use disjoint intervals, we reuse the above argument. $\square$

if the number of intervals in solution is l, we apply the lemma with k=l.

interval coloring

given n intervals $[s_1,f_1],...,[s_n,f_n]$, find a coloring of the intervals using the minimum # of colors possible, so that each interval gets one color and any two overlapping intervals get different colors.

algo:

1. sort intervals so that $s_1\le...\le s_n$.
2. for $1\le i\le n$, use the minimum available color to color the i-th interval

correctness: it is sufficient to show if the algo returns k colors, it is because at one moment there are k intervals pairwise overlapping with each other.

      t
------|-     1
  ----|--    2
 -----|----- 3
    --|---   k    current interval I_i

since all these intervals contain the start time $s_i$ (we sorted by start time), there are k intervals, so we need k.

Week 6. June 16

huffman coding

defn. we construct prefix code so that no encoding string is a prefix of another encoded string.

• allows easy encoding and decoding without ambiguity.

given n symbols, with frequencies $\sum_{i=1}^n f_i=1$. find a binary decoding tree T with n leaves that minimizes $\sum_{i=1}^nf_i\cdot\mathrm{depth}_T(i)$ (average length of encoded strings).

observation. any optimal binary decoding tree is full (every internal node is two children).
proof. because we can just delete the violating internal node without affecting disambiguation. $\square$

    r                r
   /                /
  _          =>    w
 /
w

corollary. in the decoding tree there are at least two leaves of maximum depth that are siblings.

observation. (simple claim) there is an optimal solution in which the two symbols with lowest frequencies are assigned to leaves of maximum depth, and furthermore they are siblings.
proof. if we have $f_i>f_j$ but $\mathrm{depth}(i)>\mathrm{depth}(j)$, note:

$$\begin{aligned} &\quad \,\,(f_i\cdot\mathrm{depth}(i)+f_j\cdot\mathrm{depth}(j))-(f_i\cdot\mathrm{depth}(j)+f_j\cdot\mathrm{depth}(i))\\ &=(f_i-f_j)(\mathrm{depth}(i)-\mathrm{depth}(j))\\ &>0 \end{aligned}$$

so we can always swap the two nodes and (original) $f_i\cdot\mathrm{depth}(i)+f_j\cdot\mathrm{depth}(j)>f_i\cdot\mathrm{depth}(j)+f_j\cdot\mathrm{depth}(i)$ (after). so lowest frequency symbols should appear at leaves. $\square$

algo:

1. if |S|=2, encode one symbol using 0 and the other using 1, and return tree

         R
    0 /    \ 1
    s1      s2
   

2. otherwise let y, z be two symbols with lowest frequencies.
3. delete y and z from S. add new pseudo symbol w with frequency $f_y+f_z$
4. solve this reduced problem (n-1 symbols) recursively and get a tree T'
5. in T', look at the leaf associated with w, add two leaves to it (so that w becomes an internal node) and associate y and z with two new leaves.

(see cs240 - how are they different?)

correctness: use induction. base case is if there are 2 symbols, correct. if there are more than 2 symbols and our T' is optimal, for the new tree T after adding two symbols, $\mathrm{obj}(T)=\mathrm{obj}(T')-f_w\cdot\mathrm{depth}(w)+f_y\cdot(\mathrm{depth}(w)+1)+f_z\cdot(\mathrm{depth}(z)+1)=\mathrm{obj}(T')+(-f_w+f_y+f_y)\cdot\mathrm{depth}(w)+f_y+f_z=\mathrm{obj}(T')+f_y+f_z$. we want to show any other tree will have obj >= this.
suppose an optimal solution is $T^*$. remove y and z from $T^*$ we have $T^*{}'$ is a feasible solution to the reduced problem. since $T'$ is optimal, we have $$\mathrm{obj}(T')\le \mathrm{obj}(T^*{}')$$. using same calculation we have $\mathrm{obj}(T^*)=\mathrm{obj}(T^*{}')+f_y+f_z$ (1). so we have $\mathrm{obj}(T^*)\ge\mathrm{obj}(T')+f_y+f_z=\mathrm{obj}(T)$. $\square$

(1) how can you use same calculation T* might not have w? use the y & z's common parent because they are sibling.

runtime: O(nlogn) (use heap for get min)

single source shortest path

given a directed graph G=(V,E), a non-negative length $l_e$ for each edge $e\in E$, and two vertices $s\in V$. find a shortest path from s to v for every vertex $v\in V$.

using reduction:

• we can reduce graph in to new graph G' but with length 1 -> break each edge into $l_e$ edges.
• if we follow the path G' we have path in G. use bfs
• runtime: will be proportional to the length of edges - slow

we want to simulate this process, but don't want to follow broken edges step by step. we keep track of an upper bound on the time a vertex to be found.

            5         1
      f <------- s ------> g
                 | 2
                 b

• starting from s, suppose sf has length 5, sg has length 1. we set f has bound 5
• when we move out, we reach g (bound set to 0), and f's bound is set to 4

algo (dijkstra):

dijkstra(G, s):
    auto parents = {}
    auto dist = {v: ∞ for v in G.V}
    auto Q = new priority_queue
    dist[s] = 0

    for v, bound in dist:
        Q.insert(v, key=bound)

    while Q is not empty:
        auto u = Q.delete_min()
        for each out_v in u:
            auto l = /*length of uv*/
            if dist[u] + l < dist[out_v]:
                dist[out_v] = dist[u] + l
                Q.set_key(out_v, dist[out_v])  // "decrease_key()"
                parents[out_v] = u  // may be set multiple times

    return ...

runtime:

• each vertex is enqueued once (beginning), dequeued once (in loop)
• heap operations all take O(logn)
  • make heap at beginning, then delete_max and heapify for each vertex
• total: $O(n\log n+\sum_v\mathrm{deg}(v)\log n)=O((n+m)\log n)$
• fibonacci heap: O(n +mlogn)

puzzle. do not trust this; there are better formations than it

Instead of filling the priority queue with all nodes in the initialization phase, it is also possible to initialize it to contain only source; then, inside the if dist[u] + l < dist[out_v] block, the decrease_priority() becomes an add_with_priority() operation if the node is not already in the queue.

single source shortest path (2)

idea:

• grow a subset $R\subseteq V$ so that dist[v] is computed correctly
• initially, R={s} and we add more in each iteration
  • add the vertex closest to R

algo:

1. let dist = {v: ∞ for v in G.V}, dist[s] = 0, R = ∅
2. while R != G.V:
   1. pick the vertex u $\notin$ R with smallest dist[u]
   2. R = R U {u}
   3. for each edge uv in neighbors of u:
      1. if dist[u] + $l_{uv}$ < dist[v]:
         1. dist[u] = dist[v] + $l_{uv}$

• same implementation as above

correctness: we want to show the following invariant holds: for any v in R, dist[v] is the shortest path distance from s to v.
proceed by induction. base case R={s}, then dist[s] = 0 is shortest. inductive: suppose R is computed correctly, now we have u, we want to show the shortest path from s to u is dist[v] + $l_{vu}$.

• since dist[v] is computed correctly, plus this edge, we have an upper bound of this distance: dist[u] <= dist[v] + $l_{vu}$.
• consider any path p from s to u, and passes some intermediate edges xy,... x is in R, and y is not in R. since dist[] is computed correctly for v, it will take longer than using $l_{vu}$. so length(p) >= dist[v] + $l_{xy}$ + ... >= dist[v] + $l_{vu}$. $\square$

shortest path tree:

• (v, parent[v]) form a tree
• we have succinct way to store all shortest paths from s using n-1 edges

remark. algo breaks when length is negative. it fails at the ... in the proof.

Week 7. June 23

dynamic programming

on a high level, we can solve a problem by dynamic programming if there is a recurrence relation with only a polynomial number of subproblems.

eg. how to compute $F(n)=F(n-1)+F(n-2),F(1)=F(1)=1$? we compute the same term too many times and the run time is O(1.618^n).

• top-down memorization: we can use a visited[] array to ensure each subproblem is computed at most once, and also use array answer[] is store the value of F(i) for future lookup.

  F(i):
      if visited[i]:
          return answer[i]
      if i == 0 or i == 1:
          return 1
      answer[i] = F(i - 1) + F(i - 2)
      visited[i] = true
      return answer[i]
  

  because of the visited array, each subproblem is computed at most once. there are n subproblems, so O(n) additions.
• bottom-up computation: compute F(0) and F(1) first, then we can compute F(i) that depend on eariler F(i)'s. runtime is O(n) additions.

  F(N):
      auto F0, F1 = 1, 1
      for i = 2, N:
          F0, F1 = F1, F0 + F1
      return F1
  

• note runtime can be O(n^2) as the number gets big and we do not assume addition is constant!

in principle, to come up with bottom-up implementation, we just need to use a topological ordering of the 'subproblem dependency graph' to have correct order to solve subproblems.

weighted interval scheduling

given n intervals $([s_i,f_i])_{i=1}^n$ and a weight $w_i$ for each interval i. find a subset of disjoint intervals that maximizes the total weight.

1      3        6       10
----   -------  ------  ----
 ----    -- --    8 -----
 2       4  5       9 ---
                7 ----- ------- 11

• exhaustive search: sort by start time, we can either pick the first interval or not. in each of the subproblem, we decide whether to pick the next available one. runtime is exponential.

note if we already pick 1 and 3 and wish to extend this solution. this is solves the same problem as having picked 2 and 3 - what really matters is the last interval of the current partial solution.

we use a good ordering of the intervals and precompute some useful info.

• we sort the intervals be starting time in non-decreasing order
• for each interval i, define next(i) to be the smallest j such that j > i and $s_j>f_i$ (happens after i). next(i) = n+1 if no such j exists. then

  next(1) = 6   next(4) = 9
  next(2) = 4   next(5) = 8
  next(3) = 5   next(6) = 7
  

• property. for interval i, intervals in {i+1,..., next(i)-1} overlap with i, and intervals in {next(i), ..., n} do not overlap with i,
• let D(i) be the maximum total weight of disjoint intervals using intervals {i,..., n} only.
• when facing the i-th interval, we can
  • choose to pick it, we can only choose intervals {next(i), ...}
  • choose to not pick it, we can choose intervals {i+1, ...}
• recurrence: $D(i) = \max\{ w_i + D(\mathrm{next}[i]), D(i+1) \}$
• base case: D(n+1) = 0
• answer is D(1)

runtime (top-down):

• sorting O(nlogn)
• compute next[], use binary search O(nlogn)
• n subproblems, for each we look up two values => O(n)
• total: O(nlogn)

we can use bottom-up computation too, from n to 1.

puzzle. how to print the intervals? (linked list to maintain linear time)

subset sum

given n positives integers $(a_i)_{i=1}^n$ and an integer K. find a subset $S\subseteq[n]$ with $\sum_{i\in S}a_i=K$ or report no such subset exists.

a[1] = 3, a[2] = 2, a[3] = 7, a[4] = 8, ...

• exhaustive: when seeing one number, decide wether it select it => enumerate all possibilities O(2^n)

note after picking a[1] and a[3], we solve the similar subproblem as having picked a[2] and a[4].

• the subproblem is D[i][L] = true iff there is a subset in {i,..., n} whose sum is L, where i<=i<=n, i<=L<=K.
• when facing a[i]
  • if we choose a[i], then return true if D[i+1][L-a[i]]
  • if we do not choose a[i], then return true if D[i+1][L]
• recurrence: D[i][L] = D[i + 1][L - a[i]] or D[i + 1][L]
• base case:
  • D[i][0] = true for all i
  • D[i][L] = false if i > n
  • D[i][L] = false if L < 0
• answer is D[1][K]

bottom-up:

for i = 1, n:
    for L = 0, K:
        D[i][L] = false

D[n][a[n]] = D[n][0] = true

for i = 1, n:
    D[i][0] = true

for i = n, 1, -1:
    for L = 1, K:
        D[i][L] ||= D[i + 1][L]
        if L - a[i] >= 0:
            D[i][L] ||= D[i + 1][l - a[i]]

return D[1][K]

runtime: nK subproblems, in each subproblem, look up two values => O(nK) (pseudo polynomial).

remark. if decision problem, we can keep only two rows. space complexity becomes O(K) instead of O(nK).

remark. if using top-down, we do not necessarily compute all subproblems unlike bottom-up.

• take an element first may speed up

remark. D[1][K] is true iff there exists a directed path from (1, K) to some nodes with 'true' base case.

• how to print a solution? keep a parent array we can know at which step, we take number or not take
• or just look at the created table and trace which subproblem is true

knapsack

given n items, each of weight $w_i$ and value $v_i$, and a positive integer W. find a subset $S\subseteq[n]$ such that $\sum_{i\in S}w_i\le W$ that maximizes $\sum_{i\in S}v_i$.

approach 1:

• D[i][w][v] = true iff there is a subset in {i, ..., n} with total weight w and total value v
• recurrence: D[i][w][v] = D[i + 1][w][v] or D[i + 1][w - w[i]][v - a[i]]
• base case:
  • D[i][0][0] = true for all i
  • D[n+1][w][v] = false for all w !=0 and v != 0
• answer is max{ v: D[i][w][v] = true and w <= W }

runtime: $O(nW\cdot\sum_{i}a_i)$.

approach 2:

• D[i][w] = maximum value of a subset in {i, ..., n} with total weight at most w
• recurrence: D[i][w] = max{ D[i + 1][w], a[i] + D[i + 1][w - w[i]] }
• base case:
  • D[n+1][w] = 0 for all w >= 0
  • D[i][w] = -inf for all w < 0 (illegal)
• answer is D[1][w]

runtime: O(nW)

longest increasing subsequence

given n numbers $(a_i)_{i=1}^n$, a subsequence is a subset $a_{i_1},...,a_{i_k}$ with $i_1<...<i_k$. a subsequence is increasing if $a_{i_1}<...<a_{i_k}$. find an increasing subsequence of maximum length.

[5, 1, 9, 8, 8, 8, 4, 5, 6, 7] => 1 4 5 6 7

• let L[i] be the length of a longest increasing subsequence starting at a[i] and using numbers from {1[i], ..., a[n]} only.
• at step i, find the next number greater than it (O(n) to find)
• recurrence: L[i] = 1 + max{ L[j]: a[j] > a[i] and i+1 <= j <= n }
• base case: L[n] = 1 (take only one number)
• answer is max(L)

runtime: O(n^2)

how to print the sequences?

i | 1  2  3  4  5  6  7   8   9
--+-----------------------------
a | 3  8  7  2  6  4  12  14  9
L | 4  3  3  4  3  3  2   1   1
    ^  ^              ^   ^

we know answer is of length 4. trace L from 4 to 1.

or use parent array.

remark. if runtime == # of subproblems, then algo is likely to be optimal. otherwise there might be better algo.

Week 8. June 30

longest increasing subsequence (2)

idea:

• use same recurrence
• for each length k, we only store the best position to start an increasing subsequence of length k
  • eg when computing L[7], we can throw away i=9 because anything greater than a[8]=14 is greater than a[9]=9
• then these 'best subproblems' satisfy monotone property - we can use binary search to locate next number greater than current, and skip everything in between

define $\mathrm{pos}[k]=\max_{j>i}\{a_j:L(j)=k\}$ to be the best position to extend a subsequence of length k, and let $m=\max_{i+1\leq j\leq n}L(j)$ be the length of a longest increasing subsequence we computed so far. then we only need L(pos[1]), ..., L(pos[m]) for future computations.

i | 1  2  3  4  5  6  7  8
--+------------------------
a | 2  7  6  1  4  8  5  3
L | 3  2  2  3  2  1  1  1
    ^  ^           ^
pos[1] = 6, pos[2] = 2, pos[3] = 1

claim. (monotone) a[pos[1]] > ... > a[pos[m]]: it is harder to extend a longer increasing subsequence than a shorter one.
proof. suppose by contradiction there exists j such that a[pos[j]] >= a[pos[j-1]]. assume we have the longest increasing subsequence $a_{i_1}$=a[pos[j]] < $a_{i_2}<...<a_{i_j}$ of length j. then $a_{i_2}$ will be a position to start such a subsequence of length j-1. we have $a_{i_2}$ > a[pos[j]] >= a[pos[j-1]], which is a contradiction because $i_2$ would be a better place to start subsequence of length j-1. $\square$

algo:

auto m = 1  // length
pos[1] = n // base
for i = n-1, 1, -1:
    if a[i] < a[pos[m]]:
        ++m
        pos[m] = i
    else:
        use binary search to find smallest j st a[pos[j]] <= a[i] // < a[pos[j-1]]
        pos[j] = i
return m

runtime: O(nlogn)

longest common subsequence

given two strings $a_1a_2...a_n$ and $b_1b_2...b_m$, find the largest k such that there exist $i_1<...<i_k,j_1<...<j_k$ and $a_{i_l}=b_{j_l}$ for $1\leq l\leq k$.

longest increasing subsequence is a special case of this problem, where the second array is the sorted version.

       ___     _
S1 = 3 1 2 8 9 7
     ___   _
S2 = 1 2 3 7 8 9

answer = 1 2 7

let C[i][j] be the length of a longest common subsequence of a[i]...a[n] and b[j]...b[m].

• when we scan a[i] and b[j]:
  1. do we match?
     • if a[i] == b[j], we include this in the subsequence: sol1 = 1 + C[i + 1][j + 1]

       a[i]   a a a a a a
        ||
       b[j]   b b b b b b
       

     • else: sol1 = 0
  2. we can just stay at a[i] and skip b[j]: sol2 = c[i][j + 1]

        a[i]   a a a a a a
     x  b      b b b b b
     

  3. we can just stay at b[j] and skip a[i]: sol3 = c[i + 1][j]
• recurrence: C[i][j] = max{ sol1, sol2, sol3 }
• base case:
  • C[n + 1][j] = 0 for all j
  • C[i][m + 1] = 0 for all i
• answer is a[1][1]

runtime: there are O(nm) subproblems, each takes constant time => total O(nm).

bottom-up: count i from n to 1, and count j from n to 1.

edit distance

given two strings $a_1a_2...a_n$ and $b_1b_2...b_m$, find the minimum k such that we can do k add/delete/change operations to transform $a_1a_2...a_n$ to $b_1b_2...b_m$.

let D[i][j] be the edit distance of a[i]...a[n] and b[j]...b[m].

• when we scan a[i] and b[j]:
  1. do we match?
     • if i <= n and j <= n and a[i] == b[j]: sol1 = D[i + 1][j + 1]
     • else: sol1 = inf
  2. consider ADD a matching symbol to a, we match the rest of b:
     • if j <= m: sol2 = 1 + D[i][j + 1]
     • else: sol2 = inf
  3. consider DELETE current symbol in a, we match the rest of a:
     • if i <= n: sol3 = 1 + D[i + 1][j]
     • else: sol3 = inf
  4. consider CHANGE current symbol in a to a matching one, we match rest of both:
     • if i <= m and j <= n: sol4 = 1 + D[i + 1][j + 1]
     • else: sol4 = inf
• recurrence: D[i][j] = min{ sol1, sol2, sol3, sol4 }
• base case: D[n + 1][m + 1] = 0
• answer is D[1][1]

runtime: O(nm).

bottom-up: dependency points bottom-right. we only have one corner base case, fill in the bottom row and rightmost column first.

puzzle. given DAG, what is length of longest path from s to t? order V by topo, let d[i] be the length of longest path from s to i, then d[i] = i == s ? 0 : max { d[j]: j and i and neighbors } + 1, answer is d[t].

Week 9. July 7

maximum independent sets on trees

defn. given a graph G=(V, E), a subset of vertices $S\subseteq V$ is an independent set if $uv\notin E$ for all $u,v\in S$.

given a tree T=(V,E), find an independent set of maximum cardinality.

A -- B -- C -- D
sol: A and C, or A and D, or B and D. size 2.

we define subproblem as I[v] be the size of a maximum independent set in the subtree rooted at vertex v.

• suppose we are at node v
  • we include v in the answer, then we should skip its children and take grand children: size1 = $1+\sum_{w:\pi(\pi(w))=v}I(w)$
  • we do not include v, then we take children: size2 = $\sum_{w:\pi(w)=v}I(w)$
• recurrence: max{size1, size2}
• base case: O[v] = 1 for all leaves v
• answer I[root]

runtime: there are n subproblems. in total, we look at $\sum_v({\text{\#children of }v +\text{ \# grandchildren of }v})$ vertices. this is the same as $\sum_v({\text{\#parent of }v +\text{ \# grandparent of }v})=\sum_v2=2n$.

puzzle. how to solve max weighted independent set problem?

maximum independent sets on trees (2)

• now define subproblem as J(v) be size of a maximum independent set with v included
• define M(v) be size of a maximum independent set with v excluded.
• recurrence:
  • $J(v)=1+\sum_{w:\pi(w)=v}M(w)$
  • $M(v)=\sum_{w:\pi(w)=v}\max\{J(w),M(w)\}$
• base case: J[v] = 1, M[v] = 0 for every leaf v
• answer: max{ J[root], M[root] }

runtime: $O(\sum_v\mathrm{deg}(v))=O(m+n)=O(n)$.

optimal binary search tree

given n keys $k_1<...<k_n$ and non-negative frequencies $\sum_{i}^nf_i=1$. find a binary search tree T that minimizes $\sum_{i=1}^nf_i\cdot\mathrm{depth}_T(i)$.

note optimal solution does not necessarily require key with highest frequency at the top - have to respect bst structure.

let C[i][j] be the objective value of an optimal bst with keys $k_i<...<k_j$.

• for each range i to j, we try all values as root, put smaller keys on left subtree, put greater keys on right subtree. see which arrangement has smallest obj
• recurrence: $C_{i,j}=\min_{i\leq l\leq j}\{f_l+(C_{i,l-1}+\sum_{k=1}^{l-1}f_k)+(C_{l+1,j}+\sum_{k=l+1}^jf_k)\}=\sum_{k=i}^jf_k+\min_{i\leq l\leq j}\{C_{i,l-1}+C_{l+1,j}\}$
• base case: C[i][i] = f[i], C[i][i-1] = 0 for all i
• answer: C[1][n]

runtime: n^2 subproblems, for each we take O(n) possibilities. total: O(n^3).

bottom-up: compute smaller width (j-i) first then larger subproblems.

better: Knuth's O(n^2).

shortest paths with negative edges

given a directed graph G=(V,E), a length $l_e$ for each edge $e\in E$, and two vertices $s\in V$. find a shortest path from s to v for every vertex $v\in V$, assuming no negative cycles exist.

what is wrong with dijkstra's: if we suddenly find a negative edge that decreases the distance to a visited vertex m, then all vertices that are reached by m have to be updated.

    1        5
s -----> a -----> b -----> c
|        ^
v        | -1000
g -----> h
   100

if there are no negative edges, after deciding sa and dropping sg, we instantly know sa is
shortest to reach a. however, if negative edges exist, we cannot drop sg as ah makes it smaller.

update a, b and c!

negative cycles: shortest path distance is not well-defined if a cycles consisting of negative edges appear in the middle of path.

             -1
s -----> a -----> b ------> t
      -1 |       ^
         v  -1   | -1
         c ------+

we can keep walking in the cycle - the dist is not bounded below

idea: dijkstra will compute distance to some vertices correctly eg. first vertex on a path

• no negative cycles => shortest path is a simple path => shortest path has at most n-1 edge => at most n-1 iterations

let D[v][i] be the shortest path distance from s to v using at most i edges.

• recurrence: $D_{v,i+1}=\min\{D_{v,i},\min_{u:uv\in E}D_{u,i}+L_{uv}\}$
• base case:
  • D[s][0] = 0
  • D[v][0] = inf for all v except s
• answer: D[v][n-1]

runtime:

• at each step, finding min path from in-neighbor needs to check $\mathrm{indeg}(w)$ vertices
  • total: $O(\sum_w\mathrm{indeg}(w))=O(m)$
• at most n iterations => total O(mn)

space: O(n^2) (O(n) if just want distance, only keep D[v][i+1] and D[v][i])

algo (bellman-ford):

• idea: keep a tighter upper bound on shortest path distance

dist[s] = 0
for v in V - {s}:
    dist[v] = inf

for i = 1, n-1:
    for each edge uv in E:
        if dist[u] + L[uv] < dist[v]:  // relaxation step
            dist[v] = dist[u] + L[uv]
            parent[v] = u

lemma. if there is a directed cycle C in the edges (parent[v], v), then C must be a negative cycle.
proof. assume there is a directed cycle $v_1v_2...v_kv_1$ where the final edge is $v_kv_1$ (parent of $v_1$ is $v_k$). then for $2\leq i\leq k$, the for loop tells us $\mathrm{dist}[v_i] \geq \mathrm{dist}[v_{i-1}] + l_{v_{i-1}v_i}$. if we added the edge $v_kv_1$, we also have $\mathrm{dist}[v_1] > \mathrm{dist}[v_k] + l_{v_kv_1}$. adding the inequalities we get $\sum_{j=1}^k\mathrm{dist}[v_j]>\sum_{j=1}^k\textrm{dist}[v_j]+\sum_{e\text{ in cycle}}l_e\Rightarrow 0>\sum_{e\text{ in cycle}}l_e$, which only happens for negative cycles. $\square$

negative cycles

given a directed graph G=(V,E), a length $l_e$ for each edge $e\in E$. find a negative cycle.

note D[v][i] is computed correctly even though graph can have negative cycles (we only used such assumption in last question for computing stopping condition).

idea:

1. assume every vertex can be reached from vertex s (otherwise do it in every component)
2. if there is no egative cycles, D[v][k] is finite for all v as k -> ∞
3. if there is, D[v][k] tends to -∞

claim. D[v][n] = D[v][n - 1] for all $v\in V$ iff G has no negative cycles.
proof.

• forward: by recurrence, $D_{v,n+1}=\min\{D_{v,n},\min_{u:uv\in E}D_{u,n}+L_{uv}\}=\min\{D_{v,n-1},\min_{u:uv\in E}D_{u,n-1}+L_{uv}\}=D_{v,n}$. by induction we have $D_{v,k}=D_{v,n-1}$ for all v and all $k\geq n-1$, hence $D_{v,k}$ is finite and there is no negative cycle.
• backward: there is no negative edge => shortest path is simple, we at most n-1 edges, and using an extra edge does not reduce the dist. $\square$

remark. early termination rules is D[v][k+1] = D[v][k] for all v.

hence for checking, using the above claim we can do bellman-ford with an extra iteration step.

claim. if D[v][n] < D[v][n - 1] for some v, then in the walk (by tracing parent) between two repeated vertices we find a negative cycle.
proof. then we know the shortest path using at most n edges to get to v must have exactly n edges (otherwise D[v][n] = D[v][n-1]). so there is at least one repeated vertex, meaning there is a cycle in the walk. we suppose otherwise that this cycle is not negative, then D[v][n-1] <= length(W') <= length(W) = D[v][n], where W' is done by using n-1 edges and W is done using n edges. this is a contradiction. $\square$

all-pairs shortest paths

given a directed graph G=(V,E), a length $l_e$ for each edge $e\in E$. find shortest path distances from s to t for all $s,t\in V$. assume no negative cycles exist.

naive: use bellman-ford for all s. time is O(nm*n) (account for # edges!).

define D[i][j][k] to be the shortest path distance from $v_i$ to $v_j$ using $\{v_1,...,v_k\}$ as intermediate vertices.

• do we want to use an extra intermediate node?

                          +--> k+1 --+
                          ^          | using {v[1], ..., v[k]}
  using {v[1], ..., v[k]} |          v
                          i ---------> j
  

• recurrence: d[i][j][k] = min{ D[i][j][k], D[i][k+1][k] + D[k+1][j][k] }
• base cases:
  • D[i][j][0] = l[ij] for all edges $v_iv_j$
  • D[i][j][0] = inf for all $v_iv_j\notin E$
• answer: D[i][j][n] for all i, j

algo (floyd-warshall):

D[i][j][0] = inf
for all edge v[i]v[j] in E:
    D[i][j][0] = l[ij]

for k = 1, n:
    for i = 1, n:
        for j = 1, n:
            d[i][j][k] = min(D[i][j][k], D[i][k+1][k] + D[k+1][j][k])

runtime: O(n^3)

puzzle. reduce one dimension of D by using adj matrix?

traveling salesman

given a directed graph G=(V,E), a length $l_e$ for each edge $e\in E$. find a directed cycle C that visits every vertex exactly once that minimizes $\sum_{e\in C}l_e$.

naive: try every combination of vertices and compute weights (O(n!)n).

define C[i][S] to be the shortest path distance from 1 to $v_i$ with vertex set $S\subseteq V$ on the path.

• suppose we computed C[i][S] for all |S|<=k and last vertex is $v_i$
  • want to compute C[i][S] for |S|=k+1, try all possible second last vertex of the path
• $C_{i,S}=\min_{j\in S-\{v_1,v_i\}}\{C_{v_j,S-\{v_i\}}+l_{v_jv_i}\}$
• base case: $C_{i, \{v_1,v_i\}=l_{v_1v_i}}$ for all i
• answer: $\min_{1\leq i\leq n}\{C_{v_i,V}+l_{v_iv_1}\}$

runtime:

• subproblems: all possible subset of V and times n: $O(2^nn)$ subproblems
• total: $O(2^nn^2)$
• disadvantage: space $\Theta(2^nn)$
  • there is clever way to reduce space to poly

Week 10. July 14

bipartite matching

defn. a subset of edges $M\subseteq E$ is a matching if edges in M are pairwise vertex disjoint.

defn. given matching M, a vertex v is matched if v is the endpoint of some edge $e\in M$, otherwise v is unmatched/free.

defn. a matching M is a perfect matching if every vertex is matched in M.

bipartite matching

given a bipartite graph G=(X,Y;E), find a maximum cardinality subset of edges that are vertex disjoint.

defn. a path $v_1v_2...v_{2k}$ is an augmenting path with respect to a matching M if

• $v_1,v_{2k}$ are free
• $v_{2i-1}v_{2i}\notin M,1\leq i\leq k$ (odd edges not in matching)
• $v_{2i}v_{2i+1}\in M,1\leq i\leq k-1$ (even edges in matching)