高级数据结构与算法分析¶
课程介绍¶
注意
此为 2024-2025 秋冬学期课程安排，仅供参考
dyx老师
考核方式¶
project 题目描述
期末考试¶
题型¶
- 判断：13 x 2分
- 选择：20 x 3分
- 程序填空题：2空 x 3分
- 函数题：1 x 8分
程序填空题和函数题重点关注前半学期（Intractability）均为 C 语言
课本¶
笔记¶
个人笔记及 PTA 部分习题详解¶
为什么部分习题有详解呢？因为我不会呀 😭
1 AVL Trees, Splay Trees and Amortized Analysis
2 Red-Black Trees and B+ Trees
3 Inverted File Index
4 Leftist Heaps and Skew Heaps
5 Binomial Queues
6 Backtracking
7 Divide and Conquer
8 Dynamic Programming
9 Greedy Algorithms
10 Intractability
11 Approximation Algorithms
12 Local Search
13 Randomized Algorithms
14 Parallel Algorithms
15 External Sorting
其他¶
Isshiki修's Notebook - 💎 高级数据结构 | Advanced Data Structure
Zhou Jianjun's Notebook - ADS Homework Review
project 分享¶
当时 FDS 有个 Code of Academic Honesty，里面说“【真实案例】学生 A 把自己独立完成的作业代码放到开源社区，第二年被学生 B 抄袭。A 和 B 都应被判作弊”，所以我这里分享一下思路什么的
project 8 MapReduce¶
因为是新东西，弄这个 project 花了好长时间，尤其是环境配置折腾了老半天，但是编写代码的部分比较简单，所以感觉选择这个 project 可以少动脑子，而且可以自学到新东西
- 搭建虚拟机：可以使用 VMware 这个软件
- Hadoop 的配置以及官方 WordCount Jar 文件的使用：黑马程序员大数据Hadoop入门视频教程，适合零基础自学的大数据Hadoop教程
- Java 代码编写：
- 根据这个视频初步了解一下如何创建 Java 工程和编写代码：使用hadoop的Java接口编程进行HDFS文件读取。可能还得自己在网上找找 vscode（或其他 IDE）中使用 Java 工程的教程，比如相关插件的下载，Java 版本的选择，Jar 文件的导出等等
- 根据这个视频了解类似官方 WordCount Jar 文件是怎么写的，怎么导出的：【Task01-统计单词数量】Hadoop-MapReduce编程-idea打包
- 编写代码完成 PTA 上的要求（提示：可以写不止一个 MapReduce 程序，把它们串联起来），可参考文档：Hadoop实现词频统计（按照词频降序排列以及相同词频的单词按照字母序排列）
- 导出自己的 Jar 文件，在虚拟机上运行测试
历年题整理¶
2024-2025 秋冬¶
期中¶
程序填空题 2 答案
a, mid + 1, ra[i] < a[j]ans += j - mid - 1tmp[++cnt] = a[j++]a[i] = tmp[i - l + 1]
期末¶
怎么会错这么多啊 😧
个人感受¶
期末考试一定要把 ppt 的每一页都认真看一遍啊
考试结束后经典：早知道把那个概念看一遍了