0%

Quiz部分的得分与正确率和答题速度相关，在大家都答对题目的情况下，答题更快的可以获得更高的得分。

• Quick Math (5s) - 基本的数学运算，难度大概在三位数加减法和两位数乘法的水平，重点可能在于时间限制较为紧迫
• Fun Facts (20s) - 询问一些现实生活当中的数字，考察量级估计和现场搜索的能力
• Find Pattern (30s) - 图形找规律，填写下一项是什么
• Easy Brain Teasers (30s) - 较为简单，基本上是基本数学直觉的考察
• Sequence (60s) - 数列找规律，填写下一项是什么
• Medium Brain Teasers (60s) - 普通的概率问题
• Hard Brain Teasers (120s) - 较复杂一些的概率问题

### No. 7 (Hard Brain Teasers)

10个人围成一个圈。每个人可以拍一拍左侧或者右侧的人，请问被拍的人的个数的期望是多少？

1. 2.5
2. 5
3. 7.5
4. 8.36

Answer: C

### No. 12 (Sequence)

$2,3,7,16,65,?$

1. 321
2. 81
3. 122
4. 179
Answer: A

### No. 13 (Fun Facts)

1. 10b/day (一百亿)
2. 100b/day (一千亿)
3. 1t/day (一万亿)
4. 10t/day (十万亿)

Answer: C

### No. 14 (Sequence)

$15,29,56,108,208,?$

1. 400
2. 416
3. 438
4. 386
Answer: A

1. 1157kg
2. 1312kg
3. 694kg
4. 866kg
Answer: A

1. 4/5
2. 11/30
3. 7/20
4. 5/12

Answer: B

1. 50%
2. 25%
3. 19%
4. 11%

Answer: C

Answer: A

1. 8
2. 10
3. 20/3
4. 15
Answer: A

1. 257
2. 289
3. 157
4. 349
Answer: B

### No. 22 (Medium Brain Teasers)

2. $0.5 3.$1
4. \$1/3

Answer: B

1. [1, 100]
2. [101, 200]
3. [201, 300]
4. [301, 400]

Answer: A

### No. 24 (Hard Brain Teasers)

$(1+\sqrt{2})^{3000}$小数点后第$100$位的数字是多少？

1. 0
2. 1
3. 4
4. 9

Answer: D

1. 0
2. 1
3. 2
4. 无穷多个

Answer: D

### No. 26 (Sequence)

$91,85,94,83,97,81,?,79$

1. 80
2. 100
3. 102
4. 95

Answer: B

1. 5
2. 6
3. 7
4. 8

Answer: C

1. 26
2. 28
3. 30
4. 24
Answer: A

### No. 29 (Sequence)

$99,18,36,9,18$

1. 36
2. 27
3. 9
4. 3

Answer: C

1. 250
2. 25000
3. 2500000
4. 250000000
Answer: C

1. 315
2. 420
3. 525
4. 840
Answer: A

1. -100°C
2. -60°C
3. -20°C
4. 20°C
Answer: B

1. 22
2. 23
3. 24
4. 26

Answer: A

### No. 37 (Easy Brain Teasers)

1. 在列表中至少有1个命题是错误的
2. 在列表中至少有2个命题是错误的
3. 在列表中至少有3个命题是错误的
4. 在列表中至少有4个命题是错误的
Answer: A

### No. 38 (Sequence)

$-3,3,27,69,129,?$

1. 178
2. 207
3. 312
4. 268
Answer: B

Answer: B

### No. 40 (Hard Brain Teasers)

1. Sqrt(2)
2. 2
3. Sqrt(10)
4. Sqrt(34)

Answer: C

$\text{Years to Double} = \frac{72}{\text{Interest Rate}}$

Bob和Alice被邀请参加一个卡牌游戏。庄家从一组扑克牌（4种花色，A-K）给Bob随机发放5张。Bob可以选择其中4张给Alice看，然后Alice被要求猜测Bob手中剩下的一张牌的花色和点数。

Bob和Alice能否仅仅根据牌的花色和点数设计出一个策略，使得无论Bob拿到的是哪五张牌，Alice都能成功猜测出最后一张牌的花色和点数。

$13 = 2 * 3! + 1$

• dimension (int) – unfold操作所作用的维度
• size (int) – 滑动窗口的窗口大小
• step (int) – 滑动窗口的步长

## 实现过程

Lab1的主要任务就是通过Golang来实现一个MapReduce的算法，具体的内容可以从Lab1的官方文档中获取。

One way to get started is to modify mr/worker.go's Worker() to send an RPC to the master asking for a task. Then modify the master to respond with the file name of an as-yet-unstarted map task. Then modify the worker to read that file and call the application Map function, as in mrsequential.go.

Worker()当中仿照样例里面的内容发送RPC请求，结果分为三类执行对应的MapReduceWait三类任务。

The application Map and Reduce functions are loaded at run-time using the Go plugin package, from files whose names end in .so.

If you change anything in the mr/ directory, you will probably have to re-build any MapReduce plugins you use, with something like go build -buildmode=plugin ../mrapps/wc.go

**这里每次都要重新build！**不然直接会出错，一开始没有注意到检查了挺久。

This lab relies on the workers sharing a file system. That’s straightforward when all workers run on the same machine, but would require a global filesystem like GFS if the workers ran on different machines.

A reasonable naming convention for intermediate files is mr-X-Y, where X is the Map task number, and Y is the reduce task number.

The worker’s map task code will need a way to store intermediate key/value pairs in files in a way that can be correctly read back during reduce tasks. One possibility is to use Go’s encoding/json package. To write key/value pairs to a JSON file:

and to read such a file back:

The map part of your worker can use the ihash(key) function (in worker.go) to pick the reduce task for a given key.

You can steal some code from mrsequential.go for reading Map input files, for sorting intermedate key/value pairs between the Map and Reduce, and for storing Reduce output in files.

The master, as an RPC server, will be concurrent; don’t forget to lock shared data.

Use Go’s race detector, with go build -race and go run -race. test-mr.sh has a comment that shows you how to enable the race detector for the tests.

Workers will sometimes need to wait, e.g. reduces can’t start until the last map has finished. One possibility is for workers to periodically ask the master for work, sleeping with time.Sleep() between each request. Another possibility is for the relevant RPC handler in the master to have a loop that waits, either with time.Sleep() or sync.Cond. Go runs the handler for each RPC in its own thread, so the fact that one handler is waiting won’t prevent the master from processing other RPCs.

The master can’t reliably distinguish between crashed workers, workers that are alive but have stalled for some reason, and workers that are executing but too slowly to be useful. The best you can do is have the master wait for some amount of time, and then give up and re-issue the task to a different worker. For this lab, have the master wait for ten seconds; after that the master should assume the worker has died (of course, it might not have).

To test crash recovery, you can use the mrapps/crash.go application plugin. It randomly exits in the Map and Reduce functions.

Test的最后一个部分就是crash test，会使用crash.so文件，事实上，在上面利用一个go routine取检查超时，如果一个worker在工作过程中crash了，那么就无法在最后返回个master一个Finish的RPC。所以利用以上的超时检查机制，是可以简单的对于Lab当中的crash进行正确重分配任务，保证MapReduce流程正常进行。

To ensure that nobody observes partially written files in the presence of crashes, the MapReduce paper mentions the trick of using a temporary file and atomically renaming it once it is completely written. You can use ioutil.TempFile to create a temporary file and os.Rename to atomically rename it.

test-mr.sh runs all the processes in the sub-directory mr-tmp, so if something goes wrong and you want to look at intermediate or output files, look there.

## 体验

• Golang上手的感觉还行，感觉和C语言差别不大，有C语言的基础熟悉一下语言特性应该就可以上手。
• 难度一般，可能是Lab1的缘故，总体实现上困难不是很大。
• 从文档和代码上看，整个Lab的结构上感觉没有6.828课程的巧妙，但是已经非常完备了，远超国内学校课程作业的实用程度。

2020

1. （博弈论）ABC三家公司，在0-100的101个整数点上都存在住户，按照ABC的顺序每个人依次选择1-100当中的一个位置作为公司的办公地点，住户会选择离他最近的公司。为了最大化收益（最大化到自己公司的用户数量），A的最优选择是什么？

1. $N$个序列，每个序列有3个数字，任意两组之间的correlation都小于0.7，问$N$可能的最大取值是多少。

1. 一个没有记忆功能科学计算器，加减乘除和数字键都坏了，可以采用类似三角函数，取倒数，对数，开方，阶乘等操作。最开始只有一个0，如何得到任意整数？如何得到任意有理数？

1. 笔试当中提到的，最奇怪的交易股票的策略。

CQ资产的笔试题目，笔试时间为40分钟，题量为9道。总体感觉笔试难度适中，时间有一点紧。由于笔试题目本身为英文，这里不做额外的翻译，解答为笔者所做，可能存在错误。

1. Given the following function definition: (4 min, score = 3)

How many additions will take place while evaluating f(f(f(3)))?

Solution:

\begin{aligned} f(x) &= 1 + ( 1+ \ldots+x) \\ &=1 + \frac{x(1+x)}{2} \\ &= \frac{x^2 + x + 2}{2} \end{aligned}

Total additions:$3+f(3) + f(f(3)) = 3+7+29=39$.

1. A stock’s price fluctuates every day by going up exactly 5% or going down exactly 5%. Assume that each direction is equally likely. Assume zero trading cost, zero interest rate, and no dividends and splits. What strategy is most likely to be profitable after 100 days?
(3 min, score = 3)

A. Buy or sell will produce same profitable

B. Cannot know / no strategy can be profitable

C. Buy the stock

D. Sell the stock

Solution:

D

1. Below is a list of asymptotic complexities of 8 functions, each with length N input:

1. O(N^3)

2. O(Log(N))

3. O(Sqrt(N))

4. O(N * log(N))

5. O(2^N)

6. O(N^N)

7. O(N!)

8. O(Log(Log(N)))

Please sort the functions by order of growth, with slower growing functions first. (your answer shall be a sequence of letters, for example “BACDFHGE􏰀”)
(4 min, score = 3)

Solution:

HBDCAEGF

1. What is the maximum possible variance of a random variable taking values in the interval [0, 10]?
(2 min, score = 2)

Solution:

Half is $0$, half is $10$.

$Var(x) = E[X-E(X)]^2 = 5^2 = 25$

1. How many integers $n$ such that $n^n$ is a perfect square are there in range [100: 400]?
(5 min, score = 4)

Solution:

If $n$ is even, $n = 2k$, then $\sqrt{n^n} = \sqrt{n^{2k}} = n^k$, so it’s a perfect square.

If $n$ is odd, $n = 2k+1$, then $\sqrt{n^n} = \sqrt{n^{2k+1}} = n^k\sqrt{n}$, it’s a perfect square if and only if $n$ is a perfect square.

We have:

$10^2 = 100 \qquad 20^2 = 400$

So there are 5 odds that meet the condition, $11^2,13^2,\ldots,19^2$.

Totally, $151 + 5 = 156$ integers.

1. Assume there are three random variables $X, Y, Z$. All pairwise correlations are equal: $corr (x,y)=corr(y,z)=corr(x,z) = r$. What is the range of possible values of $r$? (list a range, like $[-0.3:0.7]$, for example)
(6 min, score = 12)

Solution:

\begin{aligned} \left|\begin{array}{cccc} 1 & r & r \\ r & 1 & r\\ r & r & 1 \end{array}\right| &= 1 -r^2 + r(r^2-r) + r(r^2 - r) \\ &= 2r^3 - 3r^2 + 1 \\ &= (r - 1)^2 (2r+1)\ge 0 \end{aligned}

So the range of possible values of $r$ is $[-1/2, 1]$.

1. Assume there are three random variables $X, Y, Z$. We would like to use one number to describe their relations, just like the pairwise correlation of 2 variables $corr(x,y)$. We need the number to be normalized. Please list the possible mathematical formulas to calculate such number, the more the better.
(6 min, score = 12)

Solution:

$\frac{corr(x,y) + corr(y, z) + corr(x, z)}{3}$

1. Triangle ABC has sides of length 45, 60 and 75. A point $X$ is placed randomly and uniformly inside the triangle. What is the expected value of the sum of perpendicular distance from point X to this triangle’s three sides?
(9 min, score = 10)

Solution:

$45^2 + 60^2 = 75^2$

It’s easy to know, triangle ABC is a right triangle.

\begin{aligned} E[l]&=15 * \frac{1}{6}\int_0^4\int_0^{(12-3x)/4} \left(x+y+\frac{12-3x-4y}{5}\right) dydx \\ &= 15 * \frac{1}{6}\int_0^4\int_0^{(12-3x)/4} \left(\frac{12}{5}+\frac{2x}{5}+\frac{y}{5}\right) dydx \\ &= 15 * \frac{1}{6}\int_0^4 \left(\frac{12+2x}{5} \frac{12-3x}{4}+\frac{1}{10}(\frac{12-3x}{4})^2\right)dx \\ &= 15 * \frac{1}{6}\int_0^4 \left(\frac{3}{10}(24-2x-x^2)+\frac{1}{10}\frac{9}{16}(16-8x+x^2)\right)dx \\ &= 15 * \frac{1}{6}\int_0^4 \left(\frac{81}{10} - \frac{21}{20}x -\frac{39}{160}x^2 \right)dx \\ &= 15 * \frac{1}{6}\left(\frac{81}{10} * 4 - \frac{21}{20}*\frac{4^2}{2} -\frac{39}{160}*\frac{4^3}{3}\right) \\ &= 15 * 1/6 * 18.8 \\ &= 47 \end{aligned}

1. Please list one of your most “strange” or “crazy” idea to predict stock’s return. You can assume you have all available public data and strong computing power. The answer shall be as “strange” as possible.
(6 min, score = 10)

Solution:

Use the stock code to select stocks. If the stock code is a prime number, buy it and hold. The strategy is pretty strange because there should be no useful information in the stock code.

## 参数剪枝和量化（Parameter pruning and quantization）

### 量化与二值化（Quantization and Binarization）

（好奇.jpg，离散值的梯度反传等等怎么搞？找到了个知乎链接，有空看看，估摸着是不一定会看了)

• 二进制网络的精度降低非常严重。
• 当前的二进制方案基于简单的矩阵估计，忽略了二进制在精度损失方面的效果。

### 网络剪枝（Network Purning）

• 利用$l_1$或者是$l_2$正则化通常需要更多的迭代来收敛
• 所有的剪枝条件都一定程度上需要人工来设置网络层的敏感性
• 网络剪枝通常能够降低模型大小但是没有办法提升效率

### 构造结构化矩阵（Designing Structural Matrix）

（好奇.jpg x 2，卷积实际上应该也是一种结构化矩阵，这玩意能不能在受限情况下进行搜索？）

$\mathbf{R}=\text{circ}(\mathbf{r}):=\left[\begin{array}{ccccc} r_{0} & r_{d-1} & \ldots & r_{2} & r_{1} \\ r_{1} & r_{0} & r_{d-1} & & r_{2} \\ \vdots & r_{1} & r_{0} & \ddots & \vdots \\ r_{d-2} & & \ddots & \ddots & r_{d-1} \\ r_{d-1} & r_{d-2} & \ldots & r_{1} & r_{0} \end{array}\right]$

• 结构化约束会使得模型有偏，损害模型的性能（我的角度来看就是做了不该做的假设）

• 很难找到合适的结构化矩阵，当前也缺乏理论指导

## 低秩分解（Low-rank factorization）

• 低秩方法涉及到计算代价昂贵的分解操作，执行起来并不容易。
• 由于不同层有着不同的信息，当前的低秩估计方法是逐层的，因此不能执行全局的参数压缩。
• 比较原始模型， 分解需要额外的再训练去实现收敛。

## 转移/紧致卷积滤波器（Transferred/compact convolutional filters）

CNNs 是参数有效的对于转换的不变性，对于输入图片表示的不变性，而这对于训练深度模型而不导致过拟合是重要的。尽管目前还缺失强理论证明，但是大量的经验事实支持平移不变性和权重共享对于好的预测性能是重要的。 使用转移卷积滤波器去压缩CNN模型的想法受到研究工作启发，它引入了等价理论。让$x$是一个输入，$\Phi(\cdot)$是一个网络层和$\mathcal{T}(\cdot)$是一个转换矩阵。等价性的概念如下所定义：

$\mathcal{T}^\prime(\Phi(x)) = \Phi(\mathcal{T}x)$

• 这些方法能够对于宽度（扁平）的框架（比如VGGNet）能够实现竞争性的性能，但是对于深度的网络（比如GoogleNet，ResNet）效果就不是很好。
• 指导学习的转移假设条件有时太强了，这使得结构对于某些情形是不稳定的。

## 知识蒸馏（Knowledge Distillation）

• 知识蒸馏的方法可以显著降低运算量，但是只能够被用在softmax loss的任务上。
• 只能够从头开始训练，不能够从已有的模型权重当中进行抽取。
• 效果相对于其他方法而言也并不够好。

## 评测指标与数据集

### 评测指标

$M$为模型，$a$为模型所含有的参数数量，$s$为模型的运行时间，大部分工作是采用的平均每epoch的训练时间，但是实际上测试时间也是可以的。利用$M^*$的星号上标来表示压缩后模型的对应指标，通常采用的评价指标有以下几种：

• 压缩比率（compression rate）

$\alpha(M, M^*) = \frac{a}{a^*}$

• 索引空间节省量（index space saving）

$\beta(M, M^*) = \frac{a - a^*}{a^*}$

• 加速比率（speedup rate）

$\delta(M,M^*) = \frac{s}{s^*}$