Joey

COMP5313 Week 11 Tutorial（Network Dynamics）题解，覆盖幂律分布与富者愈富、小世界现象与强弱联系、以及 Chord DHT 的 finger table 构造与 lookup 路由，给出每题完整推理与计算过程。

来源: Assignment 3 (Feedback-only) Solutions.pdf
主题: Hamming ANN/LSH, Knapsack approximation, streaming max coverage, AMS sketch, reservoir sampling

这份 feedback-only assignment 有 5 个问题：

题目	类型	核心内容	复习建议
Problem 1	Programming	实现 Hamming ANN / LSH，并用 ANN Benchmarks 比较性能	PDF 没给理论 solution；实现和 benchmark 不是优先复习重点
Problem 2	Theoretical	Knapsack 的 2-approximation 和 streaming 版本	重点，贪心 + fractional knapsack relaxation
Problem 3	Theoretical	只选 个 items 覆盖尽量多 characteristics 的 streaming approximation	重点，threshold greedy + guessing optimum
Problem 4	Theoretical	用 Tug-of-War / AMS sketch 估计	很重要，streaming sketch + 4-wise independence
Problem 5	Theoretical	不知道 stream 长度时，均匀随机抽 个 items	重点，reservoir sampling

PDF 开头说明：Problem 1 是 programming，Problem 2-5 是 theoretical，并且 solutions 只提供 theoretical questions。 所以下面不会写 ANN Benchmarks 的代码实现，只整理它的任务目标和复习取舍；后面四题会详细写。

---

统一背景与符号

故事背景是 D&D / magical items。

有 个 magical items。第 个 item 写成：

含义：

COMP5270 Assignment 3 题解，补全 Euclidean LSH 证明中被"猫咪打翻咖啡"损坏的 15 处缺失表达式，含完整证明推导、答案汇总与关键知识点。