AADS Assignment2 ideas
==

[TOC]

### Exercises for Linear programming and optimization
#### 29.1-5
**Step 1:**
$$
\begin{array}{ll}
\operatorname{maximize}
& 2x_1 - 6x_3\\
\operatorname{subject to}
& x_1 + x_2 - x_3 & \leqslant 7 \\
& -3 x_1 + x_2 & \leqslant 8 \\
& x_1 -2 x_2 -3 x_3 & \leqslant 0 \\
& x_1, x_2, x_3 & \geqslant 0
\end{array}
$$
**Step 2:**
$$
\begin{array}{ll}
\operatorname{maximize}
& 2x_1 - 6x_3\\
\operatorname{subject to}
& x_1 + x_2 - x_3 + x_4 & = 7 \\
& -3 x_1 + x_2 + x_5 & = 8 \\
& x_1 -2 x_2 -3 x_3 + x_6 & = 0 \\
& x_1, x_2, x_3, x_4, x_5, x_6 & \geqslant 0
\end{array}
$$
**Step 3:**
$$
\begin{array}{ll}
\operatorname{maximize}
& 2x_1 - 6x_3\\
\operatorname{subject to}
& x_4 =7-x_1-x_2+x_3 \\
& x_5 =-8+3 x_1-x_2 \\
& x_6 =-x_1+2 x_2+2 x_3 \\
& x_1, x_2, x_3, x_4, x_5, x_6 \geqslant 0
\end{array}
$$
The basic variables are $x_4, x_5, x_6$ and the nonbasic variables are $x_1, x_2, x_3$.

#### 29-2.6

如图：

求最大二分配:
$$
\begin{array}{ll}
\operatorname{maximize}
& f(s, v_1) + f(s, v_2) + f(s, v_3)\\
\operatorname{subject to}
& f(s, v_1) - f(v_1, v_4) - f(v_1, v_5) & = 0\\
& f(s, v_2) - f(v_2, v_4) & = 0\\
& f(s, v_3) - f(v_3, v_4) & = 0\\
& f(v_4, t) - f(v_1, v_4) - f(v_2, v_4) - f(v_3, v_4) & = 0\\
& f(v_5, t) - f(v_1, v_5) & = 0\\
& f(s, v_1), f(s, v_2), f(s, v_3), f(v_1, v_4), f(v_1, v_5), f(v_2, v_4), f(v_3, v_4), f(v_4, t), f(v_5, t) & \leqslant 1 \\
& f(s, v_1), f(s, v_2), f(s, v_3), f(v_1, v_4), f(v_1, v_5), f(v_2, v_4), f(v_3, v_4), f(v_4, t), f(v_5, t) & \geqslant 0
\end{array}
$$
一般情况：
$$
\begin{array}{ll}
\operatorname{maximize} & \sum_{v \in L} f_{s v} \\
\text { subject to } & \sum_{v \in V} f_{v u}=\sum_{v \in V} f_{u v} \text, \space u \in L \cup R \\
& f_{u v} \leqslant 1 \text, \space u, v \in V \\
& f_{u v} \geqslant 0 \text, \space u, v \in V
\end{array}
$$

#### 29-3.5
$$
\begin{array}{ll}
\operatorname{maximize}
& 18 x_1 & +12.5 x_2 \\
\operatorname{subject to}
& x_1 & +x_2 & \leqslant 20 \\
& x_1 & & \leqslant 12 \\
& & \quad x_2 & \leqslant 16 \\
& x_1,& \quad x_2 & \geqslant 0
\end{array}
$$
**Step 1:**
$$
\begin{array}{ll}
\operatorname{maximize}
& 18 x_1 & +12.5 x_2 \\
\operatorname{subject to}
& x_1 & +x_2 & +x_3 & & & = 20 \\
& x_1 & & & +x_4 & & = 12 \\
& & \quad x_2 & & & +x_5 & = 16 \\
& x_1,& \quad x_2, & \quad x_3, & \quad x_4, & \quad x_5 & \geqslant 0
\end{array}
$$
**Step 2:**
$$
\begin{aligned}
& z = 0 +18 x_1 +12.5 x_2 \\
& x_3 = 20 -x_1 -x_2 \\
& x_4 = 12 -x_1 \\
& x_5 = 16 -x_2 \\
\end{aligned}
$$
**Step 3:**
If $x_1$ is increased beyond 20 then $x_3$ becomes negative.
If $x_1$ is increased beyond 12 then $x_4$ becomes negative.
If $x_1$ is increased then $x_5$ remains unchanged.
Constraint defining $x_4$ is binding.
$$
\begin{aligned}
& z = 0 +18(12 -x_4) +12.5 x_2 \\
& x_3 = 20 -(12 -x_4) -x_2 \\
& x_1 = 12 -x_4 \\
& x_5 = 16 -x_2 \\
\end{aligned}
$$
$$
\begin{aligned}
& z = 216 +12.5 x_2 -18x_4 \\
& x_3 = 8 -x_2 +x_4 \\
& x_1 = 12 -x_4 \\
& x_5 = 16 -x_2 \\
\end{aligned}
$$
New basic variables: $x_1=12, x_3=8, x_5=16$
New objective value: $z = 216$
New feasible basic solution: $(12,0,8,0,16)$
**Step 3:**
If $x_2$ is increased beyond 16 then $x_1$ becomes negative.
If $x_2$ is increased beyond 8 then $x_3$ becomes negative.
If $x_2$ is increased then $x_1$ remains unchanged.
Constraint defining $x_3$ is binding.
$$
\begin{aligned}
& z = 216 +12.5(8 -x_3 +x_4) -18x_4 \\
& x_2 = 8 -x_3 +x_4 \\
& x_1 = 12 -x_4 \\
& x_5 = 16 -(8 -x_3 +x_4) \\
\end{aligned}
$$
$$
\begin{aligned}
& z = 316 − 12.5x_3 − 5.5x_4 \\
& x_2 = 8 -x_2 +x_4 \\
& x_1 = 12 -x_4 \\
& x_5 = 8 +x_3 - x_4 \\
\end{aligned}
$$
New basic variables: $x_1=12, x_2=8, x_5=8$
New objective value: $z = 316$
New feasible basic solution: $(12,8,0,0,8)$

Stop, since no more non-basic variables appear in the objective with a positive coefficient.

#### 29-4.1
$$
A =
\left(
\begin{array}{ccc}
0 & 18 & 12.5 \\
20 & -1 & -1 \\
12 & -1 & 0 \\
16 & 0 & -1
\end{array}
\right)
\Rightarrow
A^T =
\left(
\begin{array}{ccc}
0 & 20 & 12 & 16 \\
18 & -1 & -1 & 0 \\
12.5 & -1 & 0 & -1
\end{array}
\right)
$$
$$
\begin{aligned}
& z = 0 +18 x_1 +12.5 x_2 \\
& x_3 = 20 -x_1 -x_2 \\
& x_4 = 12 -x_1 \\
& x_5 = 16 -x_2 \\
\end{aligned}
\Rightarrow
\begin{aligned}
& z = 0 + 20 y_1 +12 y_2 +16 y_3 \\
& x_4 = 18 -y_1 -y_2 \\
& x_5 = 12.5 -y_1 -y_3 \\
\end{aligned}
$$

### Exercises for Randomized Algorithms
#### Q1
For any given key $x$ in $S$, let $d(x)$ be the depth of $x$ in the search tree generated by *RandQS*. Give a lower and an upper bound, as a function of the number of keys $n$, on the expected value of $d(x)$ such that these bounds are within a constant factor from each other. That is, find a function $f(n)$ and prove that $E[d(x)]=\theta(f(n))$.

**Proof:**
Because the number of comparisons of *RandQS* is $O(n\log(n))$, the sum of the depths of all keys $n$ in the search tree generated by *RandQS* is also $O(n\log(n))$. Each element is compared with other elements as many times as its depth in the search tree, and since there are $n$ keys in the search tree, the average or expected depth of each of key $x$ and depth $d(x)$ in the search tree is $O(n\log(n))$. So$\frac{1}{n}O(n\log(n)) = O(\log(n))$.

#### Q2
How many runs of randomized contraction do we need to be 99% sure that a minimum cut is found?

#### Q3
In the pdf on randomized algorithms, do exercises 1.2 and 1.3. (In 1.3 you may assume that $T(n)$ is the worst case running time of A)

### submit
<iframe src="https://www.slideshare.net/slideshow/embed_code/key/n5Ak5dYU9brUvK?hostedIn=slideshare&page=upload" width="800" height="1000" frameborder="0" marginwidth="0" marginheight="0" scrolling="no"></iframe>