[ps4] typos

1 files changed, 16 insertions, 15 deletions

diff --git a/ps4/main.tex b/ps4/main.tex
index c8a8b3f..6c0915e 100644
--- a/ps4/main.tex
+++ b/ps4/main.tex
@@ -59,7 +59,7 @@ and $y$ satisfy the approximate complementary slackness conditions. Then:
 \end{align*}
 where we used the first approximate complementary slackness condition in the
 first line. In the second line, we first used that the dot product is linear in
-its first coordinate, then the definition of the matrix-product vector. Finally
+its first coordinate, then the definition of the matrix-vector product. Finally
 we used the second complementary slackness condition in the last line.
 
 \section*{Problem 2}
@@ -100,7 +100,7 @@ for page $i$ at time $t$ arrives:
         cache which are not $i$ to maintain dual feasibility.
 \end{enumerate*}
 We show that at time $t$, $P(t) \leq k D(t) + \big(\Phi(t) - \Phi(t-1)\big)$ in
-all three cases. $P(t)$ is simply one or zero depending on whether or not ther
+all three cases above. $P(t)$ is simply one or zero depending on whether or not there
 has been an eviction. $\Delta\Phi$ is the difference in the number of marked
 pages:
 \begin{enumerate*}
@@ -108,17 +108,17 @@ pages:
         marked). This is ok. 
     \item $P(t) = 1$ (one eviction), $D(t) = 0$ and $\Delta\Phi = 1$ (one page
         marked). This is still ok.
-    \item $P(t) = 1$ (one eviction), $D(t) = (n-k) - (n-k-1)$ (there are
+    \item $P(t) = 1$ (one eviction), $D(t) = (n-k) - (n-k-1) = 1$ (there are
         $n-k+1$ pages outside the cache which are not $i$) and $\Delta\phi = -k
-        + 1$. This is still ok.
+        + 1$. This is again ok.
 \end{enumerate*}
 
-If we some the previous inequality over $t$, we have $\sum_t P(t)$ on the
+If we sum the previous inequality over $t$, we have $\sum_t P(t)$ on the
 left-hand side, this is the cost of the $1$-bit LRU algorithm. On the right
 hand side, we get $k\sum_t D(t) + \Phi(T) - \Phi(1)$. The difference in
 potential is at most $k$, and $\sum_t D(t)$, the value of our dual solution is
 less than the value of any feasible solution for the primal (weak duality) and
-in particual the optimal integral solution $\text{OPT}$. Hence, we have proved
+in particular the optimal integral solution $\text{OPT}$. Hence, we have proved
 that the cost attained by $1$-bit LRU is bounded by $k\text{OPT} + k=
 k(\text{OPT} +1)$
 
@@ -140,8 +140,9 @@ can be written as:
 
 \paragraph{(b)} We propose the following algorithm. We iterate over all edges.
 At each iteration we increase the dual variable of that edge until one or both
-of the two dual constraints for its edge points become tight. Whenever
-a constraint becomes tight, we set the primal variable its vertex to 1.
+of the two dual constraints for its end points become tight. Whenever
+a constraint becomes tight, we set the primal variable of its associated vertex
+to 1.
 \begin{algorithm}
     \begin{algorithmic}[1]
         \For{$e=(u,v)\in E$}
@@ -166,9 +167,9 @@ We can now conclude by observing that:
     2\sum_e y_e = \sum_{v\in V}\sum_{e:v\in e} y_e
     \geq \sum_v c_v x_v
 \end{displaymath}
-The equality comes from the fact that the double summation counts each
-edge twice. The inequality comes from the fact that when $x_v = 1$ it means
-that the dual constraint was tight, that is $c_v  = \sum_{e: v\in e} y_e$.
+The equality comes from the fact that the double summation counts each edge
+twice. The inequality comes from the fact that $x_v = 1$ implies that that the
+associated dual constraint was tight, that is $c_v  = \sum_{e: v\in e} y_e$.
 
 But by weak duality, $\sum_e y_e$ is smaller than any primal feasible solution,
 and in particular the optimal integral solution. Hence $\sum_e y_e\leq
@@ -186,8 +187,8 @@ and in particular the optimal integral solution. Hence $\sum_e y_e\leq
 By substitution in the objective function. We see that all feasible flows have
 the same value 3. Thus every feasible solution is optimal. As a consequence,
 the fractional solution $x =\frac{1}{2}, y = \frac{3}{2}, z =\frac{1}{2}$ is
-optimal and has the same value as the integral solution $x = 1, y = 1$ (the
-other integral solution is $y=1, z=1$).
+optimal and has the same value as the integral solution $x = 1, y = 1, z=0$ (the
+other integral solution is $x=0, y=1, z=1$).
 
 \paragraph{(b)} We introduce a dual variable $p_v$ for each vertex. The dual
 problem can be written:
@@ -210,8 +211,8 @@ following two properties throughout the execution:
 \end{itemize*}
 
 At the beginning, we set $f_{u,v} = 0$ for all $(u,v)\in E$, $d_s = 0$ and $d_v
-= +\infty$ for all $v$. Let us consider a step of Dijkstra's algorithm where we are examining edge
-$(u,v)$ in $E$. If $p_v> p_u + L(u,v)$ then:
+= +\infty$ for all $v$. Let us consider a step of Dijkstra's algorithm where we
+are examining edge $(u,v)$ in $E$. If $p_v> p_u + L(u,v)$ then:
 \begin{enumerate}
     \item set $p_v = p_u + L(u,v)$ and set $f_{u,v} = 1$
     \item add $-1$ to $f_e$ for all edges $e$ in the previous path from $s$