📄 http:^^www.cs.princeton.edu^courses^archive^fall95^cs597b^
字号:
Server: Netscape-Commerce/1.12
Date: Wednesday, 20-Nov-96 22:45:25 GMT
Last-modified: Friday, 27-Oct-95 21:05:39 GMT
Content-length: 3307
Content-type: text/html
<HEADER><title> COS 597B, Fall 1995 </title></HEADER><body><H4> COS 597B, Fall 1995</H4><H4>Instructor:<!WA0><A HREF ="http://www.cs.princeton.edu/~arora"> Sanjeev Arora </A> </H4><HR><H2>Randomized Algorithms </H2> <P>Randomized algorithms are often faster, simpler,and easier to analyze than deterministic algorithms.Many recent algorithmic breakthrough --- both in algorithmictheory and in practical applications --- involve the use ofrandomness. For instance, the packet router in the CM-5is randomized. So are many cryptographic schemes.</p><p>The course will introduce students to this excitingarea, while developing all required techniquesfrom probabilistic analysis. </p><p> The text will be <!WA1><A HREF ="http://www.cup.org/Reviews&blurbs/RanAlg/RanAlg.html"> Randomized Algorithms </A> by R. Motwani and P. Raghavan, printed by Cambridge University Press. It is a rarity among good textbooks,in that it is well-written, hard-bound, and costs less than $40.</P><p>Course Prerequisites: Mathematical maturity (knowledge of probability analysis andcombinatorial enumeration at the level of COS 341) and knowledgeof algorithms at the undergrad level (COS 423).Both grads and undergrads are welcome to take the course.Grading will be based upon assignments, which will be handed outevery two weeks.</p><h4> Other Suggested Books </h4><ul><li> <!WA2><a href = "gopher://ns1.infor.com:6000/1exec%3aR27945983-27948302-/.text/Main%3a/.bin/views"> The probabilistic method.</a> J. Spencer and N. Alon. (John Wiley.)<li> <!WA3><a href = "gopher://ns1.infor.com:6000/1exec%3aR20202296-20204440-/.text/Main%3a/.bin/views"> An Introduction to Probability Theory and Its Applications, 3rd Ed. </a> W. Feller. (John Wiley)</ul><H3> Course Topics </H3><p> Various tools for probabilistic analysis: Linearity of Expectations,Chebyshev's Inequality, Chernoff and Hoeffding bounds, Lovasz Local Lemma.Applications of these tools to design and analysis of algorithms.Derandomization of algorithms: pairwise independence, use of expanders andlimited independence. Markov chains.</p><p> Various examples of randomized algorithms will be given throughoutthe course, including randomized data structures, game tree search,routing algorithms, algorithms for combinatorial optimization and linear programming, number theoretic algorithms, and algorithms for counting anduniform generation of combinatorial objects (such as matchings).</p><!WA4><a href ="http://www.CS.Princeton.EDU/courses/archive/fall95/cs597B/outline.html"> Click here for a detailed outline. </a><H3> Handouts </H3><p><ul><li> <!WA5><a href="http://www.CS.Princeton.EDU/courses/archive/fall95/cs597B/instruct.ps"> Some instructions on doing the assignment. </a><li> <!WA6><a href="http://www.CS.Princeton.EDU/courses/archive/fall95/cs597B/chernoff.ps"> Handout on Chernoff Bounds. </a><li> <!WA7><a href="http://www.CS.Princeton.EDU/courses/archive/fall95/cs597B/byzantin.ps">Handout on Byzantine Agreement (includes thecase n=3t+1). </a><li> <!WA8><a href="http://Theory.Stanford.EDU/people/wass/research.html"> Survey paper on Randomized LP Algorithms. </a></ul> <p> <H3> Problem Sets </H3><p><ul><li> <!WA9><a href="http://www.CS.Princeton.EDU/courses/archive/fall95/cs597B/ps1.ps"> Problem Set 1 </a>, due 10/2.<li> <!WA10><a href="http://www.CS.Princeton.EDU/courses/archive/fall95/cs597B/ps2.ps"> Problem Set 2 (Qs. 5 has been revised)</a>, due 10/16.<li> <!WA11><a href ="http://www.CS.Princeton.EDU/courses/archive/fall95/cs597B/ps3.ps"> Problem Set 3 </a>, due 11/13. </ul><p><HR><p><address>Created by: <!WA12><a href="http://www.cs.princeton.edu/~arora/"> Sanjeev Arora. </a><br>Last Updated: 10/12/95, 13:15</address></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -