算法设计与分析(彭攀) 2022秋  课程号:COMP6001P02
2022秋  课程号:COMP6001P02
9.2(4人评价)
9.2(4人评价)
  • 课程难度:困难
  • 作业多少:中等
  • 给分好坏:超好
  • 收获大小:很多
选课类别:基础 教学类型:理论课
课程类别:研究生课程 开课单位:计算机科学与技术系
课程层次:硕士   学分:3.0
课程主页:暂无(如果你知道,劳烦告诉我们!)
简介 最后更新:

Description

  • This course mainly introduces the basics of Randomized Algorithms, Approximation Algorithms, and Distributed Algorithms, so that students can develop algorithmic thinking and the ability to analyze the efficiency of algorithms, and find different approaches for dealing with challenging computational problems.​

(Tentative) Topics

Randomized algorithms

  • Probability review and concentration bounds
  • Las Vegas Algorithms, e.g., randomized quick sort
  • Monte Carlo Algorithms, e.g., primality testing, and matrix multiplication
  • Some other basic randomized algorithms

Approximation algorithms

  • NP-completeness, computational complexity reduction, Cook's theorem, etc
  • Basics of approximation of optimization problems
  • Basic algorithms: approximation algorithms for graph coloring, multi-machine scheduling, packing, traveling salesman, vertex cover, and maximum independent set problems

Distributed algorithms

  • Basics of distributed computing models
  • Basics of distributed algorithms: synchronous and asynchronous network models, leader election, spanning tree construction, broadcast, breadth/depth-first search, shortest path, maximum independent set, and other distributed algorithms

Prerequisites

  • Basic algorithms and data structures, discrete probability, graph theory, and linear algebra

Grading

  • Homework (30%): 6 assignments
  • Participation (5%)
  • Closed book midterm exam (30%)
  • Closed book final exam (35%)

Homework

  • An assignment will be posted on BB (www.bb.ustc.edu.cn) every two weeks. You can directly upload your solution to BB. We highly recommend using Latex for answering your homework(Here is a reference on how to use Latex).
  • Homework late policy. Full credit will be given for solutions turned in on (or before) the due date. 80% credit will be given for one-day (24-hour) late. 60% credit will be given for two-day (48-hour) late. 40% credit will be given for three-day (72-hour) late. NO credit will be given after three days.

Academic Integrity

  • Homework Completion Principle: Students are encouraged to discuss and work in groups on homework problems. However students must state the people they discussed with in the acknowledgement section of their written assignment. Students are not allowed to take detailed notes in any group discussion that will appear verbatim in assignment write-ups. Every student has to turn in answers that are written solely by himself/herself. This course will have zero tolerance for plagiarism. If mutual plagiarism is found, both the plagiarist and the plagiarized will have their grades canceled. Please take the initiative to prevent your homework from being plagiarized by others.

References

排序 学期

评分 评分 4条点评

匿名用户 2022秋
  • 课程难度:困难
  • 作业多少:中等
  • 给分好坏:超好
  • 收获大小:很多
  • 难度:困难
  • 作业:中等
  • 给分:超好
  • 收获:很多

老师是非常好的,特别体贴,不点名,5%平时分直接送给大家,也全程直播可以在bb上在线听。

但是课程内容嘛,体验下来不是特别好,(不用担心分数了,尽力学就行)老师是有认真准备的,但是内容很难,和中文班的不一样之处在于英文班更加强调数学上的证明,涉及到的数学知识非常广泛,比如SDP等等,压力非常大。(压力大?那都是我庸人自扰了)

这学期总共做过6次作业,每次作业3道题,作业的难度非常大,3题想三五天都不一定想的出来。彭老师认为作业是为了开阔大家的知识面,为了给大家进行一个拔高,需要大家检索大量参考资料来完成,如果轻易就能完成了说明没有跳出舒适区,这样也学不到什么知识。我个人赞同彭老师的观点,但是考虑到平时作业会影响到成绩,这么做是否真的妥当有待商榷。(让我担惊受怕一个学期哈哈哈)如果实验室任务繁忙,那这一门课就足以折腾得人痛不欲生。

考试难度不低,有期中期末2次考试,占比分别为30%和35%,虽然比作业要简单一点,但是依然让人压力满满

看到金老师的数据库系统有人评价为难,我个人的体会是这门课的难度要远超数据库系统,所耗费的精力至少是数据库系统的五到十倍。(但是这可是TCS!多花点精力也很正常嘛!)

个人认为这门课算是计院为数不多有含金量的好课了,看得出来老师真的很用心,光参考资料就推荐了6-7本,在课件中也标注了参考书目的章节。要是没有分数的压力,(确实没有分数的压力哈哈哈)我肯定给这门课打满分。但为了自己宝贵的头发和时间考虑,建议大家慎重选择。(不存在的,冲就完事了)

--------------------------------

出分后更新:妈呀老师真的超好,全班只有一个人没有75分,均分87分,中位数88分。给分给这么大方,难一点算什么!彭老师我吹爆!!!

 

(最后修改于 4 0 复制链接
匿名用户 2022秋
  • 课程难度:困难
  • 作业多少:中等
  • 给分好坏:超好
  • 收获大小:很多
  • 难度:困难
  • 作业:中等
  • 给分:超好
  • 收获:很多

 

再补充下,彭老师人在教学上真的非常nice


考试周结尾更新,做个小节,这时候回头看,才有一种“把点连起来”的体会。

老师最后会调一调分,难度也会有所调整,只要别太离谱应该还是能75飘过的。

这门课直到老师讲到近似算法中间一章的时候,这门课才对我稍微友好点,现在回过头来反思,其实就是少了一步“把点连起来”。这门课少不了大量的实例,一旦能跟着老师形成算法思维,收获将非常多。

彭老师是新开的这门课,一开始老师说有英语和数学门槛(主要还是数学)的时候,那时候没有对难度有个较为具体的认知,没太当回事结果就继续跟下去了,所以还是要提醒后来选的同学,门槛,那是真的有门槛,而且需要付出比较多的精力,但收获也正相关。

前半部分学概率算法的时候,一直陷入到case study的问题,那种学不明白+知识串不成网络的感觉真的血崩,但是在后面近似算法经过将近似算法和NP问题联系起来后,才稍稍有了些明白的体会,这时候才感觉稍稍有点收获了。

然而概率算法至今仍然一头雾水,这里面数学真的是我不配了orz,也一直没法形成系统的认识。

即使一开始吐槽这门课好难,有一点我是相信的,国内计算机教育想要走到下一阶段质变,对这种类型的课就更加需要,但黄金时期是在本科安排上(没再多打分还是因为和同类研究生课程相比所需要付出太多精力)。这种类型的课越多,国内计算机教育内卷可能也就能少一点,创造可以变得多一点。

 

 

从课程方方面面,大家都是能感受到彭老师和他的助教们对这门课用心程度,哪怕像我这样一个功利主义者都会承认,这门课仅仅学个大概都会有收获颇丰之感。

在此感谢下彭老师和师兄们为这门课付出的真心。

 

也许之后选这门课的同学们依然会抱怨很难,甚至更难orz。不过还是回到那句话,当你有一天回看将他们连在一起的,才会发现这门课的价值。

 


先说好的:

1. 老师备课什么还是很认真的,而且课程内容也非常硬核;

2. 知识的讲解会看录像也还是能搞懂的,老师上课讲的也算清楚;

 

再说个人不太能接受的,注意仅陈述个人感受:

1. 结合老师的出身,这门课数理方面的要求还是比较高的,喜欢挑战这些难题的同学可能都不是问题;

2. 老师是第一年开课,所以对于课程难度的把握,个人体会真的不太好,而且分数也卡的比较严;

3. 想水过的,把精力投入到其他事情上的慎重吧,这点每个人都有自己的观点。但仅分享下个人对此意见:对于工科生来说,这门课算法理论学的多扎实,从功利角度上来说,在你的简历、面试上体现不出分毫,说不好听的理论造火箭好不好,但市场决定了你面试做不出来题还是白瞎。有些课同样是有难度,但最起码那门课做出来的一些东西你是能反映到简历上作为加分项的。

给其他后来人留个参考,再次强调,仅分享个人意见做参考。

(最后修改于 3 0 复制链接
Doji_zz 2022秋
  • 课程难度:困难
  • 作业多少:中等
  • 给分好坏:超好
  • 收获大小:很多
  • 难度:困难
  • 作业:中等
  • 给分:超好
  • 收获:很多

在上课的时候比较痛苦, 容易在一个个算法问题中溺水想不明白, 但一边复习一边发现整个课程的脉络还是十分清晰的, 从随机算法到近似算法再到分布式算法. 虽然上课教过的问题和具体算法流程大概率考试以后不会记得, 但是对随机算法是个什么东西, 近似算法尝试解决什么问题, 分布式算法是在什么情况下的考量至少有了概念, 个人认为这些认识对计算机相关的学生来说很有必要, 收获还是挺大的.

很多数学证明非常恐怖, 不过仅限于授课阶段, 老师出卷和给分都很友好, 基本涉及到的都是算法流程和一些简单的证明.

2 0 复制链接
Yyeese 2022秋
  • 课程难度:困难
  • 作业多少:中等
  • 给分好坏:超好
  • 收获大小:很多
  • 难度:困难
  • 作业:中等
  • 给分:超好
  • 收获:很多

第一次写点评,冲着老师海底捞月还有助教的认真工作高低得来唠两句

·英文授课确实带来一定的困难,但老师和助教也在积极的改进。这课是目前CS的专硕必修,不管哪个老师的课,核心的算法内容这些的难度都低不了。如果英文不是太糟其实都可以试试,毕竟后面科研啥的英文这一关终归是逃不过的

·作业设置非常好,虽然有一定的难度和工作量,但是受益良多。内容上很多都是课堂内容的延申,鼓励进一步思考理解以及扩展阅读;形式上对于latex这一科研重要工具的学习使用大有脾益

·分数不用担心,这学期全班只有一个缺考的同学没有拿到75。认真做作业然后尽力考试都能拿到够用的分数

·助教非常认真负责,很耐心的讨论和解答问题。有一说一我是第一次见到老师不给答案助教也要自己写作业的课

 

 

1 0 复制链接

彭攀

教师主页: 戳这里

其他老师的「算法设计与分析」课

张曙 9.7 (3) 2024春 2023秋...
未知 10.0 (1) 2022春 2021春...
汪炀, 彭攀 8.2 (5) 2023秋
徐云 9.0 (1) 2024春 2023秋...
徐小华, 彭攀 7.8 (8) 2023秋
汪炀, 徐小华 7.7 (7) 2023秋
黄刘生, 汪炀 7.4 (17) 2022春 2021秋...
王子磊 6.0 (4) 2024春 2023春...
汪炀, 薛吟兴 5.7 (15) 2022秋
尹东 2024春
黄刘生 2022春 2021春...
田野 2021春

彭攀老师的其他课

大数据算法 9.3 (17) 2023春 2022春
算法设计与分析 8.2 (5) 2023秋
算法设计与分析 7.8 (8) 2023秋