[资料] [名校在线课程系列] MIT Introduction to Algorithms [复制链接]

Julianlod
UID：2688193

荣誉版主

Rank: 9 Rank: 9 Rank: 9

声望: 728
寄托币: 21645
注册时间: 2009-8-25
精华: 12
帖子: 340

电梯直达

楼主

发表于 2011-3-7 21:38:53 |只看该作者 |倒序浏览

本帖最后由 Julianlod 于 2011-3-7 21:49 编辑

Introduction to Algorithms

Cover of 6.046J textbook, Introduction to Algorithms, Second Edition, by Cormen, Leiserson, Rivest, and Stein. (Image courtesy of MIT Press.)

Course Description

This course teaches techniques for the design and analysis of efficient algorithms, emphasizing methods useful in practice. Topics covered include: sorting; search trees, heaps, and hashing; divide-and-conquer; dynamic programming; amortized analysis; graph algorithms; shortest paths; network flow; computational geometry; number-theoretic algorithms; polynomial and matrix calculations; caching; and parallel computing.

About Instructor

Erik Demaine

Erik Demaine is an Esther and Harold E. Edgerton Professor and Associate Professor in the department of electrical engineering and computer science, and a member of the Theory of Computation group in the Computer Science and Artificial Intelligence Laboratory, at the Massachusetts Institute of Technology. He joined the faculty in 2001, and became an Associate Professor in 2005. He received his PhD in 2001 and Math in 1996 at University of Waterloo, and his BSc in 1995 at Dalhousie University.

Demaine's research interests span much of theoretical computer science and mathematics, in particular with connections to algorithms. Major research foci include discrete and computational geometry (particularly folding and unfolding of linkages, paper, polyhedra, and proteins), advanced data structures, graph algorithms, and recreational algorithms (such as the complexity of combinatorial games).

课程内容

01 算法分析 (Insertion Sort, Mergesort)
【观看视频】

02 递归,分治法,主定理 (Recurrences Substitution, Master Method)
【观看视频】

04 快速随机排序 (Quicksort, Randomized Algorithms)
【观看视频】

06 Order Statistics, Median
【观看视频】

07 Hashing, Hash Functions
【观看视频】

08 Universal Hashing, Perfect Hashing
【观看视频】

09 Relation of BSTs to Quicksort
【观看视频】

11 Augmenting Data Structures
【观看视频】

12 Skip Lists
【观看视频】

13 Amortized Algorithms, Table Doubling, Potential Method
【观看视频】

14 Competitive Analysis: Self-organizing Lists
【观看视频】

15 Dynamic Programming, Longest Common Subsequence
【观看视频】

16 Greedy Algorithms, Minimum Spanning Trees
【观看视频】

17 Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search
【观看视频】

18 Shortest Paths 2
【观看视频】

19 Shortest Paths III: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson
【观看视频】

22 Advanced Topics
【观看视频】

23 Advanced Topics (cont.)
【观看视频】

24 Advanced Topics (cont.) 2
【观看视频】

转帖自课乐网

相关帖子

欢迎大家光临计算机版
希望广大的CSer们都来计算机版交流
欢迎2011Fall的CS applicant将今年的Offer/AD发布在[2011Fall] CS申请AD/OFFER龙虎榜
Julian的资料分享集合贴（1月8日更新）

回应
0

使用道具举报

Julianlod
UID：2688193

荣誉版主

Rank: 9 Rank: 9 Rank: 9

声望: 728
寄托币: 21645
注册时间: 2009-8-25
精华: 12
帖子: 340

沙发

发表于 2011-3-7 21:54:02 |只看该作者

Useful References 参考书目

1. Aho, Alfred V., John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Reading, MA: Addison-Wesley, 1974. ISBN: 0201000296.
The classic text, but it lacks topics in network flows and linear programming, as well as more recent algorithms.

2. Data Structures and Algorithms Reading, MA: Addison-Wesley, 1983. ISBN: 0201000237.
Revised and more elementary version of the first six chapters of The Design and Analysis of Computer Algorithms.

3. Baase, Sara. Computer Algorithms: Introduction to Design and Analysis 2nd ed. Reading, MA: Addison-Wesley, 1988. ISBN: 0201060353.
General reference, although the exposition is sometimes terse or sketchy.

4. Bentley, Jon Louis. Programming Pearls. Reading, MA: Addison-Wesley, 1986. ISBN: 0201103311.
Applications of algorithm design techniques to software engineering.

5. More Programming Pearls: Confessions of a Coder. Reading, MA: Addison-Wesley, 1988. ISBN: 0201118890.
More applications of algorithm design techniques to software engineering.

6. Writing Efficient Programs. Englewood Cliffs, NJ: Prentice-Hall, 1982. ISBN: 0139702512.
Performance hacking extraordinaire.

7. Brassard, Gilles, and Paul Bratley. Algorithmics: Theory and Practice. Englewood Cliffs, NJ: Prentice-Hall, 1988. ISBN: 0130232432.
Good examples and problems. Focus on methods rather than specific problems.

8.  Chung, Kai Lai. Elementary Probability Theory with Stochastic Processes.New York, NY: Springer-Verlag, 1974. ISBN: 0387900969.
Intuitive introduction to probability.

9.  Even, Shimon. Graph Algorithms. Rockville, MD: Computer Science Press, 1979. ISBN: 0914894218.
Broad treatment of graph algorithms, including network flow and planarity.

10.  Feller, William. An Introduction to Probability Theory and Its Applications. 3rd ed. 2 vols. New York, NY: John Wiley & Sons, 1968, 1971. ISBN: 0471257087. ISBN: 0471257095.
Excellent reference for probability theory.

11.  Garey, Michael R., and David S. Johnson. Computers and Intractibility: A Guide to the Theory of NP-Completeness. San Francisco, CA: W. H. Freeman & Co., 1979. ISBN: 0716710447.
Reference book devoted to NP-completeness. The second half contains an extensive list of NP-complete problems and references to algorithms in the literature for polynomial-time special cases.

12.  Gonnet, Gaston H. Handbook of Algorithms and Data Structures. Reading, MA: Addison-Wesley, 1984. ISBN: 020114218X.
Code in Pascal and C, comparisons of actual running times, and pointers to analysis in research papers.

13.  Gusfield, Dan. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge, UK: Cambridge University Press, 1997. ISBN: 0521585198.
General treatment of algorithms that operate on character strings and sequences.

14.  Horowitz, Ellis, and Sartaj Sahni. Fundamentals of Computer Algorithms. Potomac, MD: Computer Science Press, 1978. ISBN: 0914894226.
Good on data structures, dynamic programming, and branch-and-bound algorithms.

15.  Kingston, Jeffrey H. Algorithms and Data Structures: Design, Correctness, Analysis. Reading, MA: Addison-Wesley Publishing Co., 1991. ISBN: 0201417057.
A nice introductory book on data structures, with a good chapter on algorithm correctness.

16.  Knuth, Donald E. The Art of Computer Programming. 3rd ed. 3 vols. Reading, MA: Addison-Wesley, 1997. ISBN: 0201896834. ISBN: 0201896842. ISBN: 0201896850.
Encyclopedic work in three volumes: (1) Fundamental Algorithms, (2) Seminumerical Algorithms, and (3) Sorting and Searching.

17.  Lawler, Eugene L. Combinatorial Optimization: Networks and Matroids. New York, NY: Holt, Rinehart, and Winston, 1976. ISBN: 0030848660.
Graph algorithms (dense graphs), network flows, and linear programming. First few chapters are excellent.

18.  Liu, Chung L. Introduction to Combinatorial Mathematics. New York, NY: McGraw-Hill, 1968. ISBN: 0070381240.
Combinatorial mathematics relevant to computer science. Excellent problems.

19.  Manber, Udi. Introduction to Algorithms: A Creative Approach. Reading, MA: Addison-Wesley, 1989. ISBN: 0201120372.
Elementary text with an emphasis on creativity.

20.  Mehlhorn, Kurt. Data Structures and Algorithms. 3 vols. New York, NY: Springer-Verlag, 1984. ISBN: 038713302X. ISBN: 354013641X. ISBN: 0387136428.
Three volumes: (1) Sorting and Searching, (2) Graph Algorithms and NP-Completeness, and (3) Multidimensional Searching and Computational Geometry. Lecture notes on basic and advanced topics.

21.  Niven, Ivan, and Herbert S. Zuckerman. An Introduction to the Theory of Numbers. 4th ed. New York, NY: John Wiley & Sons, 1980. ISBN: 0471028517.
Readable introduction to number theory.

22.  Papadimitriou, Christos H., and Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Englewood Cliffs, NJ: Prentice-Hall, 1982. ISBN: 0131524623.
Linear programming and its variants.

23.  Press, William P., Brian P. Flannery, Saul A. Teukolsky, and William T. Vetterling. Numerical Recipies in C: The Art of Scientific Computing. Cambridge, UK: Cambridge University Press, 1988. ISBN: 052135465X.
Code for numerical algorithms.

24.  Reingold, Edwin M., Jurg Nievergelt, and Narsingh Deo. Combinatorial Algorithms: Theory and Practice. Englewood Cliffs, NJ: Prentice-Hall, 1977. ISBN: 013152447X.
Good on recurrence relations and binary search trees.

25.  Sedgewick, Robert. Algorithms. 2nd ed. Reading, MA: Addison-Wesley, 1988. ISBN: 0201066734.
Elementary text with an excellent breadth of topics. Light on analysis, but lots of figures.

26.  Sipser, Michael. Introduction to the Theory of Computation. Boston, MA: PWS Publishing Company, 1997. ISBN: 053494728X.
A good text on computability and complexity theory.

27.  Tarjan, Robert Endre. Data Structures and Network Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 1983. ISBN: 0898711878.
Advanced book with tons of good stuff.