Joey

COMP5313 Assignment 1 全部 5 个 task 的题解合集 —— Strong/Weak Ties、Link Formation、Structural Balance、Network Bottlenecks、Girvan-Newman。

来源: Assignment 1 (Feedback-only) Solutions.pdf
主题: Longest Increasing Subsequence, uniform random permutation, randomized fingerprinting, communication reduction

这份 feedback-only assignment 有两个独立大题：

1. Problem 1: 随机排列上的 LIS（Longest Increasing Subsequence），包含 Fisher-Yates shuffle、实验估计和理论证明。
2. Problem 2: 文件完整性验证，也就是用很短的随机 fingerprint 判断两个 -bit 文件是否相同。

其中 Problem 1 的一部分明确要求 Python 实现和画图，这些实现细节更像作业实践，不像期末证明题的核心。这里按复习目的处理：代码和画图不展开，只保留算法思想、正确性证明和最终结论。

---

哪些代码部分可以略过

位置	内容	复习时怎么处理
Problem 1(d)	在 Ed 上实现 corrected permutation generator	不写代码，记住 Fisher-Yates 的修正和正确性
Problem 1(e)	对 做 100 次实验并画	不写代码，知道实验在估计随机排列的 LIS 平均长度
Problem 1(f)	画 log-log plot，用 numpy 拟合	不写代码，记住 log-log 斜率给 ，结论约为

期末更值得复习的是：为什么 shuffle 要从 里抽、为什么 LIS 的期望是 、以及随机 fingerprint 为什么能用很少 bit 检测文件是否相同。

---

Problem 1: Random Permutation 上的 LIS

┌─────────────────────────────────────────────────