高级算法 (Spring 2026)/大作业: Difference between revisions
Jump to navigation
Jump to search
Liumingmou (talk | contribs) No edit summary |
Liumingmou (talk | contribs) No edit summary |
||
| Line 2: | Line 2: | ||
**你需要尽可能详细地解释：该论文解决了什么问题，该问题为什么重要（或者提出了什么技术，该技术为什么重要），该问题有什么相关研究（包括该论文提到的，和没提到的，以及在该论文发表之后的新的相关研究），为了解决该问题该论文提出了什么技术，该技术背后的直觉是什么，该技术有什么非凡之处厉害之处。 | **你需要尽可能详细地解释：该论文解决了什么问题，该问题为什么重要（或者提出了什么技术，该技术为什么重要），该问题有什么相关研究（包括该论文提到的，和没提到的，以及在该论文发表之后的新的相关研究），为了解决该问题该论文提出了什么技术，该技术背后的直觉是什么，该技术有什么非凡之处厉害之处。 | ||
**最后尽可能详细地（以一个挑剔严谨的、没有读过该论文的同学可以通过阅读你的 review 来轻松地弄明白、来轻松地验证为标准）解释该技术是如何实现的，如何证明该技术的正确性和优越性。 | **最后尽可能详细地（以一个挑剔严谨的、没有读过该论文的同学可以通过阅读你的 review 来轻松地弄明白、来轻松地验证为标准）解释该技术是如何实现的，如何证明该技术的正确性和优越性。 | ||
* 结果分数30%，过程分数70%. 必须使用 Notion / Overleaf / Google Docs / Word Online / Github 等在线的有版本历史的工具。(如需使用 overleaf student plan | * 结果分数30%，过程分数70%. 必须使用 Notion / Overleaf / Google Docs / Word Online / Github 等在线的有版本历史的工具。(如需使用 overleaf student plan 这样的付费服务可以向老师申请，老师予以报销。 notion education plus 是免费的。） | ||
**教师和助教应能够看到论文从资料收集、逐渐理解、观点形成、草稿撰写到反复修改的过程。如果记录不完整会扣除过程分。没有记录视为作弊。不接受截止日前一次性上传完整论文作为有效过程记录。 | **教师和助教应能够看到论文从资料收集、逐渐理解、观点形成、草稿撰写到反复修改的过程。如果记录不完整会扣除过程分。没有记录视为作弊。不接受截止日前一次性上传完整论文作为有效过程记录。 | ||
**必须开放可以随时在线访问的版本历史供教师或助教检查，老师会在你们撰写的过程中偶尔查看你们的进展。 | **必须开放可以随时在线访问的版本历史供教师或助教检查，老师会在你们撰写的过程中偶尔查看你们的进展。 | ||
Revision as of 01:37, 6 June 2026
- 至多四人一组，从以下论文中选择一篇，撰写一篇 review，中英文不限。
- 你需要尽可能详细地解释：该论文解决了什么问题，该问题为什么重要（或者提出了什么技术，该技术为什么重要），该问题有什么相关研究（包括该论文提到的，和没提到的，以及在该论文发表之后的新的相关研究），为了解决该问题该论文提出了什么技术，该技术背后的直觉是什么，该技术有什么非凡之处厉害之处。
- 最后尽可能详细地（以一个挑剔严谨的、没有读过该论文的同学可以通过阅读你的 review 来轻松地弄明白、来轻松地验证为标准）解释该技术是如何实现的，如何证明该技术的正确性和优越性。
- 结果分数30%，过程分数70%. 必须使用 Notion / Overleaf / Google Docs / Word Online / Github 等在线的有版本历史的工具。(如需使用 overleaf student plan 这样的付费服务可以向老师申请，老师予以报销。 notion education plus 是免费的。）
- 教师和助教应能够看到论文从资料收集、逐渐理解、观点形成、草稿撰写到反复修改的过程。如果记录不完整会扣除过程分。没有记录视为作弊。不接受截止日前一次性上传完整论文作为有效过程记录。
- 必须开放可以随时在线访问的版本历史供教师或助教检查，老师会在你们撰写的过程中偶尔查看你们的进展。
- 小组成员尽量保留阅读笔记、草稿和修改记录，需在设法留下各自贡献的痕迹。
- 有不懂的地方允许咨询AI帮助理解，或者求助AI帮助查询信息，但是不接受AI代写。需将AI使用记录放入版本历史中一并以可追溯的方式提交。
- 教师或助教可能在提交后随机抽取小组进行口头检查。每位成员都需要解释自己负责的内容、论文的核心论点、主要参考文献、修改过程以及 AI 工具的使用情况。若学生无法解释提交内容，或过程记录与最终文本严重不符，将被视为学术诚信风险，并影响成绩。
- Succinct dynamic dictionaries and trees
- On Data Structures and Asymmetric Communication Complexity
- A Hash Table Without Hash Functions, and How to Get the Most Out of Your Random Bits
- Lower bounds on Locality Sensitive Hashing （很短，但是你需要解释其中的傅里叶分析）
- Data structures meet cryptography: 3SUM with preprocessing
- Optimal resizable arrays
- Tiny Pointers
- How to Approximate A Set Without Knowing Its Size In Advance
- Succinct Filters for Sets of Unknown Sizes
- Succincter. M Patrascu. 2008
- Changing base without losing space
- Unifying the Landscape of Cell-Probe Lower Bounds
- Optimal Space Lower Bounds for all Frequency Moments
- Tight Lower Bounds for the Distinct Elements Problem
- On the Cell Probe Complexity of Dynamic Membership
- External Memory Priority Queues with Decrease-Key and Applications to Graph Algorithms
- An Improved Distributed Algorithm for Maximal Independent Set
- Breaking the [math]\displaystyle{ O(n^2) }[/math] bit barrier: Scalable byzantine agreement with an adaptive adversary
- Simple Contention Resolution via Multiplicative Weight Updates
- Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps
- What Cannot Be Computed Locally!
- Impossibility of Distributed Consensus with One Faulty Process
- 获取论文原文也是作业的一部分。
- 需要在review中注明参与完成 review 的每个同学的贡献。
- 到南大表格填写表格来认领论文。有问题可以问老师或者助教。