Joey

COMP5270 Assignment 2 完整题解，涵盖 Problem 1（Karger 算法枚举最小割）和 Problem 2 (a-f)（Pairwise Independent Hash Functions、图生成、随机化 MaxCut、哈希去随机化、条件期望去随机化、运行时间比较）。

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

---

Part 1: Tutorial 7 详细题解

如果 metric space / ANN / LSH / JL Lemma 这些词还不熟，先看 Part 2 的名词速查，再回来读题解。

本部分按官方 Solutions PDF（Week 7 - Tutorial 7 (Solutions)）整理，每题先给完整题目，再逐步展开；所有结论与官方一致，比官方更细的推导步骤会标注【展开】。

Tutorial 难度总览

题目	所属部分	难度	复习时怎么安排
Problem 1	Warm-up	需读讲义，应该 doable	基础题：exact NN 线性扫描 baseline
Problem 2	Warm-up	需读讲义，应该 doable	基础题：Hamming cube 上空间换查询
Problem 3	Warm-up	需读讲义，应该 doable	概念题：Bloom filter 能否替代 hash table
Problem 4	Problem Solving	；important；tutorial 会讲	重点：baby ANN 推广到 general ANN
Problem 5	Problem Solving	recommended；最后的 bound 技术性强	推荐：Euclidean SimHash LSH 分析
Problem 6	Problem Solving	；quite technical and long	长难题：Jaccard 距离 / MinHash LSH
Problem 7	Advanced	有时间再做；not necessary	扩展：kd-tree

---

Problem 1: Exact NN 的链表实现， 空间与查询

题目: 给出一个针对 Nearest Neighbour 问题的数据结构，使用 的空间，并且 Query 运行时间为 。同时说明它如何动态维护集合 ，Insert 和 Remove 各需要多少时间。

题解:

SpaceX 首日大涨 20% 创史上最大 IPO；NVIDIA Blackwell 在首个 Agentic AI 基准测试中领跑；Standard Chartered 称比特币已触底；OpenAI 推出企业 AI 课程；FFmpeg 发现 21 个零日漏洞。