【视频】计算机：算法 04 快速随机排序(Quicksort, Randomized Algorithms)
[b]Introduction to Algorithms (SMA 5503)N&x6UH|$Wg s&c'N Dw5I!~*_y
Quicksort, Randomized Algorithms
Fall 2005[/b]#tq*w`3}} W
W$o5awM\a/l C,|
[attach]241[/attach] N2R!Bm&C0R
Cover of 6.046J textbook, Introduction to Algorithms, Second Edition, by Cormen, Leiserson, Rivest, and Stein. (Image courtesy of MIT Press.)
AR"wns3h!?
[b]Course Description[/b]
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. 7Z2dP-L1b D!h
This course was also taught as part of the Singapore-MIT Alliance (SMA) programme as course number SMA 5503 (Analysis and Design of Algorithms).1Z)l'` k)F7B JN f
L1yr+bq}YK
[b]Textbook[/b] p4b5T4w*b _ B)IF
!qO!e6|)TH8Z
Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. 2nd ed. Cambridge, MA: MIT Press. ISBN: 0262032937.8gb\%g.~`#W
lxWO8a
【观看视频】(因网络原因，有时需耐心等待5-10秒以上时间)
[flash]http://www.tudou.com/v/JskVA7yWrA0[/flash]t1J*^ O&c/? vE0H
【下载讲义】l-P$d(?w2B U~
[attach]242[/attach]
[[i] 本帖最后由 autumnwater 于 2008-12-18 08:06 编辑 [/i]]
Useful References 参考书目
1. Aho, Alfred V., John E. Hopcroft, and Jeffrey D. Ullman. [i]The Design and Analysis of Computer Algorithms[/i]. Reading, MA: Addison-Wesley, 1974. ISBN: 0201000296.y;\SWf7m}I/Y(}The classic text, but it lacks topics in network flows and linear programming, as well as more recent algorithms.
} qXLd,Q'ig~,Ja
2. [i]Data Structures and Algorithms [/i]Reading, MA: Addison-Wesley, 1983. ISBN: 0201000237.)@ } uYvj0t UC3o L
Revised and more elementary version of the first six chapters of The Design and Analysis of Computer Algorithms. ~8L7EW3y9r y5A
3. Baase, Sara. [i]Computer Algorithms: Introduction to Design and Analysis[/i] 2nd ed. Reading, MA: Addison-Wesley, 1988. ISBN: 0201060353.[ p l)s/gG!h@
General reference, although the exposition is sometimes terse or sketchy.
4. Bentley, Jon Louis. [i]Programming Pearls.[/i] Reading, MA: Addison-Wesley, 1986. ISBN: 0201103311.
Applications of algorithm design techniques to software engineering.F'q5Up-CZ
5. [i]More Programming Pearls: Confessions of a Coder[/i]. Reading, MA: Addison-Wesley, 1988. ISBN: 0201118890.
More applications of algorithm design techniques to software engineering.%e4Y bE~&C
6. [i]Writing Efficient Programs.[/i] Englewood Cliffs, NJ: Prentice-Hall, 1982. ISBN: 0139702512.]:L G$\9b#T
Performance hacking extraordinaire.
7. Brassard, Gilles, and Paul Bratley. [i]Algorithmics: Theory and Practice.[/i] Englewood Cliffs, NJ: Prentice-Hall, 1988. ISBN: 0130232432.
Good examples and problems. Focus on methods rather than specific problems.(|/Q]a!wWs'mD Bm
m0q#lI_
8. Chung, Kai Lai. [i]Elementary Probability Theory with Stochastic Processes[/i].New York, NY: Springer-Verlag, 1974. ISBN: 0387900969.
Intuitive introduction to probability.
9. Even, Shimon. [i]Graph Algorithms. [/i]Rockville, MD: Computer Science Press, 1979. ISBN: 0914894218.
Broad treatment of graph algorithms, including network flow and planarity.L,A/UR Y,z0UV
b[ e huUV
10. Feller, William. [i]An Introduction to Probability Theory and Its Applications[/i]. 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. [i]Computers and Intractibility: A Guide to the Theory of NP-Completeness[/i]. San Francisco, CA: W. H. Freeman & Co., 1979. ISBN: 0716710447.hM&GD-A I/|5Hj7R%q
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.+{ ? FO7vf7m
V;AN[ \q
12. Gonnet, Gaston H. [i]Handbook of Algorithms and Data Structures[/i]. Reading, MA: Addison-Wesley, 1984. ISBN: 020114218X.u a,m/N%uz\
Code in Pascal and C, comparisons of actual running times, and pointers to analysis in research papers. A ] } p S1L7r5Z2OuL;Im
13. Gusfield, Dan. [i]Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology[/i]. Cambridge, UK: Cambridge University Press, 1997. ISBN: 0521585198.zg~8p;g Yc v(w
General treatment of algorithms that operate on character strings and sequences.!Px8f_0l}F
9y*I Q Fk;f.U?5{3y K
14. Horowitz, Ellis, and Sartaj Sahni. [i]Fundamentals of Computer Algorithms[/i]. Potomac, MD: Computer Science Press, 1978. ISBN: 0914894226.
Good on data structures, dynamic programming, and branch-and-bound algorithms.
!mw5f9K$H3U
15. Kingston, Jeffrey H.[i] Algorithms and Data Structures: Design, Correctness, Analysis[/i]. Reading, MA: Addison-Wesley Publishing Co., 1991. ISBN: 0201417057.
A nice introductory book on data structures, with a good chapter on algorithm correctness.:H g BUq-|%}hD
16. Knuth, Donald E. [i]The Art of Computer Programming[/i]. 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.d#~5O1? bC:`;A
17. Lawler, Eugene L. [i]Combinatorial Optimization: Networks and Matroids[/i]. New York, NY: Holt, Rinehart, and Winston, 1976. ISBN: 0030848660.wok ])hE v
Graph algorithms (dense graphs), network flows, and linear programming. First few chapters are excellent./?Ihb ? qn
e Z D,YWjn
18. Liu, Chung L. [i]Introduction to Combinatorial Mathematics[/i]. New York, NY: McGraw-Hill, 1968. ISBN: 0070381240.,l0Q1V f2v c4D3C#k,F
Combinatorial mathematics relevant to computer science. Excellent problems.Z.lr5dj7dZ5?
rl N }5|i
19. Manber, Udi. [i]Introduction to Algorithms: A Creative Approach[/i]. Reading, MA: Addison-Wesley, 1989. ISBN: 0201120372.+s gl~.U|$P
Elementary text with an emphasis on creativity.k k+z3ps?)hn(Da
&x#WQ(W+J$q1n:} `
20. Mehlhorn, Kurt. [i]Data Structures and Algorithms[/i]. 3 vols. New York, NY: Springer-Verlag, 1984. ISBN: 038713302X. ISBN: 354013641X. ISBN: 0387136428. d mQ'y3d{R c
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.
.L `3\{8v.o
21. Niven, Ivan, and Herbert S. Zuckerman. [i]An Introduction to the Theory of Numbers[/i]. 4th ed. New York, NY: John Wiley & Sons, 1980. ISBN: 0471028517.7S!l;v:qm zw
Readable introduction to number theory.*O:H EA6G v
A7D@$rV$f
22. Papadimitriou, Christos H., and Kenneth Steiglitz. [i]Combinatorial Optimization: Algorithms and Complexity[/i]. Englewood Cliffs, NJ: Prentice-Hall, 1982. ISBN: 0131524623.
Linear programming and its variants.i+[ G.O sM X
23. Press, William P., Brian P. Flannery, Saul A. Teukolsky, and William T. Vetterling. [i]Numerical Recipies in C: The Art of Scientific Computing[/i]. Cambridge, UK: Cambridge University Press, 1988. ISBN: 052135465X.
Code for numerical algorithms./c#n u O-{S'm.sg@
24. Reingold, Edwin M., Jurg Nievergelt, and Narsingh Deo. [i]Combinatorial Algorithms: Theory and Practice.[/i] Englewood Cliffs, NJ: Prentice-Hall, 1977. ISBN: 013152447X.
Good on recurrence relations and binary search trees. B&TUc6v |
25. Sedgewick, Robert. [i]Algorithms[/i]. 2nd ed. Reading, MA: Addison-Wesley, 1988. ISBN: 0201066734.y2D0r@UTi j
Elementary text with an excellent breadth of topics. Light on analysis, but lots of figures.
26. Sipser, Michael. [i]Introduction to the Theory of Computation[/i]. Boston, MA: PWS Publishing Company, 1997. ISBN: 053494728X.*Z+r{Q,X"eO p @
A good text on computability and complexity theory.
!y(a"e c ly
27. Tarjan, Robert Endre. [i]Data Structures and Network Algorithms[/i]. Philadelphia, PA: Society for Industrial and Applied Mathematics, 1983. ISBN: 0898711878.
Advanced book with tons of good stuff. thx for sharing thanks a million 太好了！ 多谢阿！ 很不错！！ 为什么没有3 ，5 。。。。。。。 thx for sharing 很不错的视频。
页:
[1]