06 April 2018

This is an incomplete solution to a very interesting problem set regarding cute algorithm problems. If you have (better) ideas about these problems or you find any mistake here, you can discuss with me by issue on github.

## Useful Resources

https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures.php

## 1. Longest path in a DAG

### Description

We are given a directed acyclic graph G and two specific vertices s and t in G. Each edge in the graph has a length. Design a polynomial time algorithm that finds the longest path from s to t. (if there is no path from s to t, your algorithm should be able to detect the fact.)

### Solution (DP on graph)

(V, E) = sort G in topological order

for each node x in V:
x.dist = -inf
x.pred = null

ind_s = index of s in V
V[ind_x].dist = 0

for each node x in V[ind_x:]:
for each edge e = (y, x) in E:
if (x.dist < y.dist + e.weight):
x.dist = y.dist + e.weight
x.pred = y

ind_t = index of t in V
if V[ind_t].dist > 0:
return V[ind_t].dist, path tracked by V[ind_t].pred
else:
return no-path-from-s-to-t

Theorem: Topological order can be found in any DAG in linear time $O(|V|)$, e.g. remove node with no incoming edge repeatedly from V.

## 2. Finding the maximum area polygon

### Description

We are given a unit circle and n points on the circle. Design a polynomial time algorithm that, given a number m < n, finds m points (out of n points) such that the area of the polygon formed by the m points is maximized.

### Solution (DP)

Points are labeled 1, 2, …, n. A[j, k] is the maximum area if we choose k points among points 1, 2, …, j, where point 1 and j are chosen and fixed.

We have

Where $S(x, y, z)$ are the area of the triangle whose vertices are x, y and z. Initially we have $A[i, 2] = 0, \, \forall 2\le i \le n$.

In case point 1 is not necessarily be chosen, we have to repeat this process $n-m+1$ times chosing different starting points.

Complexity $O((n-m)n^2)$

## 3. Longest palindrome subsequence

### Description

A palindrome is a nonempty string over some alphabet that reads the same forward and backward. For example, aaaabaaaa, 00000, abcddcba are all palindrome. Give an efficient algorithm to find the longest palindrome that is a subsequence of a given input string. Your algorithm should run in time better than $O(n^3)$.

### Solution (DP)

Define $A[i,j]$ as the length of longest palindrome subsequence in substring $[i,j]$.

We have

if x[i] == x[j]:
A[i, j] = A[i+1, j-1] + 2
else:
A[i, j] = max(A[i+1, j], A[i, j-1])

Notice: pay attention to the definition of subsequence. e.g. ‘ale’ is subsequence of ‘apple’.

## 4. Matrix-chain multiplication

### Description

We state the matrix-chain multiplication problem as follows:

given a chain of matrices $A_1 A_2 \cdots A_n$, where $A_i$ has dimension $p_{i−1} \times p_i$. (Note that the number of columns of $A_i$ must be the same as the number of rows of $A_{i+1}$.) Assume multiplying a $x\times y$ matrix with a $y\times z$ matrix takes $xyz$ scalar multiplications. Design a polynomial time algorithm to find a fully parenthesization of the product $A_1 A_2 \cdots A_n$ in a way that minimizes the number of scalar multiplications.

For example, consider $A_1A_2A_3$ of three matrices with the dimensions of 10 × 100, 100 × 5, and 5 × 50, respectively. If we multiply according to the parenthesization $((A_1A_2)A_3)$, we perform 5000 + 2500 = 7500 scalar multiplications. However, if instead we multiply according to the $A_1(A_2A_3)$, we perform 25000 + 50000 = 75000 scalar multiplications. Clearly, the first one is much better.

### Solution (DP)

Define $A[i, j]$ as the minimum number of scalar multiplications from $p_i$ to $p_j$. Each $A[i, j]$ corresponds to a parenthesization plan from $A_{i+1}$ to $A_j$.

We have

if j - i <= 2:
A[i, j] = min(A[i+1, j] + p[i] * p[i+1] * p[j], A[i, j-1] + p[i] * p[j-1] * p[j])
elif j - i == 2:
A[i,j] = p[i] * p[i+1] * p[j]

## 5. Viterbi algorithm

### Description

We can use dynamic programming on a directed graph $G(V; E)$ for speech recognition. Each edge $(u, v) \in E$ is labeled with a sound from a finite set $\Sigma$ of sounds. The labeled graph is a formal model of a person speaking a restricted language. Each path in the graph starting from a distinguished vertex $v_0 \in V$ corresponds to a possible sequence of sounds produced by the model. We define the label of a directed path to be the concatenation of the labels of the edges on that path.

1. Describe a polynomial time algorithm that, given an edge-labeled graph G with distinguished vertex $v_0$ and a sequence $s = \langle \sigma_1, \cdots, \sigma_k \rangle$ of sounds from $\Sigma$, returns a path in $G$ that begins at $v_0$ and has $s$ as its label, if any such path exists. Otherwise, the algorithm should return NO-SUCH-PATH.

2. Now, suppose that every edge $(u,v)$ has an associated nonnegative probability $p(u,v)$ of traversing the edge. And thus producing the corresponding sound. The sum of the probabilities of the edges leaving any vertex equals 1. The probability of a path is defined to be the product of the probabilities of its edges. We can view the probability of a path beginning at $v_0$ as the probability that a random walk beginning at $v_0$ will follow the specified path, where we randomly choose which edge to take leaving a vertex $u$ according to the probabilities of the available edges leaving $u$. Extend your answer to part 1 so that if a path is returned, it is a most probable path starting at $v_0$ and having label $s$. Analyze the running time of your algorithm.

### Solution (DP)

(1)

Define $T[i,m]$ as the feasibility of sequence $\langle \sigma_1, \cdots, \sigma_m \rangle$ with node $v_i$ labeling $\sigma_m$. If it is feasible, $T[i,m] = 1$, else, $T[i,m] = 0$.

We have

where $S(G, i, m) = {j | v_j \in V, (v_j, v_i) \in E, label[(v_j, v_i)] = \sigma_m }$, if $S(G, i, m) = \emptyset$, the term is zero.

Initially set $T[\cdot, 1] = 0$ and $\forall v_i \in V,\, (v_0, v_i) \in E,\, label[(v_0, v_i)] = \sigma_1$, we set $T[i, 1] = 1$. At last if $\exists v_i \in V, \, s.t. T[i, k] = 1$, we can return a sequence traced back from a record of the corresponding $arg\max$. If there does not exist such a node, return NO-SUCH-PATH.

The equation are evaluated m times, in each time at most |V| points are tested. Thus, $O(m|V|)$. If we use adjacency list instead of adjacency matrix, tighter bound may be obtained, I guess.

(2)

This time it is the common form of Viterbi algorithm. Use $T[i, m]$ to represent the probability of observing sequence $\langle \sigma_1, \cdots, \sigma_m \rangle$ with node $v_i$ labeling $\sigma_m$. Use $P[i, m]$ to record the corresponding $j$ chosen by $T[i, m]$, $s.t. v_j = \sigma_{m-1}$.

Define transition matrix $A\in \mathbb{R}^{|V|\times|V|}$ to record the traversing probability from nodes to nodes. i.e. $A[i,j] = p(v_i, v_j)$. Define emission matrix $B\in\mathbb{R}^{|V|\times|\Sigma|}$ to denote the label of each node. e.g. node $v_i$ is with label $\sigma_m$, thus $% $

(notations here a bit imprecise)

We have

$T[i,m] = \max\_j (T[j, m-1] \cdot A[j, i] \cdot B[j, m])$ $P[i,m] = arg\max\_j (T[j, m-1] \cdot A[j, i] \cdot B[j, m])$

Similarily, if $\exists v_i \in V ,\, T[i, k] > 0$ it is feasible and there exists a path. The path is given by tracing $P[i, m]$ back. Running time is at most $O(m|V|)$.

## 6. Edit distance

### Description

In order to transform one string x to a target string y, we can perform various edit operations. Our goal is, given x and y, to produce a series of edits that change x to y. We may choose from among edit operations:

1. Insert a letter, (e.g., changing 100 to 1001 takes one insertion)
2. Delete a letter, (e.g., changing 100 to 10 takes one deletion)
3. Replace a letter by another (e.g., you need do one replacement to change 100 to 000).

Design an efficient algorithm that finds a series of edit operations that change x to y and the total number of edits is minimized.

### Solution (DP)

Also a DP problem. Defind A[i,j] as the number of edit operation need to take to change x[1:i] to y[1:j].

We have

A[i, j] = min(
A[i-1, j] + 1,                           # delete
A[i, j-1] + 1,                           # insert
A[i-1, j-1] + I(x[i] != y[j])            # match or replace
)

where $I(\cdot)$ is indicator function. DP is running from $i+j = 2$ to len(x) + len(y).

## 7. Four Russians Speedup

### Description

In this problem, we explore an interesting trick to speed up a dynamic program. We use the edit distance problem as an example (See the last problem). We assume the size of the alphabet is constant. Suppose the two strings are $S_1$ and $S_2$, both of length $n$. To start with, your solution for the last problem must run in $O(n^2)$ time. If it is so, in the dynamic program for the problem, you need to fill a two dimensional table $M$. In fact, we can fill out this table in a more clever way such that the running time can be improved to $O(n^2/ \log n)$ (I know, it is a small improvement and of little practical interests for this particular problem. But the same trick has been used somewhere else to make a huge difference). In this trick, we need to a bit preprocessing to make many small tables. Then we fill only a subset of entries of the dynamic program table. The value of a table entry we are filling depends on the values of some entries we have already filled and the list we made in the beginning.

To make it a little bit more formal. We define a t-block to be a $t \times t$ squares in the dynamic programming table. Let $t = \dfrac{\log n}{4}$. We first observe that the distance values in a t-block starting in position $(i,j)$ are a function of the values of its first row and first colum and substrings $S_1[i,\cdots ,i+t−1]$ and $S_2[i,\cdots,i+t−1]$.

Now, let us observe another interesting fact: In any row or column, the values of two adjacent cells differ by at most 1.

We say two t-blocks $B_1$, $B_2$ are offset-equivalent if there is a number $c$, such that $B_1[i, j] = B_2[i, j]+c$ for all $i$, $j$.

• There are C types of t-blocks (up to offset-equivalence). Show how large C is.

It is obvious we can fill a t-block in $O(t^2)$ times. Therefore, filling all C types of blocks takes $O(Ct^2)$ times. These are the small tables we produce for preprocessing. How, we start to fill up the dynamic table $M$. We are going to fill up only $O(n^2/ \log n)$ entries.

• We have given you enough hints. Now, it is up to you to develop the entire algorithm which should run in $O(n^2/ \log n)$ time. In particular, you need to describe which entries of M that need to be filled and how to compute their values.

### Solution (DP optimization)

(0)

Draw grids on the big DP table and divide it into blocks. The objective is to obtain $M[n,n]$, which means we do not care the values within the table. We can compute the table block by block. Input for each block is 1) the upper left value A; 2) the first column B; 3) the first row C; 4) the corresponding $S_1[i, \cdots, i+t-1]$ and $S_2[i, \cdots, i+t-1]$. The output of the block is 1) the last column D; 2) the last row E; 3) the lower right value F.

We do the computation for all possible blocks in advance and use the result to fill the big DP table.

(1)

In any row or column, the values of two adjacent cells differ by at most 1. It is written as $M[i, j-1] - 1 \le M[i, j] \le M[i, j-1] + 1$.

The second part is easy to prove by the transition equation $M[i,j] = \min(M[i,j-1]+1, \cdots)$. For the first part, consider the value of $M[i,j]$ comes from the path M[i-k, j-1] -> M[i-k+1, j] -> M[i, j]. The first transition at least costs zero, and the second transition costs at least $k-1$. Thus, $M[i,j] \ge M[i-k, j-1] + (k-1)$. Considering another route M[i-k, j-1] -> M[i, j-1] costs at most $k$, we have $M[i-k] + k \ge M[i, j-1]$. Combining the two, we have $M[i, j-1] - 1 \le M[i, j]$.

(2)

Considering offset equivalence, different A does not incur different types of blocks. Considering the property in (1), the absolute values in B and C does not matter, and we can use incremental sequence to denote B and C, e.g. B=${+1, -1, +1, 0, -1, \cdots }$. Each of $S_1[i, \cdots, i+t-1]$ and $S_2[i, \cdots, i+t-1]$ has $|V|^t$ different possibilities.

Combined, we have $C = 3^t 3^t |V|^t |V|^t = 3^{2t}|V|^{2t}$

(3)

In the preprocessing step, we need to compute results for $C$ blocks. Each takes $O(t^2)$ time. Combined, we need $O[(3|V|)^{2t} t^2]$ time.

In the computation step, there are $O[(\dfrac{n}{t})^2]$ blocks should be fill in the large table. The input and output size of each block is $O(t)$, therefore we need $O(t)$ time to look for a block. Combined we need $O(\dfrac{n^2}{t})$ time.

By taking $t = \dfrac{\log_{3|V|} n}{2}$, the total running time $O[\dfrac{n^2}{t} + (3|V|)^{2t} t^2] = O(n^2 / \log n)$.

# do the preprocessing
for c in (all types of the block):
result = compute the result for the block c
B[c] = result

# do the computation
for i = 1 to ceil(n/t):
for j = 1 to ceil(n/t):
M[i+t-1, j+t-1], M[i+1:i+t-1, j+t-1], M[i+t-1, j+1:j+t-1] \
= B(M[i, j], M[i, j+1:j+t-1], M[i+1:i+t-1, j], incr(S1[i:i+t-1]), incr(S2[j:j+t-1]))

return M[n,n]

### Reference

• http://cs.au.dk/~cstorm/courses/AiBS_e12/slides/FourRussians.pdf

## 8. Solve the following two recurrences

### Description

(a) $T(n)=2T(\dfrac{n}{2})+n\log n$

(b) $T(n)=2T(\sqrt{n})+\log n$

### Methods

Methods to solve recurrences are

1. Guess and confirm (can be used in all cases): guess and replace to prove it’s true; unrolling to find the rule
2. Recurrence tree (solve $T(n) = aT(\frac{n}{b}) + f(n)$ like recurrences): $T(n) = \sum_{k=0}^L a^k f(\dfrac{n}{b^k})$
3. Master therem

Something useful:

• $\sum_{i=1}^n \dfrac{1}{i} = \Theta(\log n)$

### Solution

(a)

Use recurrence tree formula

(b)

By drawing the recurrence tree, we find the numbers of calculation on each layer are the same, $2^k \log(n^{\dfrac{1}{2^k}}) = \log n$. Easily we get, $T(n) = \Theta(\log n \log n)$

## 9. Maximal Common Subsequence

### Description

String C is a subsequence of string A if C can be obtained by deleting some letters from A. For example, ade is a substring of abcde. We are given two string $A = a_1a_2 \cdots a_m$ and $B = b_1b_2 \cdots b_n$. Design an algorithm that finds a common subsequence of A and B using $O(mn)$ time and $O(m + n)$ space. (You will get half of the points if you can find a polynomial time algorithm, but the running time (and/or) the space are worse that the stated.)

### Solution (DP and space optimization)

Define P[i, j] to be the length of longest common subsequence (LCS), Q[i,j] to trace the path of this LCS. A DP formula can be easily written as

This takes $O(mn)$ time and $O(mn)$ space. Further investigation shows that only the adjacent DP matrix is useful, thus we can have the following algorithm running in $O(mn)$ and using $O(m+n)$ space to obtain the length of LCS.

X = [0] * (m+n)
Y = [0] * (m+n)
Z = [0] * (m+n)

for i = 1 to n:
for j = 1 to m:
X[j] = max(Y[j], X[j-1], Y[j-1] + 1 * (A[i] == B[j]))
if i == floor(n/2):
Z[j] = which term is taken in the above max function
Y = X

Notice that we cannot trace what the LCS is. By Dan Hirschberg (1975), we can use another 1D array to note down one trace in the middle (the Z in the above) and find the crossing point k. Later solve recursively LCS(A[1:n/2], B[1:k]) and LCS(A[n/2+1:n], B[k+1:m]). Though much more computation to be done, running time is still $O(mn)$.

### Reference

• https://www.ics.uci.edu/~eppstein/161/960229.html

## 10. Stick Game

### Description

There is a pile of n sticks. Two players A and B take turns removing 1 or 4 sticks. A starts first. The players who removes the last stick wins. Design a polynomial time algorithm (polynomial in n) that decides which player has a winning strategy (i.e., no matter how the opponent plays, the player can take certain moves to win the game.)

### Solution (induction)

Just simply find patterns when n = 1, 2, 3, …

We found that when n = 5, 10, 15, …, A has no winning strategy, i.e. if B has a winning strategy. In other cases, A has winning strategy. We guess when n mod 5 == 0 B has winning strategy, otherwise A has winning strategy.

Next, we are going to prove it. When n mod 5 == 0, no matter how many sticks A removes, B can remove 1 to 4 sticks to make A face a number that can be devided by 5 again. At last, when n = 5, the number of sticks after A’s action is 1 to 4. B wins by remove all the remaining sticks. When n mod 5 != 0, on the other hand, A can always let B face the ‘dead’ numbers (numbers that can be devided by 5) and wins.

Thus

if n mod 5 == 0:
return B
else:
return A

which is an $O(1)$ algorithm.

## 11. Monge Matrix

### Solution (divide and conquer)

(a)

It can be proved by contradiction. Suppose there exists some $i < j$, s.t. $f(i)>f(j)$. Observe that A[i, f(j)] > A[i, f(i)] and A[j, f(i)] >= A[j, f(j)]. We have A[i, f(j)] + A[j, f(i)] > A[i, f(i)] + A[j, f(j)] and i<j and f(j) < f(i), which is a violation of property of the matrix.

(b)

A divide and conquer solution.

def find\_min(i, j, m, n):
""" returns [f(i), f(i+1), ..., f(j)] """
mid = floor((i + j) / 2)
f(mid) = argmin(A[mid, m:n])
return find\_min(i, mid-1, m, f(mid)) + [f(mid))] + find\_min(mid+1, j, f(mid), n)

We have recurrence T(m, n) = T(m/2, n1) + T(m/2, n - n1 + 1) + n - $O(n)$ on each level, with $O(\log m)$ levles. Considering at leat m entries should be written. We have $O(m + n \log m)$ running time.

### Description

We are given a set of unit-time tasks. Each task $i$ is supposed to finish by time $d_i$ ($d_i$ is an integer). Each task $i$ is also associated with a penalty $w_i$ if $i$ is not finished by time $d_i$. There is no penalty if we finish task $i$ by its deadline. Design a polynomial time that find a schedule that minimizes the total penalty.

### Methods

This belongs to a category of problems called Matroid. Matroid is a tuple $(S, I)$, where $S$ is a finite ground set, and $I$ is a family of independent subset of $S$, which has following properties

1. Hereditary property: $B\in I, A\subset B \Rightarrow A\in I$
2. Exchange property: $A\in I, B\in I, |A|<|B| \Rightarrow \exists x \in B-A, s.t. A\cup { x } \in I$

A Weighted Matriod Problem is a matroid where each element in $S$ assigned by a weight $w_i$ and the total weight of a independent subset of $S$ is maximized. This problem can be solved greedy algorithm.

Greedy(S, I, w):
A = {}
sort S decreasingly by w
for x in S:
if A + {x} in I:
A = A + {x}

Many greedy problems can be interpreted as matroid.

• minimum spanning tree: subset of edges to connect all vertices with minimum weight sum
• Kruskal algorithm greedily pick smallest weight
• interval scheduling: given start time, end time, find maximum compatible intervals
• greedily pick the task with earliest finish time that is compatible with the previous
• optimality proved by exchange argument
• interval partitioning: given start time, end time, find maximum of m/c to finish all the tasks
• greedily pick the task in order of increasing start time, if the task cannot be allocated, open a new m/c
• property: #m/c can never be less than maximum depth, depth is number of overlapping tasks at a given time
• schedule to minimize maximum lateness: earliest ddl first
• inversion: two adjacent jobs - latter one has earlier ddl
• swap on inversion does not increase lateness
• optimal has no idle time; there’s optimal strategy with no inversion
• earliest-ddl-first greedy is optimal
• optimal offline caching: farthest-in-future
• reduced schedule: only insert an item to cache when it is requested
• every strategy can transform to reduced version with no more eviction
• Huffman coding: merge from least frequent node
• 合并叶子节点为一个节点，节点的频率为叶子节点频率之和，这样做新树和旧树的代价只相差一个常数，因此具有意义的最优结构
• 通过把频率最小换到最深的位置，可以证明不增加总体代价，由此证明最优解中最小频率的两个节点一定是最深的兄弟

Methods used to prove optimal:

1. Show that after each step of the greedy algorithm, its solution is at least as good as any other algorithm’s.
2. Discover a simple “structural” bound asserting that every possible solution must have a certain value. Then show that your algorithm always achieves this bound.
3. Gradually transform any solution to the one found by the greedy algorithm without hurting its quality.
4. Show it is a matroid

### Solution (greedy)

$N_t(A)$ is the number of tasks in set A whose ddl is no later than t. If $N_t(A) \le t, \, \forall t$, A is a independent set, i.e. a set of tasks can be done with no penalty. $S$ to be the set of all tasks, $I$ to be the family of all independent subsets, it can be proved that $M=(S, I)$ is a matriod (by illustrating heredity and exchange property), and can be solved by a greedy algorithm.

Greedy(S, I, p):
A = {}
sort S decreasingly by penalty value p
for x in S:
if N(t, A + {x}) <= t for all t:
A = A + {x}

It is a $O(n^2)$ algorithm.

### Reference

https://www.cise.ufl.edu/class/cot5405sp11/slides/greedy_algo.pdf

## 13. Coin changing

### Description

Suppose that the coins are in the denominations that are powers of c, i.e., $c^0,c^1,c^2,\cdots ,c^k$, for some integers $c > 1$, $k \ge 1$. You are asked to change for n cents using the fewest number of coins. Show that the greedy algorithm yields an optimal solution. (The greedy algorithm first tries the coin with the largest denomination , then the coin with the second largest denomination, and so on).

### Method

Greedy-choice property:
If element x cannot be used immediately by GREEDY, it can never be used later.

### Solution (greedy proof)

Denote the solution followed by the greedy algorithm to be $a = (a_0, a_1, \cdots, a_k)$, where $a_i$ is the number of coins whose denomination is $c^i$. An optimal solution to be $b = (b_0, b_1, \cdots, b_k)$.

Firstly, we discover a property for optimal solution. $b_i \le c-1,\, \forall 0\le i \le k-1$. Otherwise, if there’s a $b_i \ge c$, we can change c $c^i$ coins to a $c^{i+1}$ coins without affacting others and decreasing the total number of coins. This contradicts the optimal assumption.

Next, consider the situation when remaining denomination x is faced. Suppose $c^j \le x < c^{j+1}$. We wanna show that an optimal solution must contain a $c^j$ coin. Suppose in optimal solution $b_j = 0$. Obviously, $b_i = 0, i > 0$, or the denomination of coins exceeds the required denomination. Given the previous property, the denomination this optimal solution can present $\sum_{i=0}^{j-1} b_i c^i \le \sum_{i=0}^{j-1} (c-1) c^i = c^j - 1 < c^j \le x$, which is not possible to be a valid solution. Thus, when $c^j \le x < c^{j+1}$ is faced, a $c^j$ coin must be contained in an optimal solution.

By induction, the greedy algorithm is proved to be correct every single step.

## 14. Schedule to minimize completion time

### Description

You are given a set $S = {a_1, a_2, \cdots , an}$ tasks. Task $a_i$ is released at time $r_i$ and requires $p_i$ units of time to process. You machine can process one task at each time. Assume preemption is allowed, so that you can suspend a task and resume it at a later time. For a particular schedule $S$, we denote the completion time of task $a_i$ to be $c_S(a_i)$. Give a polynomial time algorithm that finds a schedule $S$ of all tasks and minimizes the total completion time $\sum^n_{i=1} c_S(a_i)$.

### Solution (greedy)

# num of unit time since start
t = 0
r = p

i = None
rmin = inf
for j in tasks start before t:
if r[j] < rmin:
i = j
rmin = r[j]

t\_closest = closest start time of unfinished task

if i is None:
t = t\_closest
elif t + rmin < t\_closest:
r[i] = 0
t = t + rmin
else:
r[i] -= (t\_closest - t)
t = t\_closest

Running time: main loop either jump to a start time or finish a job, at most $O(n)$ runs. Finding shortest remaining time and find closest start time each takes $O(n)$. Thus $O(n^2)$.

I cannot prove it…. tell me (zhangchuheng123@qq.com) if you can.

## 15. Matching in graph

### Description

We are given an unweighted undirected graph G. Let $M$ be a matching in G that has no augmenting path of length smaller than $2t + 1$. Let $M^∗$ be the maximum matching in G. Show that $|M|\ge \dfrac{t}{t+1} |M^∗|$.

### Methods

• matching: 不共点的边集M
• matching number: 不共点边集的边的数量
• maximum matching: matching number最大的
• perfect matching: 能够覆盖所有点的
• M-alternating path: $G=(V, E)$中一条交替出现在$M$和$E\setminus M$中的路径
• M-augmenting path: 路径中两端没有被覆盖

### Reference

http://www-sop.inria.fr/members/Frederic.Havet/Cours/matching.pdf

## 16.

### Description

We are given n jobs and one server. Each job $j$ is associated with a profit $p_j$, a release time $r_j$ and completion time $c_j$. If we decide to schedule job $j$, the server has to process it continuously from time $r_j$ to $c_j$ and we can get a profit $p_j$. No partial profit can be obtained if the job is not finished. The server can process at most $k$ jobs at any time. Design a polynomial time algorithm that finds a feasible schedule such that the total profit we can get is maximized.

## 17.

### Description

Given an undirected graph G(V,E), a feedback set is a set X ⊆ V with the property that G − X has no cycles. The undirected feedback set problem asks whether G contains a feedback set of size at most k. Show that the problem is NP-complete.

## 18. Rearrangable Matrix

### Description

1. 给一个每行每列都有1元素但是不是RM的例子
2. 给一个多项式算法判断给定矩阵是不是RM

1.

1 0 0
1 0 0
0 1 1

2.

## 20. Multiple Interval Scheduling

### Description

In this problem, we have a single processor which can only work on one job at any single point in time. We are also given a set of jobs, each of them requiring a set of disjoint intervals of time during which it needs to be processed on the processor. For example, a job could require the processor form 10am to 11am and 1pm to 2pm. We would like to answer the following question: For a set of jobs and a given number k, is it possible to process at least k jobs in the processor. Show that the problem is NP-complete. (Hint: Maximum Independent Set is a possible candidate for the reduction.)

## 21.

### Description

You have m slow machines and k fast machines. You are given a set of n jobs. Job i takes time ti to process on a slow machine and time ti/2 to process on a fast machine. Assign each job to a machine such that the makespan is minimized. (The makespan is the maximum load of any machine.) Design a polynomial time approximation algorithm that produces an assignment with a makespan at most 3 times the optimum.

## 22. Densest k-Subgraph

We are given an undirected graph G(V,E). The densest k-subgraph problem asks for a subset S of k vertices such that the number of edges in the induced graph G[S] is maximized. Formulate the decision version of the problem and show it is NP-Complete.

### Solution

CLIQUE问题，是否存在包含k个节点的CLIQUE（任两个节点两两相连）；给定一个这个问题，问是否存在k个节点的CLIQUE使得边的数目为k(k-1)/2。

## 23. Maximum Coverage

We are given a ground set U of n element and a collection of subsets S1, . . . , Sm. The goal is to choose k subsets and maximize the cardinality of their union.

1. Formulate the decision version of the problem and show it is NP-Complete.
2. Design a polynomial time approximation algorithm for the problem. Your algorithm should havean approximation ratio of 1 − 1/e in order to get full credit.

1.

2.

## 24. Polynomial Multiplication

You are given 2n numbers a1 , b1 , . . . , an , bn . Consider the polynomial P (x) = prod ni=1 (ai x + bi ). Design an algorithm that computes the expansion of P (x). In order to get full credit, your algorithm should run in time o(n2) (Note: small o).

### Solution

1. Evaluate p(x) and q(x) at 2n points ω0 , . . . , ω2n−1 using DFT. This step takes time Θ(n log n).

2. Obtain the values of p(x)q(x) at these 2n points through pointwise multiplication

3. Interpolate the polynomial p·q at the product values using inverse DFT to obtain coefficients c0, c1, . . . , c2n−2. This last step requires time Θ(n log n).

## 25. Longest increasing subsequence

You are given a sequence S of n numbers a1 , a2 , . . . , an . A subsequence ai1,ai2,…,aik is increasing if i1 < i2 < … < ik and ai1 < ai2,… < aik. For example, S = {2, 10, 7, 11, 8, 6, 12} is the given sequence and {2, 10, 11, 12} is an increasing subsequence. Design a polynomial time algorithm that finds an longest increasing subsequence in the given sequence S.

## 28. Hamitonian cycle

Every graph with n ≥ 3 vertices and minimum degree at least ⌈n/2⌉ has a Hamitonian cycle.

## 29. Catch a car

Catch a car without knowing anything. We have an infinite road (i.e., (−∞, +∞)) and a car whose initial position p (at time 0) is some unknown integer. The car is running at a fixed velocity v. v is some unknown but fixed integer. Note that v can be negative which means the car is heading towards −∞. At each time step, you can make at most one query of the following form: Is the car at position x now? (you can choose the integer x). Design a query strategy such that you can guarantee you will get a ”yes” answer in finite time. (HINT: It is easy to see that the position of the car at time t is p + vt.)

## 31. Traveling salesman in the unit square

In this problem, we are considering a very classic problem in computer science - the traveling salesman problem. We are given a set of n points in the unit square ([0, 1] × [0, 1]). For two points v, u, we use |uv| to denote the Euclidean distance between u and v. A traveling salesman tour is a tour that starts at some starting point, goes through all points exactly once and ends at the starting point.

1. Prove that there is a tour {v1, v2, . . . , vn, v1} (i.e., the tour visits v1 first, then v2 and so on) such that |v1v2|2 + |v2v3|2 + . . . + |vn−1vn|2 + |vnv1|2 ≤ 4
2. Prove that there is a tour {v1,v2,…,vn,v1} such that |v1v2|+|v2v3|+…+|vn−1vn|+|vnv1|≤2 √n

### Solution

1. 不会求解

2. 柯西不等式可以直接从第一问的结果推出第二问的结果 $(|v_1v_2| + \cdots + |v_nv_1|)^2 \le n (|v_1v_2|^2 + \cdots + |v_nv_1|^2)$

## 32.

1. Show that a graph with maximum degree ∆ can be colored in ∆ + 1 colors.
2. We are given a 3-colorable graph G(V, E). In other words, it is possible to color the vertices of G using 3 colors such that no edge is incident on two vertices with the same color. Show that 2-coloring the neighbors of any vertex (if possible) can be done in polynomial time.
3. We are given a 3-colorable graph G(V, E). Design a polynomial time algorithm that finds an O(√|V |)-coloring of G.

### Solution

1. 显然，由于最大的degree比颜色数目少一个，因此它的顶点都能够分配不同的颜色；从任意顶点开始着色，所有颜色的集合C，与它相连的已经着色的顶点的颜色集合A，未着色的顶点的数目N，|C \ A| > N，因此每个未着色的顶点都能够被着不同颜色。
2. 首先证明如果一个图是3-colorable的，那么对于任意一个顶点v，其邻居N(v)中的节点构成一个二分图。如果N(v)中有一个单数环，那么不可能用剩下的两种颜色着色，因此，不存在单数环，因此N(v)是一个二分图。因此对于任意一个节点，它的颜色如果是A，那么在N(v)中，二分图的一边着色B，一边着色C。由此，再找这个节点的一个邻居扩展。可以着色所有的顶点。
3. 对于degree大于$\sqrt(n)$的节点用第二问的方法着色；对于degree小于$\sqrt(n)$的节点就用$\sqrt(n)$个颜色来着色。

## 34. Coupon collector’s problem

Initially, we have n empty bins. In each round, we throw a ball into a uniformly random chosen bin. Let T be number of rounds needed such that no bin is empty. Show that $\mathbb{E}[T] = nH_n$, where$H_n = \sum_{i=1}^n \dfrac{1}{n}$.

## 35. Bipartite min-cost matching

Show that finding a min-cost matching with exactly k edges in a bipartite graph can be solved in polynomial time.

## 36.

1. In any bipartite graph, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover.
2. In any bipartite graph, the number of vertices in a maximum independent set equals the total number of vertices minus the number of edges in a maximum matching.

### Solution

1.

Kőnig’s theorem: 从一个最大匹配构最小顶点覆盖的方法。注意最大匹配的性质是不能找到更长的alternating path。U: 左边L没有被匹配的节点；Z: 通过alternating path和U相连的节点；$K=(L \backslash Z) \cup (R \cap Z)$是构造出来的顶点覆盖。

2.

K是最小顶点覆盖 $\Leftrightarrow$ V-K是最大独立集

## 39.

1. A man finds himself on a riverbank with a wolf, a goat, and a head of cabbage. He needs to transport all three to the other side of the river in his boat. However, the boat has room for only the man himself and one other item (either the wolf, the goat, or the cabbage). In his absence, the wolf would eat the goat, and the goat would eat the cabbage. Show how the man can get all these ”passengers” to the other side.
2. We consider a generalization of the above problem. We are given n objects on a riverbank. We are also given a set of pairs of objects. Each pair of objects means that the two objects cannot stay on either side of the river together without the man’s supervision. For example, in the above problem, the set of pairs is (Wolf, Goat), (Goat, Cabbage). Now, your boat can hold the man and at most k other objects where the input k is smaller than n. Design an algorithm to decide whether it is possible for the man to get all objects to the other side of the river. What is the running time of your algorithm?

### Solution

1. G ->; <-;C ->; G <-; W ->; <-; G ->
2. 待验证：每个物品是一个顶点，一个这样的对连接一个边，如果这个图的Vertex Cover的数目不超过k，并且最大度数也不超过k，就可以运输？

## 40.

### Description

Without the help of a computer or calculator, find the total sum of the digits in all integers from 1 to a million, inclusive. Write down the computation details.

### Solution

1到9合起来是45，到100w有6位的数字，每一位都从0~9变化了10w次，所以是$610000045+1=27000001$次，最后那一个是100w中的单出来的1。

There are n people, each in possession of a different rumor. They want to share all the rumors through a series of bilateral conversations (e.g., via a telephone). Devise an efficient (in terms of the total number of conversations) algorithm for this task. Assume that in every conversation both parties exchange all the rumors they know at the time. (You can assume n is a power of 2 first.)

## 42.

### Description

We are given a sequence of distinct numbers A1, A2, A3, ,, An. For each number, its position in the sequence and its position in the sorted sequence (in increasing order) differ by at most k, where k is much smaller than n. Design an algorithm that sort the sequence in time less than O(n log n). Of course, the running time of your algorithm should depend on k.

### Solution

for i = 1 to k:
for j = 1 to n-1:
if A[j] > A[j+1]:
swap(A[j], A[j+1])

## 46.

### Description

An undirected Eularian graph is a connected graph in which all nodes have even degree. You job is to design an efficient algorithm that traverse an undirected Eularian graph so that each edge is visited exactly once.

### Solution

• 方法一：从任意的一个点开始，每选择一条边之后就把这个边从图里面删除，当有多条边可以选择的时候，要选择删除这条边之后不会破坏图联通性的边。检测图连通性的方式最差可以使用一个DFS在多项式时间里面找出来。对于连通性的检测的次数最多为O(d|E|)，其中d为图中最大的度数
• 方法二：从任意的一个点开始，随便走，最后肯定能回到这个点，只不过有些点访问不到。在刚刚的路径里面找一个点，它还有往外面连通的边，然后从这个点再随便走一个环，并且把这个环加到刚刚的环的某个位置上。重复此操作，可以找到最后的环。复杂度O(|E|)

## 47.

### Description

A directed Eularian graph is a strongly connected graph in which the indegree of each node is equal to its outdegree. You job is to design an efficient algorithm that traverse a directed Eularian graph so that each edge is visited exactly once.

## 57.

### Description

Given a set $\mathcal{H}$ of halfspaces (in general positions) in $\mathbb{R}^d$, design an efficient algorithm that decides whether $\mathcal{H}$ can cover the whole space $\mathbb{R}^d$. If $\mathcal{H}$ can cover $\mathbb{R}^d$, show there is always a subset of $\mathcal{H}$ with at most d + 1 halfspaces that also covers $\mathbb{R}^d$.

### Solution

Similar to Helly’s Theorem but not the same, I have no idea.

## 59.

### Description

There are n players. Each player holds a private 0/1 bit. Player 1 is the coordinator. The coordinator wants to compute the parity (i.e., determine there are even number of 1s or odd number of 1s).

In each round, your protocol can choose a player and let the player to broadcast a bit (depending on your protocol, the bit can be either the player’s own bit, or other encoded information). Upon the broadcast, each other player can receive the bit with probability $1 − \epsilon$ for some small constant $0 < \epsilon < 1/3$, and the flipped bit with probability $\epsilon$ (all flips are independent of each other). Show if every player broadcasts her bits for k = O(log n) times, the coordinator can compute the parity correctly with probability 0.9.

## 60.

### Description

There are n straight lines in a $\mathbb{R}^{2}$ plane.

1. Design an $O(n\log n)$ time algorithm for the following decision problem: Given two vertical slab W bounded by two vertical line x = a and x = b, compute how many intersection points of ${l_i},\ i\in[n]$ are there in W.
2. Given a vertical slab, show how to uniformly sample q intersection points in W in $O(n \log n + q)$ time.

### Solution

1.

1. find intersection points of the n lines with x=a in O(n).
2. argsort these points in O(nlogn), resulting in a list of the numbering of the lines $[i_1, i_2, \cdots, i_n]$, where $i_1$ represent the $i_1$-st line’s intersection with x=a hax maximum y.
3. calculate the lines’ intersection with x=b note down $(j, y_{i_j})$ if line $i_j$ intersect at $(x,y)=(b,y_{i_j})$ in O(n)
4. argsort these tuple by y in O(n logn), resulting in a list which is a permutation of $[n]$
5. number of intersection points is the number of inversions（逆序对）
6. we can count inversions in a mergesort style during which a counter is added - the counter should add the length of current left-hand-side part when a element in right-hand-side is added to the merging queue. This can be done in O(n log n)

2.

## 64. Tiling Problem is NPC

### Description

We are given a finite set S of rectangles and a rectangle R in the plane. Is there a way of placing the rectangles of S inside R, so that no pair of the rectangles intersect, and all the rectangles have their edges parallel of the edges of R? Show the problem is NPC.

### Method

• 一般证明步骤：
1. 证明是NP（给定一个候选的解，能够在多项式时间内检验解是不是合理的解）
2. 能够把一个现成的NPC问题规约到这个问题上（给定一个NPC问题，把NPC问题的输入在多项式时间内变为这个问题的输入，再将这个问题的输出变化为该NPC问题的输出）
• 常见NPC问题：
1. 3SAT：给定一堆布尔变量和一堆子句（形如A或者B或者C），是否存在一个布尔变量的赋值是的所有子句为真。
2. Independent Set：图G中的顶点集合S满足其中的任意两个顶点不共边，则称S为独立集；求解图G的最大独立集。
3. Vertex Cover：图的顶点覆盖是一组顶点的集合，使得图的每个边缘至少与集合中的一个顶点相连接；求解图G的最大顶点覆盖。
4. Integer Linear Programming：线性方程组是否存在整数解
5. Hamiltonian Cycle：一个图是否存在Hamiltonian cycle
6. Subset Sum：给定一组整数，是否存在一些整数使得其和等于K
7. Bin Packing：给定一组一维长度小于1的线段，找出这堆线段的一个划分，使得划分的子集数目最小，并且每个子集中线段的和都小于1

### Solution

1. 给定一个矩形的分配方案，我们能够在多项式内验证这个方案是否可以，即，逐对检查矩形是否相交，并且是否超出了大矩形，即是NP
2. 我们从Bin Packing规约，给定Bin Packing的一个输入$x_1, x_2, \cdots, x_n$，构造一个Tiling的输入，使得n个矩形的宽度分别为$x_i$，长度为2（任何大于1的数都可以），大举行的宽度为1，长度为$2k$。我们依次增加k，看看最少k等于多少时，能够把这些矩形都包含进去，返回这个k。这个k的数值就是Bin Packing问题里面最少需要的子集个数。注意到因为小矩形的长大于1，因此没法旋转，只能横向排。