Joey

COMP5416/COMP4416 Advanced Network Technologies Week 01 讲课总结，整理课程安排与考核规则、分层网络模型 (ISO/OSI 与本课五层模型)、各层职责与典型协议，以及用博弈论分析无线信道竞争的完整推导（纯策略 / 混合策略 Nash Equilibrium、p=2/3 与 p=1/3 的对比）。

INFO5990 final exam practice answer sheet with bilingual English and Chinese model answers.

课程: COMP5270 - Randomness, Probability, and Algorithms 学期: S1 2026 来源: Week 9 Lecture Notes & Tutorial 9 Solutions

---

Part 1: Tutorial 9 详细题解

本部分按官方 Solutions PDF整理，每题含完整题目和逐步展开的详细解答。 注：Tutorial 9 也要求完成 Week 8 的 Problem 3 和 Problem 4（关于 BJKST）。

Tutorial 难度总览

题目	所属部分	难度	复习建议
Problem 1	Warm-up	需读讲义；Bloom Filter ↔︎ CountMinSketch 类比	概念题：理解 AND(bits) = MIN(bits)
Problem 2	Warm-up	不必读讲义；ℓ_p 范数单调性	理解即可：
Problem 3	Warm-up	需读讲义；MG vs CMS 对比	重点：理解优缺取舍
Problem 4	Problem Solving	重要；CS vs CMS 同空间预算	重点：误差比较
Problem 5	Problem Solving	可选；CMS 在 turnstile 模型	理解 Markov 需要非负
Problem 6	Advanced	重要；证明 MG 是 sketching	重点：如何合并两个 MG sketch
Problem 7	Advanced	扩展；CMS 求 ℓ₁ Heavy Hitters	了解思路即可

---

Problem 1: Bloom Filter ↔︎ CountMinSketch 类比

题目: 讨论 Bloom Filter 和 CountMinSketch 之间的平行关系。

题解: