📄 index.htm
字号:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en"> <head> <title>MIT OpenCourseWare | Electrical Engineering and Computer Science | 6.856J Randomized Algorithms, Fall 2002 | Calendar </title> <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" /> <meta name="WT.cg_n" content="6-856JRandomized-AlgorithmsFall2002" /> <meta name="WT.cg_s" content="Calendar" /> <!-- Begin Automatic Metadata Insertion --><meta name="Title" content="Calendar"/><meta name="Description" content=""/><meta name="Author" content="Karger, David"/><meta name="Keyword" content="Randomized Algorithms, efficient in time and space, computational problems, data structures, graph algorithms, optimization, geometry, Markov chains, estimation, geometric algorithms, randomization, random sampling, random selection of witnesses, symmetry breaking, randomized computational models, hash tables, skip lists, minimum spanning trees, shortest paths, minimum cuts, convex hulls, fixed dimension, arbitrary dimension, approximate counting, online algorithms, derandomization techniques, probabilistic analysis, computational number theory, simplicity, speed, design, basic probability theory, application, randomized complexity classes, game-theoretic techniques, Chebyshev, moment inequalities, limited independence, coupon collection, occupancy problems, tail inequalities, Chernoff bound, conditional expectation, probabilistic method, random walks, algebraic techniques, probability amplification, sorting, searching, combinatorial optimization, linear programming, approximation, counting problems, parallel algorithms, distributed algorithms, 6.856J, 18.416J, 6.856, 18.416"/><meta name="Version" content=""/><!-- End Automatic Metadata Insertion --> <link title="default" href="../../../../OcwWeb/style/common.css" type="text/css" rel="stylesheet"/> <link title="default" href="../../../../OcwWeb/style/courses.css" type="text/css" rel="stylesheet"/> <link rel="metadata" type="application/rdf+xml" href="../../../../OcwWeb/xml/ocwcc.rdf" /> <script type="text/javascript" src="../../../../OcwWeb/js/styleswitch.js"></script> </head> <body id="global" > <div id="container"> <form method="get" action="http://search.mit.edu/search"><input type="hidden" name="__EVENTTARGET" value="" /><input type="hidden" name="__EVENTARGUMENT" value="" /><script language="javascript" type="text/javascript"><!-- function __doPostBack(eventTarget, eventArgument) { var theform; if (window.navigator.appName.toLowerCase().indexOf("microsoft") > -1) { theform = document.CourseHomePage; } else { theform = document.forms["CourseHomePage"]; } theform.__EVENTTARGET.value = eventTarget.split("$").join(":"); theform.__EVENTARGUMENT.value = eventArgument; theform.submit(); }// --></script><script language="javascript" type="text/javascript"><!-- var __CMS_PostbackForm = document.forms['CourseHomePage']; var __CMS_CurrentUrl = "/OcwWeb/templates/section/GenericOther.aspx?NRMODE=Published&NRNODEGUID=%7bC5D9FF4A-D0DA-4336-97C2-859CC122AE48%7d&NRORIGINALURL=%2fOcwWeb%2fElectrical-Engineering-and-Computer-Science%2f6-856JRandomized-AlgorithmsFall2002%2fCalendar%2findex%2ehtm&NRCACHEHINT=Guest";// --></script> <div class="page_header"> <div class="logo"> <h1><a href="http://ocw.mit.edu/OcwWeb/web/home/home/index.htm"><img src="../../../../OcwWeb/images/logo-ocw-home_new.gif" alt="MIT OpenCourseWare" width="289" height="36" /></a></h1> </div> <!-- end header --></div><div id="primary_nav"> <ul id="nav"> <li class=""> <a href="http://ocw.mit.edu/OcwWeb/web/home/home/index.htm">Home</a></li> <li class="first active"> <a href="http://ocw.mit.edu/OcwWeb/web/courses/courses/index.htm">Courses</a></li> <li class=""> <a href="http://ocw.mit.edu/OcwWeb/web/donate/donate/index.htm">Donate</a></li> <li class=""> <a href="http://ocw.mit.edu/OcwWeb/web/about/about/index.htm" class="about_ocw">About OCW</a></li> </ul> <!-- begin search area, inputs are placed inside div blocks to validate xhtml strict --> <div class="searchform"> <div> <input type="hidden" name="site" value="ocw" /> <input type="hidden" name="client" value="mit" /> <input type="hidden" name="getfields" value="*" /> <input type="hidden" name="output" value="xml_no_dtd" /> <input type="hidden" name="proxystylesheet" value="http://ocw.mit.edu/OcwWeb/search/google-ocw.xsl" /> <input type="hidden" name="proxyreload" value="1" /> <input type="hidden" name="as_dt" value="i" /> <input type="hidden" name="oe" value="utf-8" /> <input type="hidden" name="departmentName" value="Electrical Engineering and Computer Science" /> <input type="hidden" name="courseName" value="" /> </div> <div> <input type="text" name="q" id="terms" maxlength="255" class="search" value="Enter search keyword" onfocus="clearSearchBox()" onblur="fillSearchBox()"/> <input type="image" src="../../../../OcwWeb/images/go_new.gif" name="btnG" alt="Go" class="but" /> <a href="../../../../OcwWeb/search/AdvancedSearch.htm">Advanced Search</a> </div> </div> <!-- end search area --> <ul id="secondary_nav"> <li class="first"> <a href="http://ocw.mit.edu/OcwWeb/web/help/help/index.htm">Help</a></li> <li> <a href="../../../../OcwWeb/jsp/feedback.jsp?Referer=">Contact Us</a></li> </ul> <!-- end Primary Nav --></div> <div id="main"> <div id="local_navigation"> <script language="javascript" type="text/javascript"><!--function MM_openBrWindow(theURL,winName,features) { window.open(theURL,winName,features);}// --></script> <!-- AE3305: Commented out: <table id="CourseLeftNav1_tblLeftNav" border="0"></table> --><!-- LeftNav --><div class="left-nav"> <div class= "get_started"><ul><li class="courses"><a href="http://ocw.mit.edu/OcwWeb/web/courses/courses/index.htm">VIEW ALL COURSES</a></li></ul></div><div class="get_started"><ul><li class = "courses"><a href="../../../../OcwWeb/Electrical-Engineering-and-Computer-Science/6-856JRandomized-AlgorithmsFall2002/CourseHome/index.htm">Course Home</a></li><li><a href="../../../../OcwWeb/Electrical-Engineering-and-Computer-Science/6-856JRandomized-AlgorithmsFall2002/Syllabus/index.htm">Syllabus</a></li><li><a href="../../../../OcwWeb/Electrical-Engineering-and-Computer-Science/6-856JRandomized-AlgorithmsFall2002/Calendar/index.htm" class = "selected">Calendar</a></li><li><a href="../../../../OcwWeb/Electrical-Engineering-and-Computer-Science/6-856JRandomized-AlgorithmsFall2002/LectureNotes/index.htm">Lecture Notes</a></li><li><a href="../../../../OcwWeb/Electrical-Engineering-and-Computer-Science/6-856JRandomized-AlgorithmsFall2002/Assignments/index.htm">Assignments</a></li><li><a href="../../../../OcwWeb/Electrical-Engineering-and-Computer-Science/6-856JRandomized-AlgorithmsFall2002/DownloadthisCourse/index.htm">Download this Course</a></li></ul></div></div><!-- End LeftNav --> </div> <div id="content_body"> <div class="page_links"> <div class="breadcrumb"><a href="http://ocw.mit.edu/OcwWeb/web/home/home/index.htm">Home</a> > <a href="http://ocw.mit.edu/OcwWeb/web/courses/courses/index.htm">Courses</a> > <a href="http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/index.htm">Electrical Engineering and Computer Science</a> > <span>Randomized Algorithms</span></div> <span id="switchbutton"></span> </div> <div id="main_content_course"> <div id="courses_inner"> <h1>Calendar</h1> <div class="clear"></div> <div class="clear"></div> <div class="mod8"> <div class="bodycopy" id="BodyCopy1"> <table class="tbloutline" cellspacing="0" cellpadding="1" width="50%" summary="Course Table Outline" border="0"><tbody><tr><td><table class="datatable" cellspacing="0" cellpadding="8" width="100%" summary="Course Table Listing" border="1"><!-- BEGIN TABLE HEADER (for Table Template) --><thead><tr class="tableheader"><th id="col1" scope="col">LEC #</th><th id="col2" scope="col">TOPICS</th></tr></thead><!-- END TABLE HEADER --><tbody><tr class="gray-row"><td headers="col1">1</td><td headers="col2">Introduction to Randomized Algorithms</td></tr><tr class="white-row"><td headers="col1">2</td><td headers="col2">Min-Cut, Complexity Theory, Game Tree Evaluation</td></tr><tr class="gray-row"><td headers="col1">3</td><td headers="col2">Adelman's Theorem, Game Theory, Lower Bounds</td></tr><tr class="white-row"><td headers="col1">4</td><td headers="col2">Coupon Collecting, Stable Marriage, Markov Inequality</td></tr><tr class="gray-row"><td headers="col1">5</td><td headers="col2">Chebyshev, Two Point Sampling, Chernoff</td></tr><tr class="white-row"><td headers="col1">6</td><td headers="col2">Median Finding, Routing</td></tr><tr class="gray-row"><td headers="col1">7</td><td headers="col2">Probabilistic Method, Expanders, Wiring, MAX SAT</td></tr><tr class="white-row"><td headers="col1">8</td><td headers="col2">Method of Conditional Probabilities and Expectations, Fingerprinting</td></tr><tr class="gray-row"><td headers="col1">9</td><td headers="col2">Hashing, Perfect Hash Families, Freivald's Technique</td></tr><tr class="white-row"><td headers="col1">10</td><td headers="col2">Fingerprints by Polynomials, Perfect Matching, Hashing</td></tr><tr class="gray-row"><td headers="col1">11</td><td headers="col2">Shortest Paths</td></tr><tr class="white-row"><td headers="col1">12</td><td headers="col2">Parallel Algorithms</td></tr><tr class="gray-row"><td headers="col1">13</td><td headers="col2">Maximal Independent Sets</td></tr><tr class="white-row"><td headers="col1">14</td><td headers="col2">Minimum Spanning Trees</td></tr><tr class="gray-row"><td headers="col1">15</td><td headers="col2">Polling, Minimum Cut, Transitive Closure</td></tr><tr class="white-row"><td headers="col1">16</td><td headers="col2">Estimating Min-Cut Size</td></tr><tr class="gray-row"><td headers="col1">17</td><td headers="col2">Linear Programming</td></tr><tr class="white-row"><td headers="col1">18</td><td headers="col2">DNF Counting</td></tr><tr class="gray-row"><td headers="col1">19</td><td headers="col2">Markov Chains</td></tr><tr class="white-row"><td headers="col1">20</td><td headers="col2">UTS, Eigenvalue Analysis, Expanders</td></tr><tr class="gray-row"><td headers="col1">21</td><td headers="col2">Expander based Pseudo-Random Generator</td></tr><tr class="white-row"><td headers="col1">22</td><td headers="col2">Sampling with Markov Chains, Coupling</td></tr><tr class="gray-row"><td headers="col1">23</td><td headers="col2">Computational Geometry</td></tr><tr class="white-row"><td headers="col1">24</td><td headers="col2">Randomized Incremental Construction</td></tr><tr class="gray-row"><td headers="col1">25</td><td headers="col2">Trapezoidal Decomposition, Treaps</td></tr><tr class="white-row"><td headers="col1">26</td><td headers="col2">Online Algorithms</td></tr><!-- TEN ROWS --></tbody></table><!-- END INNER TABLE --></td></tr></tbody></table><!-- END OUTER TABLE --></div> </div> </div><!--End of courses_inner" div--> </div><!-- End of main_content_course div--> <div class="clear"></div> </div><!--End of content_body div--> </div><!-- End main div --> <div class="footer"> <div class="footer_logo"> <a href="http://web.mit.edu"><img src="../../../../OcwWeb/images/trans.gif" alt="MIT Logo" width="65" height="35" align="top" title="MIT Logo"></a> <a href="../../../../OcwWeb/web/terms/terms/index.htm"><img src="../../../../OcwWeb/images/trans.gif" alt="Copyright 2002-2007 MIT" width="100" height="13" align="textTop" title="Copyright 2002-2007 MIT"></a> </div> <div class="footer_links"> <ul> <li class="first"> <a href="http://ocw.mit.edu/OcwWeb/web/about/rss/index.htm"><img src="../../../../OcwWeb/images/footer_rss_new.gif" border="0" width="32" height="15" align="absbottom" alt="RSS Feeds"></a><a href="http://ocw.mit.edu/OcwWeb/web/about/rss/index.htm">RSS Feeds</a> <li> <a href="../../../../OcwWeb/web/terms/terms/index.htm">Privacy and Terms of Use</a> <li> <a href="http://ocw.mit.edu/OcwWeb/web/help/sitemap/index.htm">Site Map</a></li> </ul> <p>Your use of the MIT OpenCourseWare site and course materials is subject to our Creative Commons License and other terms of use.</p> <!-- end footer links --> </div> <div class="license"> <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/3.0/us/" target="_blank" class="first"><img src="../../../../OcwWeb/images/cc_logo_new.gif" alt="Creative Commons - some rights reserved" border="0" width="80" height="15"></a><br> <a rel="license" href="http://www.ocwconsortium.org/" target="_blank" class="first"> <img src="../../../../OcwWeb/images/ocw-logo_new.gif" alt="OCW Consortium" width="80" height="44"></a></div></div><DIV></DIV><!-- end footer --><!-- Start Webtrends Tracking Tag --><noscript> <div> </div></noscript><!-- End Webtrends Tracking Tag --> </A> </form> </div> </body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -