数据结构与算法分析

DSAA，很多同学进计系的第一关。至少唐老师的某一句话说得很对——这门课的内容你会在未来求职刷算法题时再次见到。

这门课讲了很多基础的算法知识和数据结构，从线性的数组、链表到非线性的树、图，从排序算法到最小生成树。如果你在高中达到了普及+/提高这个层次，那么飘过这门课应该是没问题的！

如果零基础也没关系，算法的世界一样欢迎你。但是——这是一门需要你夯实基础的课，你必须认真学习，在课后反思老师上课讲的内容。由于唐老师默认你会第二遍学这门课，他会讲一些你听不懂的东西，没关系你先记着就好，记不住也没关系。课后对于没有理解的定义和模板请一定去搜索相关的文章（各个博客、知乎等都有很多专门讲相关知识的文章），并总结出属于自己的代码模板。少用或者不用gpt，至少这门偏理的课不要。

一个好的代码习惯是：把你的代码尽量模块化，出了错误可以快速定位到具体的算法位置，而确认其他部分没有任何问题。比如下面的二分答案代码，理论上你只需要修改 check 部分：

bool check(int x){
	//check if your x is legal
}

int main(){
	
	int l=...,r=...,ans=-1;
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid))ans=mid,...;
		else ...;//modify your l or r into mid+1 or mid-1
	}
	if(ans!=-1)//then you get your answer
}

我很推荐大家在这门课多和别人交流，计系初来乍到，可以多多交流（线上&线下！），找一找一起学习的伙伴，计系的好日子还在后头呢。

祝你的思维方式和代码能力取得长足进步！

好歹我在 OJ lab 的排名也蛮高的，所以时刻欢迎后来的同学咨询！在这里留下联系方式 qq1351591429（不许开我盒😠）

最后留一句和我一节课的同学们知道的谜语吧——树德之窗绝赞征稿中！「树德之窗」栏目长期征稿中！

upd on 2025/1/9:

总绩100.0/100.0。第一眼还以为是作业分没看到（）那么这门课大家有问题欢迎咨询！

更新一点关于quiz和考试的内容。

总共有quiz1，midterm，quiz2和final四次考试。quiz1会比较严格，一是给大家见识一下算法的魅力（迫真），二是前面讲的东西比较少，于是会选择考得深入一些，在这一部分推荐掌握线性查找第k大（快速排序的变式）以及唐老师课上提到的思考题；midterm开始就得准备捞人了（笑），在quiz1的基础上要好好复习字符串相关的知识，不会考太拔高的题目，但是一定会很考察你对基础模板的理解；quiz2纯捞人，写名字就有50分，但是说到底这里的知识还是蛮重要，树的概念需要好好消化；final回归了quiz1的体感，主打量大管饱，允许你带cheating paper，但是一是大部分考察的和你cheating paper上的模板没什么关系，二是题量不支持你很不熟练地去大幅度查找cheating paper，这里主要考察的是大家的熟练度，基础不牢地动山摇，写啊写啊写啊。

唐老师为了大家的均绩会有不少捞人送分的时候，比如quiz2和其他bonus。这学期没有程序设计校赛（按往年说法，人均提2分总绩），在final里加了bonus题目，不过写完的人甚少啊。

对于考试题目中算法书写的练习，我推荐大家去写一些lab课习题的题解。把自己的思路好好梳理下来，也培养一个自己的书写习惯。优质的题解笔记可以参考网上的博客文章，学习他们的行文结构，对一些术语的准确把握，以及对时间复杂度的分析。

不管问问题还是给别人讲解，最好都能尝试向对方说明你的思路。小黄鸭大法好啊，很多时候你一面说一面就知道自己错在哪里；同时，真正把思路梳理清晰，能够引导他人，也才是你真正达到了这个水平的证明。

这门课可能会给不少计系的新同学一个下马威，但是请大家不要气馁，你所收获的远比绩点更多。同时，你和数据结构与算法分析的缘分也一定不会止于这门课，希望你能在未来的计系生活中巩固你的收获，并找到属于你自己的各种答案。

唐老师的风格算是很有特点的，授课内容讲的也算足够清晰，理解课程内容听课就够了。

Lab作业共十次占20分，还有一次bonus Lab 2分(仅能补Lab作业分)。作业通过ACM Online Judge布置，和java A的OJ不同，只要有一个测试点过不了就一分没有，并且不展示报错信息，在debug层面难度就更上一层楼了(不过可以找温柔善良的sy姐姐帮忙还是挺好的awa)。Lab题对于没有竞赛基础的同学，有些题还是颇有难度，例如本学期比较恶心的两道题是块状链表和平衡树，实际上写不出来也不必死磕，bonus Lab的难度都很低(至少这学期是这样)，可以抵消3,4道前面太难的题，何乐而不为呢？作为参考，我有微弱的算法基础，每次Lab死磕做完的耗时大概在4~30小时不等，平均用时12h附近？

考试和上课所讲直接重合的部分有，但不是全部，会出一些比较伤脑筋的算法设计题，现场很难想出最优解，想不出最优解唐老师就会给你这道题打个亲切的六折，还是挺痛的。

考试复习的建议就是看看课件，长期有精力的话可以看看算法导论对应章节的练习题，唐老师似乎很喜欢这本书，上面的题解也还是挺巧妙，但也挺伤脑筋的。

给分不予评价，人不行不能怪路不平。毕竟是计算机系必经之课，也是很基础很重要的内容，学到的东西的重要性比成绩要重要多了。

挺好的课，虽然总评卡B

推荐选沈老师的实验课，讲的每道题都很清晰透彻，绝对值得高昂的选课积分。

但是，如果只跟着实验课做题的话，感觉最后还是很难自己写出一道题，因为有很多细节如果只听一遍只是知道有这个问题，但不知道为什么也想不出来要这么处理。并且对于每个题板只练一遍确实是有点少，如果有时间的话还是推荐大家自己找点题做，否则很可能像我一样所有实验题都做了但在考试时很难想出思路。

可能是本学期教学周调整的问题，导致期末前（图与树）进度飞快，有点跟不上，因此这里还是有必要预习的，对理解有一定帮助。

另外，建议大家仔细留意课程邮件。quiz1曾经在课上说是开卷，但是在考前发邮件改成了闭卷，没看到被坑了一下。

总体来看，学完这门课确实可以对算法有一些基础的了解，并且解算法题还是挺有意思的。