Joey

Posted on Edited on In , Word count in article: 8.7k Reading time ≈ 32 mins.

课程: 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 各需要多少时间。

题解:

Read more »

Posted on Edited on In Word count in article: 3.9k Reading time ≈ 14 mins.

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

Read more »

Posted on Edited on In , Word count in article: 4.6k Reading time ≈ 17 mins.

COMP5313 Large Scale Networks — Lecture 总结

基于 Week 01-12 课程录音转录，涵盖老师讲的所有知识点、考点和重点提示。

Week 01: 课程介绍 & 图论基础

课程信息

  • 讲师：Adrian Chen
  • 考核：Assignment 1 (10%) + Midterm Quiz (10%, MCQ, 闭卷) + Group Project (20%) + Final Exam (60%, hurdle 40%)
  • 期末考试 hurdle：必须拿到 40% 以上才能通过
  • Midterm Quiz：纯选择题，闭卷但可带纸质材料，不能用电子设备
  • 可以使用 AI 工具辅助作业，但不能直接生成答案/报告/代码

课程主题概览

  • Week 2-4：社交网络（strong/weak ties, structural balance, community detection）
  • Week 5-6：信息网络（web graph, HITS, PageRank）
  • Week 7-8：图机器学习（GNN, label propagation）
  • Week 9-10：网络动力学（information cascade, power law, small world model）
  • Week 11：P2P 网络（Chord, CAN）

图论基础概念

  • 图 (Graph)：节点 (vertices/nodes) + 边 (edges/links)，G = (V, E)
  • 无向图 vs 有向图：无向图边是对称的；有向图边有方向
  • 路径 (Path)：节点序列，相邻节点间有边；有向图必须沿方向走
  • 简单路径：无重复节点
  • 环 (Cycle)：起点 = 终点的路径
  • 连通分量 (Connected Component)：最大连通子图
  • 巨型分量 (Giant Component)：远大于其他分量的连通分量；大多数网络只有一个
  • 距离 (Distance)：最短路径长度
  • 直径 (Diameter)：所有节点对中最大的距离
  • BFS (广度优先搜索)：计算从一个节点到所有其他节点的距离
    • BFS 树的性质：边只存在于相邻层之间或同层之间
    • 时间复杂度：O(n + m)
Read more »