Solutions to Exam 3
Problem 1
Algorithm: Assign new request to the server with the least load. If there are multiple servers with the same least load, assign the request to the server with the smallest index.
We will show that the algorithm above is $2$-competitive.
Let $m(t)$ be the minimum load given by the algorithm above at time $t$. Additionally, let $\ell_i(t)$ be the total load of server $i$ at time $t$ assigned by our algorithm. Analogously, let $\ell_i^*(t)$ be the total load of server $i$ at time $t$ assigned by the optimal algorithm.
Note that $$ \sum_{i=1}^n \ell_i(t) = \sum_{i=1}^n \ell_i^*(t) = \sum_{k=1}^t p_k $$ since each request must be assigned to some server by any algorithm.
In particular, for any $t \geq 1$ this implies: $$ n \cdot M^*(t) \geq \sum_{i=1}^n \ell_i^*(t) = \sum_{k=1}^t p_k = \sum_{i=1}^n \ell_i(t) \geq n \cdot m(t) \Rightarrow M^*(t) \geq m(t). $$
Moreover, we also have that $M^*(t) \geq p_k$ for any $k \leq t$ since the optimal algorithm must assign each request to some server. Lastly, note that $M^*(t) \geq M^*(t-1)$ since the optimal algorithm cannot decrease the maximum load by assigning a request.
We are now ready to prove that our algorithm is $2$-competitive.
Let $i\in [n]$ be such that $\ell_i(t) = M(t)$ and let $k \leq t$ be the last time that server $i$ was assigned a request. Then, we must have $$M(t) = \ell_i(t) = \ell_i(k) = M(k) = \ell_i(k-1) + p_k$$ and by our algorithm we know that $\ell_i(k-1) = m(k-1)$, as we only assign a request to the server with minimum load.
Thus, by the inequalities above, we have: $$ M(t) = M(k) = \ell_i(k-1) + p_k = m(k-1) + p_k \leq M^*(k-1) + p_k \leq M^*(k-1) + M^*(k) \leq 2 \cdot M^*(t). $$
This concludes our proof that the algorithm is $2$-competitive.
Problem 2
As Max pointed out during the exam, this is exactly the unweighted heavy hitters problem that we saw in class. Thus, we will use the algorithm from class with $\varepsilon = 1/5$, which yields $k = \lceil 1/\varepsilon \rceil - 1 = 4$.
Thus, as we have seen in class, the unweighted heavy hitters will give us a list of at most for users that have read over $1/5$ of the total number of requests. Correctness follows from the analysis in class.
For the memory requirements, all we need to is to keep track of 2 arrays (each of length 4), one with the user IDs, and the other with the current counter as updated by the algorithm. Since each counter is at most $N$, the counter array needs $O(k \log N) = O(\log N)$ bits to be stored. And since each user ID is at most $N$, the user ID array needs $O(k \log N) = O(\log N)$ bits to be stored.
Problem 3
This is exactly the easy variant of the MWU problem with the investors that we saw in class. More precisely, we will assign values $1$ if a weather service predicts sunny weather, and $-1$ if it predicts rainy weather.
Then, our algorithm is as follows:
- Initialize $w_1(i) = 1$ for $i \in [n]$.
- For $t = 1, \ldots, T$:
- For the $t^{th}$ day, let $x_t(i) = 1$ if the weather service predicts sunny weather, and $x_t(i) = -1$ if it predicts rainy weather.
- Make the following prediction: $$ y_t = \begin{cases} 1 & \text{if } \sum_{i=1}^n w_t(i) x_t(i) \geq 0 \\ -1 & \text{otherwise} \end{cases} $$
- If weather service $i$ makes wrong prediction at time $t$, set $w_{t+1}(i) = w_t(i)/2$. (i.e. our parameter $\varepsilon = 1/2$).
Here you could have just claimed the result from class, but you could also have given a proof. (both were accepted with full credit).
From class, we saw that $$M_T \leq 2(1 + \varepsilon) M_T(i) + \dfrac{2\log n}{\varepsilon} = 3 \cdot M_T(i) + 4 \cdot \log n$$ where $M_T(i)$ is the number of mistakes made by weather service $i$, and $M_T$ is the number of mistakes of our algorithm.
Problem 4
We will prove each direction separately.
Claim 1: If there is an assignment satisfying $t$ clauses, then there is an independent set of size $t$ in $G_\varphi$.
Proof: Let $y$ be an assignment satisfying clauses $C_1, \ldots, C_t$ (after potential relabeling of the clauses). Then, for each $j \in [t]$, let $v_{ij}$ be a vertex corresponding to a literal in $C_j$ that satisfies $C_j$. We will show that the set $S = {v_{ij} \mid i \in [n], j \in [t]}$ is an independent set of size $t$. Since we pick exactly one vertex per clause $C_1, \ldots, C_t$, we have that $|S| = t$ and that no two of these vertices are connected by edges from the triangle given by $C_j$. Moreover, since we are picking consistent assignments, if we pick $v_{ij}$ and $v_{ik}$ for two different clauses, it must be the case that $y_i$ (or $\overline{y_i}$) satisfies both $C_j$ and $C_k$. Hence, there is no consistency edge between $v_{ij}$ and $v_{ik}$. Since we covered all possible edges, this proves that $S$ is an independent set of size $t$.
Claim 2: If there is an independent set of size $t$ in $G_\varphi$, then there is an assignment satisfying $t$ clauses.
Proof: Let $S$ be an independent set of size $t$ in $G_\varphi$. Then, for each $j \in [t]$, let $v_{ij}$ be the vertex in $S$ corresponding to a literal in $C_j$. Since $S$ is an independent set, we know that no two vertices $v_{ij}$ and $v_{ik}$ are connected by either a clause edge or a consistency edge. Thus, we have two properties:
- After potential relabeling of clauses, we have $S = {v_{i_1 1}, \ldots, v_{i_t t}}$
- If $v_{ij}$ and $v_{ik}$ are elements of $S$ then $y_i$ (or $\overline{y_i}$) satisfies both $C_j$ and $C_k$.
Where point 1 comes from having no clause edges, and point 2 comes from having no consistency edges.
Hence, construct the assignment as follows: for each $i \in [n]$:
- if there is no $j \in [t]$ such that $v_{ij} \in S$, set $y_i = 0$.
- else, set $y_i = 1$ if the literal corresponding to $v_{ij}$ is $x_i$, and $y_i = 0$ otherwise (i.e., the literal corresponding to $v_{ij}$ is $\overline{x_i}$).
We claim that this assignment satisfies the $t$ clauses $C_1, \ldots, C_t$. To see this, note that for each $j \in [t]$, we have that $v_{ij} \in S$ for some $i \in [n]$. Thus, by construction, $y_i$ (or $\overline{y_i}$) satisfies $C_j$. This completes the proof.
Problem 5
Let $A$ be an $n \times n$ matrix. Thus, we can write $p_A(t) := \sum_{i=0}^n a_i t^i$ for some coefficients $a_0, \ldots, a_n$ (with $a_n = 1$). Then, we have that the evaluations $p_A(0), \ldots, p_A(n)$ can be encoded as the following matrix vector multiplication: $$ \begin{bmatrix} p_A(0) \\ \vdots \\ p_A(n) \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0^2 & \cdots & 0 \\ 1 & 1 & 1^2 & \cdots & 1 \\ \vdots & \vdots & \ddots & \ddots \\ 1 & n & n^2 & \cdots & n^n \end{bmatrix} \begin{bmatrix} a_0 \\ \vdots \\ a_n \end{bmatrix} $$
Let $B$ be the matrix on the right hand side of the above equation. Then, we have that $B$ is a Vandermonde matrix on distinct evaluations, and hence, it is invertible.
Thus, our algorithm to compute $p_A$ is as follows:
- Compute $B^{-1}$ with a matrix inverse algorithm.
- Compute $p_A(0), \ldots, p_A(n)$ by using an algorithm to compute the determinant.
- Compute $B^{-1} \begin{bmatrix} p_A(0) \\ \vdots \\ p_A(n) \end{bmatrix}$ by a matrix vector multiplication.
The above algorithm will give us all the coefficients of $p_A$, and thus we have succeeded in computing it. Correctness follows from the equation above, and the runtime is given by $n+1$ determinant computations (each taking $C \cdot n^\omega$ time) and one matrix inverse computation (taking $C \cdot n^\omega$ time), for a total runtime of $O(n^{\omega+1})$. (note that matrix-vector multiplications run in $O(n^2)$ time, and hence are dominated by the determinant and matrix inverse computations, as $2 \leq \omega$).