ans9.pdf.xml

MIT开放课件 6.856J / 18.416J Randomized Algorithms Fall 2002

<?xml version="1.0" encoding="utf-8"?>
<lom:lom xsi:schemaLocation="http://ocw.mit.edu/xmlns/LOM http://ocw.mit.edu/xsd/LOM/lomv1.0/lomv1.0.xsd http://ocw.mit.edu/xmlns/ocwLOM http://ocw.mit.edu/xsd/ocwLOM/ocwlomv1.0/ocwlomv1.0.xsd" xmlns="http://ocw.mit.edu/xmlns/LOM" xmlns:lom="http://ocw.mit.edu/xmlns/LOM" xmlns:ocwlom="http://ocw.mit.edu/xmlns/ocwLOM" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
  <!--************************************************************ This LOM
			record was produced by an automatic transformation to IEEE LOM, from
			OpenCourseWare's (OCW) initial version of Learning Object Metadata (LOM). (The
			initial version was based on IMS Global Consortium's LOM.)
			********************************************************--><!--***************************--><!--**** GENERAL ****--><!--***************************--><lom:general uniqueElementName="general"><lom:title uniqueElementName="title"><lom:string language="en">Homework 9 Solutions</lom:string></lom:title><lom:description><lom:string language="en"></lom:string></lom:description><lom:language>en</lom:language><lom:aggregationLevel uniqueElementName="aggregationLevel"><lom:source uniqueElementName="source">LOMv1.0</lom:source><lom:value uniqueElementName="value">2</lom:value></lom:aggregationLevel></lom:general><!--***************************--><!--**** LIFECYCLE ****--><!--***************************--><lom:lifeCycle uniqueElementName="lifeCycle"><lom:version uniqueElementName="version"><lom:string language="en">Fall 2002</lom:string></lom:version><lom:contribute><lom:role><lom:source uniqueElementName="source">OCW_LOMv1.0</lom:source><lom:value uniqueElementName="value">Author</lom:value></lom:role><lom:entity>Karger, David</lom:entity><lom:date uniqueElementName="date"><lom:dateTime uniqueElementName="dateTime">2006-12-06</lom:dateTime></lom:date></lom:contribute></lom:lifeCycle><!--***************************--><!--**** TECHNICAL ****--><!--***************************--><lom:technical uniqueElementName="technical"><lom:location>/NR/rdonlyres/4C32B01F-E826-4FB7-9B4F-9D3BEF8725A1/0/ans9.pdf</lom:location><lom:format>application/pdf</lom:format><lom:otherPlatformRequirements><lom:string language="en">Adobe庐 Reader庐 software is required to view this .pdf file.</lom:string></lom:otherPlatformRequirements><lom:size>57115</lom:size><lom:requirement><lom:orComposite><lom:type uniqueElementName="type"><lom:source uniqueElementName="source">LOMv1.0</lom:source><lom:value uniqueElementName="value">browser</lom:value></lom:type><lom:name uniqueElementName="name"><lom:source uniqueElementName="source">LOMv1.0</lom:source><lom:value uniqueElementName="value">ms-internet explorer</lom:value></lom:name><lom:minimumVersion uniqueElementName="minimumVersion">5.1</lom:minimumVersion></lom:orComposite><lom:orComposite><lom:type uniqueElementName="type"><lom:source uniqueElementName="source">LOMv1.0</lom:source><lom:value uniqueElementName="value">browser</lom:value></lom:type><lom:name uniqueElementName="name"><lom:source uniqueElementName="source">LOMv1.0</lom:source><lom:value uniqueElementName="value">netscape communicator</lom:value></lom:name><lom:minimumVersion uniqueElementName="minimumVersion">4.7</lom:minimumVersion></lom:orComposite></lom:requirement></lom:technical><!--***************************--><!--**** EDUCATIONAL ****--><!--***************************--><lom:educational><lom:learningResourceType><lom:source uniqueElementName="source">LOMv1.0</lom:source><lom:value uniqueElementName="value">exercise</lom:value></lom:learningResourceType><lom:context><lom:source uniqueElementName="source">OCW_LOMv1.0</lom:source><lom:value uniqueElementName="value">Graduate</lom:value></lom:context><lom:description><lom:string language="en">Solutions to problem set.</lom:string></lom:description></lom:educational><!--***************************--><!--**** RIGHTS ****--><!--***************************--><lom:rights uniqueElementName="rights"><lom:copyrightAndOtherRestrictions uniqueElementName="copyrightAndOtherRestrictions"><lom:source uniqueElementName="source">LOMv1.0</lom:source><lom:value uniqueElementName="value">yes</lom:value></lom:copyrightAndOtherRestrictions><lom:cost><lom:source uniqueElementName="source">LOMv1.0</lom:source><lom:value uniqueElementName="value">no</lom:value></lom:cost><lom:description><lom:string language="en">This site (c) Massachusetts Institute of Technology 2003. Content within individual courses is (c) by the individual authors unless otherwise noted. The Massachusetts Institute of Technology is providing this Work (as defined below) under the terms of this Creative Commons public license ("CCPL" or "license"). The Work is protected by copyright and/or other applicable law. Any use of the work other than as authorized under this license is prohibited. By exercising any of the rights to the Work provided here, You (as defined below) accept and agree to be bound by the terms of this license. The Licensor, the Massachusetts Institute of Technology, grants You the rights contained here in consideration of Your acceptance of such terms and conditions.</lom:string></lom:description></lom:rights><!--***************************--><!--**** RELATION ****--><!--***************************--><lom:relation><lom:kind uniqueElementName="kind"><lom:source uniqueElementName="source">LOMv1.0</lom:source><lom:value uniqueElementName="value">ispartof</lom:value></lom:kind><lom:resource uniqueElementName="resource"><lom:identifier><lom:catalog uniqueElementName="catalog">OCW Master Course Number</lom:catalog><lom:entry uniqueElementName="entry">6.856J Randomized Algorithms Fall 2002</lom:entry></lom:identifier><lom:description><lom:string language="en">Studies how randomization can be used to make algorithms simpler and more efficient via random sampling, random selection of witnesses, symmetry breaking, and Markov chains. Models of randomized computation. Data structures: hash tables, and skip lists. Graph algorithms: minimum spanning trees, shortest paths, and minimum cuts. Geometric algorithms: convex hulls, linear programming in fixed or arbitrary dimension. Approximate counting; parallel algorithms; online algorithms; derandomization techniques; and tools for probabilistic analysis of algorithms. Alternate years.</lom:string></lom:description></lom:resource></lom:relation><!--***************************--><!--**** CLASSIFICATION ****--><!--***************************--><lom:classification><lom:taxonPath><lom:source uniqueElementName="source"><lom:string language="en">CIP</lom:string></lom:source><lom:taxon><lom:id uniqueElementName="id">270303</lom:id><lom:entry uniqueElementName="entry"><lom:string language="en">Computational Mathematics</lom:string></lom:entry></lom:taxon></lom:taxonPath><lom:taxonPath><lom:source uniqueElementName="source"><lom:string language="en">LCSH</lom:string></lom:source><lom:taxon><lom:id uniqueElementName="id">Algorithms</lom:id></lom:taxon></lom:taxonPath><lom:keyword><lom:string language="en">Randomized Algorithms</lom:string></lom:keyword><lom:keyword><lom:string language="en">efficient in time and space</lom:string></lom:keyword><lom:keyword><lom:string language="en">computational problems</lom:string></lom:keyword><lom:keyword><lom:string language="en">data structures</lom:string></lom:keyword><lom:keyword><lom:string language="en">graph algorithms</lom:string></lom:keyword><lom:keyword><lom:string language="en">optimization</lom:string></lom:keyword><lom:keyword><lom:string language="en">geometry</lom:string></lom:keyword><lom:keyword><lom:string language="en">Markov chains</lom:string></lom:keyword><lom:keyword><lom:string language="en">estimation</lom:string></lom:keyword><lom:keyword><lom:string language="en">geometric algorithms</lom:string></lom:keyword><lom:keyword><lom:string language="en">randomization</lom:string></lom:keyword><lom:keyword><lom:string language="en">random sampling</lom:string></lom:keyword><lom:keyword><lom:string language="en">random selection of witnesses</lom:string></lom:keyword><lom:keyword><lom:string language="en">symmetry breaking</lom:string></lom:keyword><lom:keyword><lom:string language="en">randomized computational models</lom:string></lom:keyword><lom:keyword><lom:string language="en">hash tables</lom:string></lom:keyword><lom:keyword><lom:string language="en">skip lists</lom:string></lom:keyword><lom:keyword><lom:string language="en">minimum spanning trees</lom:string></lom:keyword><lom:keyword><lom:string language="en">shortest paths</lom:string></lom:keyword><lom:keyword><lom:string language="en">minimum cuts</lom:string></lom:keyword><lom:keyword><lom:string language="en">convex hulls</lom:string></lom:keyword><lom:keyword><lom:string language="en">fixed dimension</lom:string></lom:keyword><lom:keyword><lom:string language="en">arbitrary dimension</lom:string></lom:keyword><lom:keyword><lom:string language="en">approximate counting</lom:string></lom:keyword><lom:keyword><lom:string language="en">online algorithms</lom:string></lom:keyword><lom:keyword><lom:string language="en">derandomization techniques</lom:string></lom:keyword><lom:keyword><lom:string language="en">probabilistic analysis</lom:string></lom:keyword><lom:keyword><lom:string language="en">computational number theory</lom:string></lom:keyword><lom:keyword><lom:string language="en">simplicity</lom:string></lom:keyword><lom:keyword><lom:string language="en">speed</lom:string></lom:keyword><lom:keyword><lom:string language="en">design</lom:string></lom:keyword><lom:keyword><lom:string language="en">basic probability theory</lom:string></lom:keyword><lom:keyword><lom:string language="en">application</lom:string></lom:keyword><lom:keyword><lom:string language="en">randomized complexity classes</lom:string></lom:keyword><lom:keyword><lom:string language="en">game-theoretic techniques</lom:string></lom:keyword><lom:keyword><lom:string language="en">Chebyshev</lom:string></lom:keyword><lom:keyword><lom:string language="en">moment inequalities</lom:string></lom:keyword><lom:keyword><lom:string language="en">limited independence</lom:string></lom:keyword><lom:keyword><lom:string language="en">coupon collection</lom:string></lom:keyword><lom:keyword><lom:string language="en">occupancy problems</lom:string></lom:keyword><lom:keyword><lom:string language="en">tail inequalities</lom:string></lom:keyword><lom:keyword><lom:string language="en">Chernoff bound</lom:string></lom:keyword><lom:keyword><lom:string language="en">conditional expectation</lom:string></lom:keyword><lom:keyword><lom:string language="en">probabilistic method</lom:string></lom:keyword><lom:keyword><lom:string language="en">random walks</lom:string></lom:keyword><lom:keyword><lom:string language="en">algebraic techniques</lom:string></lom:keyword><lom:keyword><lom:string language="en">probability amplification</lom:string></lom:keyword><lom:keyword><lom:string language="en">sorting</lom:string></lom:keyword><lom:keyword><lom:string language="en">searching</lom:string></lom:keyword><lom:keyword><lom:string language="en">combinatorial optimization</lom:string></lom:keyword><lom:keyword><lom:string language="en">linear programming</lom:string></lom:keyword><lom:keyword><lom:string language="en">approximation</lom:string></lom:keyword><lom:keyword><lom:string language="en">counting problems</lom:string></lom:keyword><lom:keyword><lom:string language="en">parallel algorithms</lom:string></lom:keyword><lom:keyword><lom:string language="en">distributed algorithms</lom:string></lom:keyword><lom:keyword><lom:string language="en">6.856J</lom:string></lom:keyword><lom:keyword><lom:string language="en">18.416J</lom:string></lom:keyword><lom:keyword><lom:string language="en">6.856</lom:string></lom:keyword><lom:keyword><lom:string language="en">18.416</lom:string></lom:keyword></lom:classification></lom:lom>