## Algorithms: Design and Analysis, Part 1

 所在平台: CourseraArchive 课程类别: 计算机科学 授课老师： Tim Roughgarden

#### 课程详情

In this course you will learn several fundamental principles of algorithm design. You'll learn the divide-and-conquer design paradigm, with applications to fast sorting, searching, and multiplication. You'll learn several blazingly fast primitives for computing on graphs, such as how to compute connectivity information and shortest paths. Finally, we'll study how allowing the computer to "flip coins" can lead to elegant and practical algorithms and data structures. Learn the answers to questions such as: How do data structures like heaps, hash tables, bloom filters, and balanced search trees actually work, anyway? How come QuickSort runs so fast? What can graph algorithms tell us about the structure of the Web and social networks? Did my 3rd-grade teacher explain only a suboptimal algorithm for multiplying two numbers?

#### 课程大纲

Week 1: Introduction.  Asymptotic analysis including big-oh notation.  Divide-and-conquer algorithms for sorting, counting inversions, matrix multiplication, and closest pair.

Week 2: Running time analysis of divide-and-conquer algorithms.  The master method.  Introduction to randomized algorithms, with a probability review.  QuickSort.

Week 3: More on randomized algorithms and probability.  Computing the median in linear time.  A randomized algorithm for the minimum graph cut problem.

Week 4: Graph primitives.  Depth- and breadth-first search.  Connected components in undirected graphs.  Topological sort in directed acyclic graphs.  Strongly connected components in directed graphs.

Week 5: Dijkstra's shortest-path algorithm.  Introduction to data structures.  Heaps and applications.

Week 6: Further data structures.  Hash tables and applications.  Balanced binary search trees.

#### 课程评论(5条)

 0 sonach 2014-12-05 22:54 0 票支持; 0 票反对 非常赞，对思路的讲解非常到位！
 1 大吃一惊异 2014-06-22 02:16 1 票支持; 0 票反对 Another back to basics review of CS fundamentals. 这课是上完了Sedgewick的数据结构接着看的。和Sedgewick不同的是，他给出的证明比较多，而implementation detail通常会略过。编程作业非常好得illustrate了高效算法的作用。用比较蠢的算法可能得让机器死磕个几个小时，但是换上了efficient algorithm就是(sub)second出结果。我实现的时候都是用的Python，开始用的CPython但是第四个作业光read input就花了十几秒，用了PyPy两秒就读完了。
 2 超級現實的超現實理想主義者 2013-10-31 17:33 2 票支持; 0 票反对 背景： 上这门课的之前从来没学过编程，编程是现学的，用的是这门课：https://www.coursera.org/course/programming1 这门课要求的数学背景其实不高，几乎没用到多少微积分的知识，线性代数也只提到过一点，而且也是很简单的矩阵乘法(介绍了Strassen Algorithm，但没有在作业和考试中体现)， 需要一些概率论的知识，但最重要的是清楚数学证明的方法，尤其是反证法和数学归纳法。 内容： 课程内容很厚实，虽然讲师Tim Roughgarden的授课方式和课件都很粗旷，但是如果仔细研究他的授课就会发现他讲的东西非常精确，几乎没有疏漏，我是在几乎没看教材只听课件的情况下把这门课过掉的。 课程推荐了几本教材都很经典，包括国人熟知的《算法导论》(CLRS)，这门课借鉴下列两本教材的比重比较大： DPV - Dasgupta, Papadimitriou, and Vazirani, Algorithms KT - Kleinberg and Tardos, Algorithm Design 其中DPV这本完全免费，在UC Berkeley网站上就有，写的非常通俗易懂而且只有300多页，极力推荐。这个是本书的官方地址：http://www.cs.berkeley.edu/~vazirani/algorithms/all.pdf 作业： 1.选择题难度不高，很多内容只要认真听课就能做出来。比较突出的是六道编程题。 2.编程题不限定语言，每道题目给你一个file的数据同时给你相应的要求，只要你符合题目的要求把这些file数据结果跑出来，把答案上交就行了。至于用什么语言，运行效率如何一概不论 3.期末考有一部分题目直接来自之前作业的选择题， 只要前面的作业认真做课认真听，通过是没什么问题的 4. 作业中印象最深的是第三周和第四周的编程题，第三周的题目是Minimum Cut, 第四周是Kosaraju's Strongly-Connected Component, 尤其是第四周，题目难不说，数据还给的很变态，好不容易花了三天时间写出一个正确的算法因为数据量太大（70M多）电脑直接跑崩了（我用Python），只好放弃。 社区： 论坛很活跃，有什么问题很快就能有人解答，最给力的是有很多活雷锋给出各种test,给我测试代码提供了不少帮助 。 顺便说一下，第二第三周的时候Jeff Dean乱入社区，还给我留了言（大神也上基础课啊） 感受： 这门课对我的影响非常大，直接改变了我的思维方式，并且为日后的学习打下了很好的基础。 据说有不少人因为他的语速和板书觉得这门课不好而放弃这门课，我的建议是：千万别！ Don't judge a book by its cover! Tim的语速是有点快，但是发音和里面的内容都非常清晰，我的英语听力也是在这六周里突飞猛进的。（现在听MOOC已经习惯1.5倍速了）
 1 ototsuyume 2013-06-07 18:28 1 票支持; 0 票反对 这门课一个值得吐槽的地方就是ppt写得太潦草了。值得一提的是编程作业的运算量很大，假如用python这种语言去做作业又不留意哪些地方开销很大的话会导致跑很长时间才能跑出结果。这变相是强迫你去优化程序避免在大运算量的时候出错而难以debug。就算是大学学过算法的仍然值得一试。
 1 超級現實的超現實理想主義者 2013-05-14 23:11 1 票支持; 0 票反对 講師是斯坦福副教授。之前為了這門課買了很多書，到後面發現一本也用不到。老師語速極快，但是說話的內容異常準確，學習的過程中一旦發現有模糊的點，都能在他的隻言片語中找到解答。這也是我個人的第一門CS課程，在做第一周的作業的過程中掌握了python，寫的第一段代碼就是merge-sort(split inversion)。作為一個純文科生，如果沒有這個平台我想是不可能有機會完成這樣的跨越，所以這門課對於我來說意義非凡。如果要說缺點的話，就是太難了，掉了不少頭髮。。。

#### 课程简介

In this course you will learn several fundamental principles of algorithm design: divide-and-conquer methods, graph algorithms, practical data structures (heaps, hash tables, search trees), randomized algorithms, and more.