COMP5270 Quiz Questions (All Weeks)

Posted on In , Word count in article: 7.2k Reading time ≈ 26 mins.

来源: [[5270.md]]（原始文档）
说明: 本文档整理了 COMP5270 全部 Week 的 Quiz 题目及正确答案。Week 4 缺失，Week 12 仅有标题无内容。
用途: 期末复习、知识点快速回顾

Week 1: 随机变量与期望基础

Question 1

[EN] If is the indicator variable of an event , then is equal to...

[CN] 若 是事件 的指示变量，则 等于……

  • 1
  • 0
  • ✅
  • 1/2

[!note] 知识点 指示变量的期望等于事件发生的概率：。

Question 2

[EN] The worst-case lower bound for comparison-based sorting algorithms doesn't apply to randomised algorithms.

[CN] 比较排序的 最坏情况下界不适用于随机化算法。

  • False ✅
  • True

[!note] 知识点 该下界针对的是决策树模型（基于比较），与算法是否随机化无关。随机化 QuickSort 仍是基于比较的排序。

Question 3

[EN] What type of randomised algorithm is Randomised QuickSort?

[CN] 随机化 QuickSort 属于哪种类型的随机化算法？

  • Both
  • Neither
  • Monte Carlo
  • Las Vegas ✅

[!note] 知识点 Las Vegas：结果总是正确，运行时间是随机的（期望）。
Monte Carlo：运行时间是确定的，结果有一定概率错误。

Question 4

[EN] If a random variable has a well-defined variance and expectation, then

[CN] 若随机变量有定义良好的方差和期望，则

  • ✅

[!note] 知识点 由 ，且 ，所以 。

Question 5

[EN] (Pick the best bound that applies) The expected number of comparisons by Randomised QuickSort is at most

[CN]（选择最紧的上界）随机化 QuickSort 的期望比较次数至多为

  • ✅

Question 6

[EN] For a given input , a randomised algorithm A always gives different answers when given different random strings.

[CN] 对于给定输入 ，随机化算法 A 在不同随机串下总会给出不同答案。

  • False ✅
  • True

[!note] 知识点 随机化算法可能因随机串不同而输出不同，也可能相同（例如 Las Vegas 算法的结果总是正确的）。

Question 7

[EN] We have a much faster polynomial-time randomised algorithm than the best known deterministic algorithm for:

[CN] 对于以下哪个问题，我们已知有多项式时间的随机化算法，比最好的确定性算法快得多？

  • Deciding whether an integer is a prime number ✅
  • Deciding whether a prime number is an integer
  • Factoring an integer into prime numbers
  • Factoring a prime number

[!note] 知识点 质数判定有高效随机化算法（如 Miller–Rabin），但整数分解目前没有已知的多项式时间算法。

Question 8

[EN] Suppose I am given a randomised algorithm A which, given as input an integer , outputs a random (not necessarily uniformly random) English sentence of exactly words. If I run the algorithm twice with input with the same random bits, will I get the same sentence?

[CN] 给定随机化算法 A，输入整数 ，输出一个恰好 个词的随机英文句子。若用相同的输入 和相同的随机比特运行两次，会得到相同句子吗？

  • Yes ✅
  • No
  • That depends on the algorithm

[!note] 知识点 随机化算法的输出由输入 + 随机比特完全决定。若两者都相同，则输出必然相同。

Question 9

[EN] What is a possible limitation to keep in mind when using randomised algorithms?

[CN] 使用随机化算法时需要记住的可能限制是？

  • They are always better
  • They assume access to "good" randomness ✅
  • They're harder to analyse
  • They're usually slower

Question 10

[EN] If the expected running time of an algorithm (on any input of size n) is , then the worst-case running time of that algorithm is always .

[CN] 若算法在任何大小为 的输入上的期望运行时间都是 ，则其最坏情况运行时间总是 。

  • False ✅
  • True

[!note] 知识点 期望时间小不代表最坏情况小。例如：99% 概率 ，1% 概率 ，期望仍是 ，但最坏情况是 。

Week 2: 集中不等式与算法类型

Question 1

[EN] The union bound states that, for events , the probability of is equal to the sum of probabilities .

[CN] 并集界（Union Bound）指出：对事件 ， 等于 。

  • Only if the events are independent
  • True
  • False ✅

[!note] 知识点 Union Bound 给出的是上界：，不是等号。等号仅在事件两两不交时成立。

Question 2

[EN] Markov's inequality applies to every random variable which has a well-defined expectation.

[CN] Markov 不等式适用于所有具有良好定义期望的随机变量。

  • True
  • False: it needs to have a variance
  • False: it needs to be non-negative ✅

[!note] 知识点 Markov 不等式要求随机变量非负：若 ，则 。

Question 3

[EN] It is always possible to convert a Las Vegas algorithm to a Monte Carlo one with similar runtime (but now worst-case).

[CN] 总是可以把 Las Vegas 算法转化为 Monte Carlo 算法，保持相似运行时间（现在是 worst-case）。

  • True ✅
  • False

[!note] 知识点 方法：设定时间阈值，超时后输出任意答案。这样由期望时间得到 worst-case 时间，但结果可能错误。

Question 4

[EN] It is always possible to convert a Monte Carlo algorithm to a Las Vegas one with similar runtime (but now expected).

[CN] 总是可以把 Monte Carlo 算法转化为 Las Vegas 算法，保持相似运行时间（现在是期望时间）。

  • True
  • Not that we know of ✅
  • Yes, but decision problems

[!note] 知识点 Monte Carlo → Las Vegas 通常需要可验证的答案（如决策问题或 NP 类型问题），一般情况我们不知道如何做。

Question 5

[EN] Chebyshev's inequality, when it applies, is always stronger than Markov's inequality.

[CN] 当 Chebyshev 不等式适用时，它总是比 Markov 不等式更强。

  • False ✅
  • True

[!note] 知识点 两者适用于不同场景，没有绝对的强弱之分。Chebyshev 需要方差信息，且在某些距离下 Markov 给出的界更紧。

Question 6

[EN] If there is a Monte Carlo algorithm for a decision problem, with success probability 51%, then there is a Monte Carlo algorithm for this problem with similar runtime (up to constant factors) with success probability 99.999%.

[CN] 若某决策问题有成功概率 51% 的 Monte Carlo 算法，则存在运行时间相似（至多常数倍）且成功概率 99.999% 的 Monte Carlo 算法。

  • True ✅
  • False

[!note] 知识点 通过重复运行并取多数票（majority vote）可指数级提升成功概率。这是概率放大（probability amplification）。

Question 7

[EN] The Randomised Median algorithm seen in class can be converted into a Las Vegas algorithm running in expected linear time.

[CN] 课上讲的 Randomised Median 算法可以转化为期望线性时间的 Las Vegas 算法。

  • False
  • True ✅

[!note] 知识点 Randomised Median 本身的结果可以被验证（检查是否为真正中位数），所以验证后转化为 Las Vegas。

Question 8

[EN] The Chernoff bound and Hoeffding's inequality both give concentration bounds where the error decreases with the distance from the expectation...

[CN] Chernoff 界和 Hoeffding 不等式给出的 concentration bound，其误差随偏离期望的距离……衰减。

  • Exponentially fast ✅
  • Polynomially fast
  • Logarithmically fast

Question 9

[EN] A Monte Carlo algorithm whose output can be efficiently checked for correctness can be transformed into a Las Vegas algorithm with similar running time.

[CN] 若 Monte Carlo 算法的输出可以被高效验证正确性，则可将其转化为 Las Vegas 算法，保持相似运行时间。

  • True ✅
  • Only for decision problems

Question 10

[EN] Concentration inequalities are only used to analyse the running time of algorithms.

[CN] 集中不等式仅用于分析算法的运行时间。

  • True
  • False ✅

[!note] 知识点 集中不等式还可用于分析近似质量、误差界限、采样复杂度等。

Week 3: 球入箱与哈希

Question 1

[EN] The variance of a sum of random variables is always the sum of their variances.

[CN] 个随机变量之和的方差总是等于它们方差之和。

  • True
  • False ✅

[!note] 知识点 仅当变量两两不相关时成立。一般情况下：。

Question 2

[EN] The expected number of collisions when throwing balls into bins uniformly at random with replacement grows as

[CN] 将 个球随机投入 个箱子（有放回），碰撞数的期望增长阶为

  • ✅

[!note] 知识点 碰撞数期望 。

Question 3

[EN] When throwing balls into bins, the expected load of each bin is

[CN] 将 个球投入 个箱子，每个箱子的期望负载为

  • 1 ✅

Question 4

[EN] When throwing balls into bins, the probability to see at least a collision is

[CN] 将 个球投入 个箱子，至少发生一次碰撞的概率为

  • ✅
  • 1
  • 0

[!note] 知识点 生日悖论现象： 时碰撞概率已有常数下界。

Question 5

[EN] When throwing balls into bins, the expected maximum load among all bins is

[CN] 将 个球投入 个箱子，期望最大负载为

  • ✅

[!note] 知识点 这是经典结果： 球 箱，最大负载 whp。

Question 6

[EN] The expected number of balls needed to hit every single of bins at least once (when throwing balls uniformly at random) is

[CN] 期望需要多少个球才能命中每个箱子至少一次（Coupon Collector）

  • ✅

Question 7

[EN] A Binomial random variable with parameters and (i.e., Bin()) behaves roughly like a random variable with...

[CN] 大致 behaves like

  • ... a Poisson(1) distribution ✅
  • ... a Normal(0,1) distribution
  • ... a Bernoulli(1/2) distribution

[!note] 知识点 Poisson 分布是 Binomial 的稀有事件极限：, 时 。

Question 8

[EN] The probability that two balls thrown uniformly and independently into bins both fall in the same bin is...

[CN] 两个球独立均匀投入 个箱子，落在同一箱子的概率为

  • 1/2
  • ✅
  • 0

[!note] 知识点 第一个球任意，第二个球与第一个同箱的概率是 。

Question 9

[EN] If two random variables and are negatively correlated, then we have

[CN] 若 和 负相关（negatively correlated），则

  • We cannot say anything
  • ✅

[!note] 知识点 负相关意味着协方差 ，所以方差和会减小。

Question 10

[EN] The "power of two choices" is...

[CN] "Power of two choices" 是……

  • an ad for a 2-in-1 detergent
  • ... a strategy to distribute balls into bins at random ✅
  • a concentration inequality

[!note] 知识点 每个球选两个随机箱子，放入负载较小的那个。可将最大负载降至 。

Week 5: Min-Cut 与 Karger 算法

Question 1

[EN] Min-Cut is NP-Hard.

[CN] Min-Cut 是 NP-Hard。

  • False ✅
  • True

[!note] 知识点 Min-Cut 是多项式时间可解的（如 Karger 算法、Max-Flow 方法）。

Question 2

[EN] Min-Cut can be solved using calls to a Max-Flow algorithm, where is equal to...

[CN] Min-Cut 可以用 次 Max-Flow 算法调用求解，其中 等于

  • 1
  • ✅

[!note] 知识点 固定一个源点，对另外 个点各做一次 Max-Flow，取最小值。

Question 3

[EN] If is a minimum cut, then Karger's algorithm returns it with probability at least...

[CN] 若 是最小割，Karger 算法返回它的概率至少为

  • ✅

Question 4

[EN] If is a minimum cut, then Karger-Stein's algorithm returns it with probability at least...

[CN] 若 是最小割，Karger-Stein 算法返回它的概率至少为

  • ✅

Question 5

[EN] To achieve constant probability of success, Karger's algorithm runs in time (pick the best that holds):

[CN] 为达到常数成功概率，Karger 算法运行时间为

  • ✅

[!note] 知识点 单次成功概率 ，重复 次得常数成功概率，每次 ，总时间 。

Question 6

[EN] The key idea behind Karger's algorithm is that if is a minimum cut, it is ____ likely to be killed than other cuts because it has ____ edges.

[CN] Karger 算法的核心思想：若 是最小割，它被收缩掉的概率比其它割更_，因为它有更_条边。

  • more/fewer
  • more/more
  • less/fewer ✅

[!note] 知识点 最小割边数最少，所以在随机收缩时被选中的概率相对较小。

Question 7

[EN] Every undirected graph on vertices has ___ many distinct cuts.

[CN] 个顶点的无向图有____个不同的割。

  • ✅

[!note] 知识点 每个非空真子集 定义一个割 ，但 和 是同一割，所以共 个。

Question 8

[EN] The idea behind the Karger-Stein algorithm is that Karger's algorithm makes ____ progress in ___ iterations.

[CN] Karger-Stein 算法的思想是：Karger 算法在_次迭代中取得_进展。

  • good/later
  • good/earlier ✅
  • good/all
  • little/earlier

[!note] 知识点 收缩前期边多，不容易误杀最小割；后期边少，容易误杀。Karger-Stein 用递归来处理后期阶段。

Question 9

[EN] The analysis of Karger's algorithm can be used to immediately show an upper bound on the number of maximum cuts in an undirected graphs.

[CN] Karger 算法的分析可立即推出无向图中最大割数量的上界。

  • True
  • False ✅

Question 10

[EN] Karger's algorithm can be modified to work on weighted undirected graphs.

[CN] Karger 算法可以扩展到加权无向图。

  • True ✅
  • False

Week 6: 哈希表

Question 1

[EN] (Properly designed) hash tables allow for lookups, insertions, and deletions in a data structure, all in...

[CN] 设计良好的哈希表支持查找、插入、删除，时间复杂度均为

  • Worst-case constant time
  • Expected constant time ✅

Question 2

[EN] Compared to the array-based solution to implement a dictionary, a hash table is...

[CN] 相比基于数组的字典实现，哈希表更

  • more space-efficient ✅
  • more randomness-efficient
  • faster

Question 3

[EN] To store a truly random hash function from a universe of size to a space of size , we would need ____ bits.

[CN] 存储一个从大小为 的全宇宙到大小为 的随机哈希函数，需要____比特。

  • ✅

Question 4

[EN] By using a good family of hash functions, we can store elements in a hash table of space complexity without any hash collisions (with high probability).

[CN] 使用好的哈希函数族，可以在空间 的哈希表中存储 个元素而没有任何碰撞（whp）。

  • False ✅
  • True

[!note] 知识点 根据生日悖论， 个元素 空间仍有碰撞概率（虽可用完美哈希，但非普通哈希表）。

Question 5

[EN] By using a good family of hash functions, we can store elements in a hash table of space complexity without any hash collisions (with high probability).

[CN] 使用好的哈希函数族，可以在空间 的哈希表中存储 个元素而没有任何碰撞（whp）。

  • True ✅
  • False

[!note] 知识点 空间 时碰撞概率极低（生日悖论： 个球投入 个箱，期望碰撞 ）。

Question 6

[EN] Assess the following two statements: - By using linear probing to handle collisions in our hash table, we can achieve load factor greater than 1. - By using separate chaining to handle collisions in our hash table, we can achieve load factor greater than 1.

[CN] 判断以下两个陈述： - 线性探测可支持负载因子 > 1 - 分离链接法可支持负载因子 > 1

  • False/False
  • True/True
  • True/False
  • False/True ✅

[!note] 知识点 线性探测需要空位来解决碰撞，负载因子必须 < 1。分离链接法每个桶可挂链表，无此限制。

Question 7

[EN] [Pick the best answer] When handling collisions with linear probing, insertions, lookups, and deletions have expected time complexity depending on the load factor as:

[CN]（选择最佳答案）线性探测处理碰撞时，插入、查找、删除的期望时间依赖于负载因子 为

  • ✅

Question 8

[EN] (Properly implemented) cuckoo hashing gives lookups in _____ constant time, deletions in _____ constant time, and insertions in _____ constant time.

[CN] Cuckoo 哈希的查找、删除、插入时间分别为

  • worst-case/worst-case/expected ✅
  • expected/worst-case/worst-case
  • worst-case/expected/worst-case
  • worst-case/worst-case/worst-case

[!note] 知识点 Cuckoo 哈希查找和删除都是直接定位，最坏 ；插入可能需要重新放置元素链（cuckoo path），期望时间。

Question 9

[EN] Bloom filters are _____ space-efficient than hash tables, but have a small probability of __________ error during lookups.

[CN] Bloom filters 比哈希表更_空间高效，但查找时有小的_错误概率。

  • less/false negative
  • more/false negative
  • less/false positive
  • more/false positive ✅

[!note] 知识点 Bloom filter 用位数组 + 多个哈希函数，空间极小，但可能误判（假阳性：说元素在，实际不在）。

Question 10

[EN] Bloom filters have both insertions and lookups in _____ (pick the most accurate answer)

[CN] Bloom filters 的插入和查找时间均为

  • Worst-case constant time ✅
  • Expected constant time

Week 7: 近似最近邻 (ANN)

Question 1

[EN] We know how to solve the (exact) Nearest Neighbour question over a -dimensional space with query time ____ and space ____.

[CN] 维空间中的精确最近邻查询，查询时间_，空间_。

  • ✅

Question 2

[EN] Typically, for this type of applications we care about large dimension and large dataset , where is _____

[CN] 对于这类应用，我们关心大维度 和大数据集 ，其中 通常____。

  • Much larger than
  • Equal to
  • Much smaller than ✅
  • Comparable to

Question 3

[EN] Suppose the number of points is huge: exponential in the dimension . The known algorithms for the (exact) Nearest Neighbour problem have query time or space complexity that scales ____ with the dimension .

[CN] 若点数 是维度 的指数级，精确最近邻算法的查询时间或空间复杂度随

  • Exponentially ✅
  • Logarithmically
  • Linearly

[!note] 知识点 精确最近邻在高维下遭遇"维度诅咒"（curse of dimensionality）。

Question 4

[EN] The Approximate Nearest Neighbour problem relaxes the Nearest Neighbour problem by...

[CN] 近似最近邻（ANN）放宽 NN 的方式是……

  • Allowing exponential space
  • Allowing a probability of failure
  • Allowing to return a point that might not be the closest to the query ✅

Question 5

[EN] The Johnson-Linderstrauss Lemma allows us to preserve exactly the Euclidean distances between points, but on a much smaller space of dimension only .

[CN] Johnson-Linderstrauss 引理可精确保持 个点之间的欧氏距离，但只需 维。

  • True
  • False ✅

[!note] 知识点 JL 引理是近似保持距离（失真 ），不是精确保持。

Question 6

[EN] The Johnson-Linderstrauss Lemma allows us to preserve approximately the Euclidean distances between points, but on a much smaller space of dimension only .

[CN] JL 引理可近似保持欧氏距离，只需 维。

  • True
  • False ✅

[!note] 知识点 目标维度是 （与点数相关），不是 。

Question 7

[EN] The Johnson-Linderstrauss Lemma allows us to preserve approximately the Euclidean distances between points, but on a much smaller space of dimension only .

[CN] JL 引理可近似保持欧氏距离，只需 维。

  • True ✅
  • False

Question 8

[EN] The Johnson-Linderstrauss Lemma allows us to preserve approximately the Hamming distances between points, but on a much smaller space of dimension only .

[CN] JL 引理可近似保持 Hamming 距离，只需 维。

  • False ✅
  • True

[!note] 知识点 标准 JL 引理针对欧氏距离。Hamming 距离需其它方法。

Question 9

[EN] Locality-Sensitive Hashing uses a type of hash functions which makes collisions more likely when hashing elements close to each other.

[CN] 局部敏感哈希（LSH）使用一类使相近元素更可能碰撞的哈希函数。

  • False
  • True ✅

Question 10

[EN] Using LSH, one can solve the ANN question in Hamming and Euclidean space with expected query time _____ in the number of points , and space _____ in .

[CN] 用 LSH 可在 Hamming 和欧氏空间中解决 ANN，期望查询时间关于 为_，空间为_。

  • exponential/sublinear
  • exponential/sublinear
  • sublinear/sublinear
  • sublinear/nearly linear ✅

Week 8: 数据流算法

Question 1

[EN] The Misra-Gries algorithm allows us to solve the MAJORITY problem in one pass, using space .

[CN] Misra-Gries 算法可用单次遍历、空间 解决 MAJORITY 问题。

  • No ✅
  • Yes

[!note] 知识点 Misra-Gries 解决的是 Frequent Elements（Heavy Hitters），不是 MAJORITY。空间也更大。

Question 2

[EN] In the standard streaming streaming setting, the input comes one element at a time, in _________ order.

[CN] 标准数据流设定中，输入元素以____顺序到达。

  • Uniformly random
  • Arbitrary ✅
  • Sorted
  • Best-case

Question 3

[EN] Most streaming problems can be solved exactly by a randomised algorithm using space .

[CN] 大多数数据流问题可用随机化算法以 空间精确求解。

  • True
  • False ✅

[!note] 知识点 许多数据流问题需要 空间才能精确求解，这是下界。

Question 4

[EN] The Misra-Gries algorithm is ________.

[CN] Misra-Gries 算法是____的。

  • Randomised
  • Deterministic ✅

Question 5

[EN] The Morris Counter algorithm provides an approximate count of the number of non-zero elements in a stream of length using space:

[CN] Morris Counter 用____空间近似统计流中非零元素个数。

  • ✅

Question 6

[EN] The "vanilla" version of the Morris Counter gives an estimate of which has variance ____

[CN] "Vanilla" Morris Counter 给出 的估计，方差为

  • ✅

Question 7

[EN] The "vanilla" Tidemark (AMS) algorithm gives a ____ approximation for the Distinct Elements problem using space . [Select the best that applies]

[CN] "Vanilla" Tidemark（AMS）算法对 Distinct Elements 给出____近似，空间 。

  • additive
  • constant-factor ✅
  • -factor

Question 8

[EN] The "vanilla" BJKST algorithm gives a ____ approximation for the Distinct Elements problem using space . [Select the best that applies]

[CN] "Vanilla" BJKST 算法对 Distinct Elements 给出____近似，空间 。

  • additive
  • -factor ✅
  • constant-factor

Question 9

[EN] The Morris Counter can be made to provide an -factor approximation to the number of non-zero elements in a stream using the ____________.

[CN] Morris Counter 可通过____提供 -factor 近似。

  • Median trick
  • Median-of-means trick ✅
  • Trick-or-treat strategy
  • Mean trick

[!note] 知识点 Median-of-means：将估计分成多组，每组取平均，最后取中位数，降低方差。

Question 10

[EN] The Tidemark algorithm solves the MAJORITY problem in two passes.

[CN] Tidemark 算法用两次遍历解决 MAJORITY 问题。

  • False ✅
  • True

Week 9: Sketching

Question 1

[EN] A sketching algorithm is a streaming algorithm which allows you to _____ results from ____ streams.

[CN] Sketching 算法是一种数据流算法，允许你_来自_流的结果。

  • multiply/different
  • combine/reverse
  • draw/different
  • combine/different ✅

Question 2

[EN] The Misra-Gries algorithm can be seen as a sketching algorithm.

[CN] Misra-Gries 可看作 sketching 算法。

  • No
  • Yes ✅

Question 3

[EN] The Misra-Gries algorithm can be seen as a linear sketching algorithm.

[CN] Misra-Gries 可看作 linear sketching 算法。

  • No ✅
  • Yes

[!note] 知识点 Misra-Gries 不是线性的，不能表示为向量加法形式。

Question 4

[EN] A linear sketch is a subset of sketches where the "combine" operation is _______.

[CN] Linear sketch 中 "combine" 操作是____。

  • (Vector) addition ✅
  • Matrix multiplication
  • Linear-time
  • (Vector) inner product

Question 5

[EN] The CountMin and CountMinSketch both give _______ for the _______ problem [Select the most accurate answer].

[CN] CountMin 和 CountMinSketch 对_问题给出_。

  • sketches/distinct elements
  • sketches/frequency estimation
  • linear sketches/frequency estimation ✅
  • linear sketches/distinct elements

Question 6

[EN] CountMinSketch is _______ than the Misra-Gries algorithm, and uses _____ space.

[CN] CountMinSketch 比 Misra-Gries 更_，且使用_空间。

  • slower/more
  • faster/more
  • faster/more ✅
  • slower/less

Question 7

[EN] CountSketch and CountMinSketch provide qualitatively _______ guarantees for the quality of their output.

[CN] CountSketch 和 CountMinSketch 对输出质量提供____保证。

  • different
  • similar ✅
  • opposite

[!note] 知识点 两者都提供频率估计，但误差形式不同（CountMin 偏上，CountSketch 无偏但有误差方差）。

Question 8

[EN] CountSketch works only in the "cash register" model, where updates can only be positive.

[CN] CountSketch 仅在 "cash register" 模型（只增不减）下工作。

  • True
  • False ✅

Question 9

[EN] CountMinSketch can be generalised to the general "turnstile" model, where updates can be positive or negative and no assumptions are made on the sequence of updates.

[CN] CountMinSketch 可推广到 "turnstile" 模型（增减均可，无序列假设）。

  • True
  • False ✅

[!note] 知识点 标准 CountMinSketch 假设非负更新。Turnstile 模型需要更复杂的 sketch。

Question 10

[EN] In the cash register model, CountMinSketch provides an _____ of the true frequencies.

[CN] 在 cash register 模型中，CountMinSketch 提供真实频率的____。

  • overestimate ✅
  • underestimate
  • unbiased estimate

[!note] 知识点 CountMinSketch 因哈希碰撞只会多计（overestimate），不会少计。

Week 10: 线性规划与随机舍入

Question 1

[EN] Linear Programming is concerned with maximising (or minimising) a ________ function subject to ________ constraints.

[CN] 线性规划关注在_约束下最大化（或最小化）_函数。

  • linear/linear ✅
  • convex/linear
  • arbitrary/linear
  • linear/convex

Question 2

[EN] We have efficient (polynomial-time in the number of variables, constraints, and representation of the problem) algorithms to solve linear programs (LPs).

[CN] 我们有高效（多项式时间）算法求解线性规划（LP）。

  • False
  • True ✅

Question 3

[EN] An Integer Linear Program (ILP) is like an LP, but the objective function is integer-valued.

[CN] 整数线性规划（ILP）与 LP 类似，但目标函数是整数值。

  • False ✅
  • True

[!note] 知识点 ILP 要求变量取整数值，不是目标函数。

Question 4

[EN] We have efficient (polynomial-time in the number of variables, constraints, and representation of the problem) algorithms to solve integer linear programs (ILPs).

[CN] 我们有高效算法求解整数线性规划（ILP）。

  • True
  • False ✅

[!note] 知识点 ILP 是 NP-Hard 的。

Question 5

[EN] Every problem which can be solved in polynomial time can be phrased as an LP.

[CN] 所有多项式时间可解的问题都可表述为 LP。

  • True ✅
  • False

Question 6

[EN] Only NP-Hard problems can be formulated as ILPs.

[CN] 只有 NP-Hard 问题才能表述为 ILP。

  • False ✅
  • True

[!note] 知识点 任何决策问题都可表述为 ILP，包括 P 中的问题。

Question 7

[EN] The optimal solution to the LP relaxation of an ILP typically are not solutions to the original ILP.

[CN] ILP 的 LP 松弛的最优解通常不是原 ILP 的解。

  • False
  • True ✅

Question 8

[EN] Randomised rounding is the general idea to take the optimal solution of an ___ and round its value to integers to get a valid solution to the original ___ while being able to relate its value to that of the ___.

[CN] 随机舍入（Randomised Rounding）的一般思想是：取_的最优解，将其值舍入为整数，得到原_的有效解，同时能将其值与____的值关联。

  • LP/ILP/LP ✅
  • ILP/LP/LP
  • LP/ILP/ILP
  • ILP/LP/LP

Question 9

[EN] The LP relaxation + randomised rounding algorithm for Max-SAT seen in class gives a ____-factor approximation (in expectation).

[CN] 课上讲的 LP 松弛 + 随机舍入算法对 Max-SAT 给出____近似比（期望）。

  • ✅
  • 0.878
  • 1/2
  • 3/4

Question 10

[EN] The LP relaxation + randomised rounding algorithm for Min-CUT seen in class gives a ____-factor approximation (in expectation).

[CN] 课上讲的 LP 松弛 + 随机舍入算法对 Min-Cut 给出____近似比（期望）。

  • 1/2
  • 1 ✅
  • 3/4

[!note] 知识点 Min-Cut 的 LP 松弛 + 随机舍入实际上是精确算法，近似比为 1。

Week 11: 分布学习与测试

Question 1

[EN] In learning and testing distributions, we typically assume the probability distribution we get i.i.d. samples from is over a _______ domain.

[CN] 分布学习与测试中，我们通常假设从概率分布 获得的 i.i.d. 样本定义在____域上。

  • Unknown
  • Continuous
  • Discrete ✅

Question 2

[EN] The total variation (TV) distance corresponds to the distance between the probability mass functions.

[CN] 总变差（TV）距离对应概率质量函数之间的 距离。

  • True ✅
  • False

Question 3

[EN] Total variation distance is ________ and ________.

[CN] TV 距离是_且_。

  • Unbounded/not a metric
  • Unbounded/a metric
  • Bounded/a metric ✅
  • Bounded/not a metric

[!note] 知识点 TV 距离 （有界），且满足度量三公理。

Question 4

[EN] The Data Processing Inequality states that "applying the same function to two random variables cannot ________ their statistical distance."

[CN] 数据处理不等式（DPI）指出：对随机变量 施加相同函数不会____它们的统计距离。

  • Decrease
  • Increase ✅
  • Change

[!note] 知识点 DPI：，处理后的距离不会变大。

Question 5

[EN] Learning the bias of an unknown coin to an additive with probability .99 takes ______ independent coin tosses.

[CN] 以加性误差 、概率 0.99 学习未知硬币的偏差，需要____次独立抛掷。

  • ✅

Question 6

[EN] Testing with probability .99 whether an unknown coin is fair or has bias takes ____ independent coin tosses.

[CN] 以概率 0.99 测试未知硬币是否公平或偏差为 ，需要____次独立抛掷。

  • ✅

Question 7

[EN] Testing with probability .99 whether an unknown coin has bias at most or at least takes ____ independent coin tosses.

[CN] 以概率 0.99 测试未知硬币偏差 还是 ，需要____次独立抛掷。

  • ✅

[!note] 知识点 偏差差距为 （而非 vs 公平），样本复杂度降为 。

Question 8

[EN] Learning an unknown probability distribution (over a known domain of size ) to total variation distance with probability .99 takes _______ independent samples.

[CN] 以 TV 距离 、概率 0.99 学习未知分布 （已知域大小 ），需要____样本。

  • ✅

Question 9

[EN] Testing whether an unknown probability distribution (over a known domain of size ) is the uniform distribution over vs. at total variation distance at least 1/100 from , with probability .99, takes ______ independent samples.

[CN] 以概率 0.99 测试未知分布 （域大小 ）是否为均匀分布 ，或距 TV 距离至少 ，需要____样本。

  • ✅

[!note] 知识点 测试均匀分布只需 样本（碰撞测试），远少于学习的 。

Question 10

[EN] Among all probability distributions over a given domain , the uniform distribution over _________ the collision probability.

[CN] 在所有定义域 上的概率分布中，均匀分布 ____碰撞概率。

  • Minimises ✅
  • Maximises

[!note] 知识点 均匀分布的碰撞概率 最小（最"分散"）。碰撞概率 ，Cauchy-Schwarz 可证均匀时最小。

附录：Week 12

原始文档中 Week 12 仅有标题，无具体内容。

[!tip] 复习建议 - 重点关注标注 [!note] 的知识点 - 对比记忆相似概念（如 Las Vegas vs Monte Carlo, CountMin vs CountSketch） - 注意 在不同上下文中的准确含义 - 分布测试的样本复杂度是常考难点