Advanced Data Structure & Algorithm Analysis
Table of Contents#
- ADS 01 AVL Trees, Splay Trees and Amortized Analysis
- ADS 02 Red-Black Trees and B+ Trees
- ADS 03 Inverted File Index
- ADS 04 Leftist Heaps and Skew Heaps
- ADS 05 Binomial Queue
- ADS 06 Backtracking
- ADS 07 Divide and Conquer
- ADS 08 Dynamic Programming
- ADS 09 Greedy Algorithm
- ADS 10 NP-Completeness
- ADS 11 Approximation
- ADS 12 Local Search
- ADS 13 Randomized Algorithms
- ADS 14 Parallel Algorithms
- ADS 15 External Sorting
- Final
Info#
Advanced Data Structure & Algorithm Analysis
- 代码：CS2045M
- 学分：4.0
- 学期：2024 秋冬
- 教师：陈昊
- 教材：Introductin to Algorithms, 3rd Edition
Grading Policy
Warning
每位老师的评分标准可能不同，仅供参考！
-
Discussions 10 可能的加分
-
Research Project + Peer Review 30 8 选 2，每多做一个加 2 分
- 报告 20
- 会留 2 周时间
- 展示 6
- 需要报名，一共 24 次，20 组
- 压缩展示时间
- Peer Review 4 及时给别人打分
- Pr 给分不算成绩，只有 TA 的打分有效
- 打分不认真会扣分，每次打分好的可能获得加分
- 报告 20
- MidTerm 10 斩杀 40 分
- 钉钉群好的提问和回答都可能加分
- Final 40
Tips#
这份笔记并不完整！
- 本笔记基本涵盖了所有课程内容，但无法保证完整性和正确性
- 每章节笔记末尾有部分 pta 题目的订正/思路，由于课程要求，没有任何源码
- 含有部分期末复习笔记
- ADS Cheat Sheet 是一份并不完整的 Cheat Sheet，其中的 Complexity Class 和 Approximation 部分可能有很多错误
- ADS Cheat Sheet Dynamic Programming 整理了部分动态规划内容，笔者认为对期末复习有一定帮助，毕竟期末函数题基本都是 dp
- ADS Final Questions 是历年卷里一些错题的订正/思路，也不保证正确，欢迎大家来讨论和修正
Useful Links