Algorithms: Design and Analysis, Part 2
开始时间: 04/22/2022
持续时间: 6 weeks
课程主页: https://www.coursera.org/course/algo2
课程评论: 4 个评论
评论课程
关注课程
课程详情
In this course you will learn several fundamental principles of advanced algorithm design. You'll learn the greedy algorithm design paradigm, with applications to computing good network backbones (i.e., spanning trees) and good codes for data compression. You'll learn the tricky yet widely applicable dynamic programming algorithm design paradigm, with applications to routing in the Internet and sequencing genome fragments. You’ll learn what NP-completeness and the famous “P vs. NP” problem mean for the algorithm designer. Finally, we’ll study several strategies for dealing with hard (i.e., NP-complete problems), including the design and analysis of heuristics. Learn how shortest-path algorithms from the 1950s (i.e., pre-ARPANET!) govern the way that your Internet traffic gets routed today; why efficient algorithms are fundamental to modern genomics; and how to make a million bucks in prize money by “just” solving a math problem!
课程大纲
Weeks 1 and 2: The greedy algorithm design paradigm. Applications to optimal caching and scheduling. Minimum spanning trees and applications to clustering. The union-find data structure. Optimal data compression.
Weeks 3 and 4: The dynamic programming design paradigm. Applications to the knapsack problem, sequence alignment, shortest-path routing, and optimal search trees.
Weeks 5 and 6: Intractable problems and what to do about them. NP-completeness and the P vs. NP question. Solvable special cases. Heuristics with provable performance guarantees. Local search. Exponential-time algorithms that beat brute-force search.
课程评论(4条)
|
0
|
大吃一惊异
2014-08-09 16:08
0 票支持; 0 票反对
吸取了第一部分的教训，放弃了Python改用Go。运行效率唰唰唰得上去了，再也不(mei)用(you)担(jie)心(kou)程序跑个几分钟了。这门课感觉quiz明显比编程难。编程作业基本上实现了课上讲过的算法就能比较轻松得的到结果了（即使是那个tsp的boss battle随便写写也能几十秒跑完），quiz没思路的时候那叫个难受啊。上完之后意犹未尽，继续钻研还是要自己看书啊。
|
|
0
|
老爷不要啊啊啊
2014-07-27 14:52
0 票支持; 0 票反对
Part2学了快一年了, 唯一一门尽力了还是跌破90分的课. 确实是相当的困难, 第一次学习能吸收的相当有限. TSP最好使用课上没有讲解的剪枝, 对所给的data set运行时间是不可接受的. 我时间来不及, 几乎放弃, 结果一个南洋理工的计算学博士单骑杀出, 给出了一个贪心的思路, 救我于水火, 神奇般的只要一瞬间(Python). 之后2SAT也只稍逊一筹, 已经用了SCC去优化, 3小时下来也只跑出5个结果.
最后的期末只拿了78%, 总分跌破90收场. 这次经历让我对另一门离散优化变得相当敬畏.
|
|
0
|
wzyer
2013-05-17 08:15
0 票支持; 0 票反对
很好的课程。不像Princeton的那个，那个更注重基础知识，而这个更注重思路。确实老师语速很快，不过听起来很清晰。学这门课主要就是要跟着老师的思路一块思考。很多作业也非常需要动脑子，较有挑战性的一门课。
|
|
0
|
wsz-bupt
2013-05-13 22:55
0 票支持; 0 票反对
老师讲解很详细，前因后果解释得很清楚，既有深度游有广度，讲完一个算法之后还会讨论一些尚未解决的问题，并给出一些经典的参考文献。不过老师讲课的语速非常快，不习惯的话可能会稍感不适，但是个人非常喜欢。部分Quiz会比较有挑战性，不过也很具有启发性。老师的个人主页：http://theory.stanford.edu/~tim/
|
