# 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β}}$.

PyFusion 0 - Task PyFusion 1 - 初步调研 PyFusion 2 - 安装记录 + 一些问题 PyFusion 3 - 初版 demo + 测试 PyFusion 4 - Superbenchmark 测试 nnfusion.jit config 设计 关于 nnfusion jit Decorator for class method + other details Others

3/24/2022Summary 语法初步调研 + 实现小 demo Details Decorators and/or with-statement with-statement with-statement 我理解不太合适。 with EXPR as VAR: BLOCK

2/9/202220210914 跑实验，存 pkls 来画 auc 图 conda activate chem git checkout get_fold 第一个实验 python train.py --data_path ~/chemprop/CTSL/CTSL_train_1.csv --dataset_type classification --save_dir checkpoints/CTSL_first_exp --gpu 6 --num_folds 10 --config_path ~/chemprop/CTSL/CTSL.json --ensemble_size 2 &> train_first_exp.log &

9/16/2021
Published on ** HackMD**

or

By clicking below, you agree to our terms of service.

Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet

Wallet
(
)

Connect another wallet
New to HackMD? Sign up