# Algorithm - Homework 3 姓名: 陈声发 学号:2019280355 ## Problem 1 ![](https://i.imgur.com/yE68bsK.png) We can maintain winning statistics of player 0 and a play terminates with a win for player 0 iff player 0 is declared a winner and the play is a win for player 1 iff it runs forever. The set Q of nodes of this game consists of nodes of the form $(a, p, \tilde{b})$ where $a$ is a node of the parity game, the player $p \in \{\text{player 0}, \text{player 1}\}$ moves next and $\tilde{b}$ represents the winning statistics of player 0. The number of elements of Q can be bounded by $O(n^4)$. The starting node is $(s, p, \tilde 0)$, where $\tilde 0$ is the vector of all $b_i$ with value 0, $s$ is the starting node of the parity game and $p$ is the player who moves first. Note that the number of increasing functions from $\{0, 1, 2, . . . , log(n) + 2\}$ to $\{1, 2, 3, . . . , \log(n)\}$ can be bounded by $O(n^2)$. And $b^\prime_k\leq b^\prime_{k+1}$ implies $b^\prime_k + k \lt b^\prime_{k+1}+k+1$ and therefore the set can construct all the $b^\prime_k$. So we need at most $\log n+3$ additional bits to indicate which $b_k$ is 0. The overall winning statistics can then be represented by $3\log n + 5$ bits. And we need 1 bit to represent the player and $\log n$ bits to represent the current node in the play. So each node can be represented with $4 \log n$ + 6 bits resulting in $O(n^4)$ node in $Q$. Therefore, the time complexity is $O(2^m n^4)$, where m is the number of distinct value on the nodes. For $m \leq \log n$, there is a solution of time complexity $O(n^5)$. <div style="page-break-after: always;"></div> ## Problem 2 ![](https://i.imgur.com/CtwAaXz.png) We know all matching edges are tight and every blossom $B$ contains $\frac{|B|-1}{2}$ matching edges + $w(M^*)=\sum_{e\in M^*}yz(e)=\sum_{u\in V}y(u)+\sum_{b\in\Omega}z(B)\frac{|B|-1}{2}$ For every other matching $M$, a blossom $B$ contains no more than $\frac{|B|-1}{2}$ edges of $M$ + $w(M)$ $\leq\sum_{e\in M}yz(e)$ $=\sum_{u\in V}y(u)+\sum_{b\in\Omega}z(B)|M\cap E(B)|$ $\leq\sum_{u\in V}y(u)+\sum_{b\in\Omega}z(B)\frac{|B|-1}{2}$ Therefore, $M^*$ is a maximum weighted matching. <div style="page-break-after: always;"></div> ## Problem 3 ![](https://i.imgur.com/VCz26HD.png) There are at most $O(\frac{m}{t})$ dense rows or columns. The multiplication of dense part taks $n^{ω(p)}=O(\max\{n^2,n^2(\frac{m}{tn^α})^β\})$ time. The naive multiplication enumerates at most $O(t)$ many nonzero $b_{j,k}$ for each nonzero $a_{i,j}$, so it takes $O(mt)$ time. In total $O(\max\{n^2,n^2(\frac{m}{tn^α})^β\}+mt)$ time. We choose $t=O(\frac{n^{\frac{2-αβ}{1+β}}}{m^{\frac{1-β}{1+β}}})$, time complexity $O(\max\{n^2,n^{\frac{2-αβ}{1+β}}m^{\frac{2β}{1+β}}\})$. Let $m=n^k$, the time complexity has a better bound than $O(n^ω)$ when $m<n^{\frac{α+ω}{2}+\frac{ω-2}{2β}}$.