imsmanifest.xml

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

<?xml version="1.0" encoding="UTF-8"?>
<manifest identifier="urn_edu.mit.ocw_6-856JRandomized-AlgorithmsFall2002" version="2007-11-02T06:57:04" cwsp:packageType="Course" xml:base="6-856JFall-2002/" xmlns="http://www.imsglobal.org/xsd/imscp_v1p1" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:adlcp="http://www.adlnet.org/xsd/adlcp_rootv1p2" xmlns:cwsp="http://www.dspace.org/xmlns/cwspace_imscp" xmlns:ocw="http://ocw.mit.edu/xmlns/ocw_imscp" xmlns:lom="http://ocw.mit.edu/xmlns/LOM" xsi:schemaLocation="http://www.imsglobal.org/xsd/imscp_v1p1 http://www.imsglobal.org/xsd/imscp_v1p1.xsd 	http://www.adlnet.org/xsd/adlcp_rootv1p2 http://www.adlnet.org/xsd/adlcp_rootv1p2.xsd http://www.dspace.org/xmlns/cwspace_imscp http://www.dspace.org/xsd/cwspace_imscp/version10/cwspace_imscpv10.xsd http://ocw.mit.edu/xmlns/ocw_imscp http://ocw.mit.edu/xsd/ocw_imscp/version10/ocw_imscpv10.xsd http://ocw.mit.edu/xmlns/LOM http://ocw.mit.edu/xsd/LOM/lomv1.0/lomv1.0.xsd">
  <metadata>
    <schema>IMS Content</schema>
    <schemaversion>1.1</schemaversion>
    <cwsp:packageMetadata>
      <cwsp:sourceSystem>OCW</cwsp:sourceSystem>
      <cwsp:profile>CWSpace</cwsp:profile>
      <cwsp:profileVersion>0.1</cwsp:profileVersion>
    </cwsp:packageMetadata>
    <lom:general uniqueElementName="general">
      <lom:title uniqueElementName="title">
        <lom:string language="en">Randomized Algorithms</lom:string>
      </lom:title>
      <lom:identifier>
        <lom:catalog uniqueElementName="catalog">OCW Master Course Number</lom:catalog>
        <lom:entry uniqueElementName="entry">6.856J</lom:entry>
      </lom:identifier>
      <lom:identifier>
        <lom:catalog uniqueElementName="catalog">OCW Linked Course Number</lom:catalog>
        <lom:entry uniqueElementName="entry">18.416J</lom:entry>
      </lom:identifier>
    </lom:general>
    <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">2007-10-12</lom:dateTime>
        </lom:date>
      </lom:contribute>
    </lom:lifecycle>
    <adlcp:location>OcwWeb/Electrical-Engineering-and-Computer-Science/6-856JRandomized-AlgorithmsFall2002/CourseHome.xml</adlcp:location>
  </metadata>
  <organizations default="ocw_6-856JRandomized-AlgorithmsFall2002">
    <organization identifier="ocw_6-856JRandomized-AlgorithmsFall2002">
      <title>Randomized Algorithms</title>
      <item identifier="i_6-856JRandomized-AlgorithmsFall2002.CourseHome" identifierref="r_OcwWeb.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.CourseHome.index.htm" ocw:sectionTemplateType="CourseHomePage" ocw:sectionTemplateVersion="2007-10-12">
        <title>Randomized Algorithms</title>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.CourseHome.chp_algorithm_1.jpg" identifierref="r_NR.rdonlyres.Global.A.A3908774-DC8D-473C-BD55-85FC0885BC56.0.chp_algorithm_1.jpg">
          <title>Unstructured grid for a four element airfoil</title>
        </item>
      </item>
      <item identifier="i_6-856JRandomized-AlgorithmsFall2002.Syllabus" identifierref="r_OcwWeb.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.Syllabus.index.htm" ocw:sectionTemplateType="GenericOther" ocw:sectionTemplateVersion="2007-10-12">
        <title>Syllabus</title>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.Syllabus.a_logo_17.gif" identifierref="r_NR.rdonlyres.Global.2.207C16E2-AABD-48E3-9DFB-9CE5011549BC.0.a_logo_17.gif">
          <title>Amazon Logo</title>
        </item>
      </item>
      <item identifier="i_6-856JRandomized-AlgorithmsFall2002.Calendar" identifierref="r_OcwWeb.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.Calendar.index.htm" ocw:sectionTemplateType="GenericOther" ocw:sectionTemplateVersion="2007-10-12">
        <title>Calendar</title>
      </item>
      <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes" identifierref="r_OcwWeb.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.LectureNotes.index.htm" ocw:sectionTemplateType="GenericOther" ocw:sectionTemplateVersion="2007-10-12">
        <title>Lecture Notes</title>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes.n1.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.7594FDEB-A1F0-4375-B6DB-69E8EC83F06A.0.n1.pdf">
          <title>Introduction to Randomized Algorithms</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes.n2.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.EEF0212A-7A05-455C-8134-D70C38A80CE3.0.n2.pdf">
          <title>Min-Cut, Complexity Theory, Game Tree Evaluation</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes.n3.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.5DA291F5-A5A8-46A5-A9D6-93F5957BA25C.0.n3.pdf">
          <title>Adelman's Theorem, Game Theory, Lower Bounds </title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes.n4.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.C98EE649-75E1-4DE4-B31B-F1E54B8D5A95.0.n4.pdf">
          <title>Coupon Collecting, Stable Marriage, Markov Inequality</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes.n5.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.1A049FF6-2903-43DD-9A4B-589B12DA94A2.0.n5.pdf">
          <title>Chebyshev, Two Point Sampling, Chernoff </title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes.n6.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.CD859C43-F7E6-4E5E-AFBA-A6B182BAE5E0.0.n6.pdf">
          <title>Median Finding, Routing</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes.n7.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.362EEC35-343F-4877-9331-756FF00A9640.0.n7.pdf">
          <title>Probabilistic Method, Expanders, Wiring, MAX SAT</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes.n8.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.CCC378DE-91C8-4F04-9E6B-D62088012C16.0.n8.pdf">
          <title>Method of Conditional Probabilities and Expectations, Fingerprinting</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes.n9.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.3B940133-C125-4015-B93D-4F4FD731878C.0.n9.pdf">
          <title>Hashing, Perfect Hash Families, Freivald's Technique </title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes.n10.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.BE8E290F-2286-4C05-9B09-36409EAC851B.0.n10.pdf">
          <title>Fingerprints by Polynomials, Perfect Matching, Hashing</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes.n11.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.42D342D5-BCF6-4DEC-96B0-41279FE9BCE4.0.n11.pdf">
          <title>Shortest Paths</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes.n12.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.F577E2AF-0C04-4375-9C2B-5EB5467235E8.0.n12.pdf">
          <title>Parallel Algorithms</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes.n13.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.26FC388D-A4D6-4FC8-9E21-C75E0CCC23D2.0.n13.pdf">
          <title>Maximal Independent Sets</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes.n14.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.0AE152C0-515D-4E01-8981-E1971C6E0340.0.n14.pdf">
          <title>Minimum Spanning Trees</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes.n15.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.B4B2E8DC-4E04-4A78-B7BA-5684117AE7F8.0.n15.pdf">
          <title>Polling, Minimum Cut, Transitive Closure</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes.n16.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.47CB15DA-F54F-4B28-91EA-CB0A857E2207.0.n16.pdf">
          <title>Estimating Min-cut Size</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes.n17.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.2B82D395-2E8C-4311-A542-564F40EA2A11.0.n17.pdf">
          <title>Linear Programming</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes.n18.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.0C56229A-23C9-4E46-9262-5D436B530475.0.n18.pdf">
          <title>DNF Counting</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes.n19.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.99EEF696-EB46-467A-9531-1824F65D6A9B.0.n19.pdf">
          <title>Markov Chains</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes.n20.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.207A2035-690A-4B04-A8C2-630120D9CF90.0.n20.pdf">
          <title>UTS, Eigenvalue Analysis, Expanders </title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes.n21.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.A44CB128-CC8F-410B-81D9-C0649B12C432.0.n21.pdf">
          <title>Expander based Pseudo-random Generator</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes.n22.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.A229C64E-17A5-4CAA-9426-6FDA704358B8.0.n22.pdf">
          <title>Sampling with Markov Chains, Coupling</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes.n23.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.2499BE35-CF85-4983-8E9C-CB7BB5008149.0.n23.pdf">
          <title>Computational Geometry</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes.n24.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.29C4B25E-BCD8-42EC-8DDA-B89B4F445EC2.0.n24.pdf">
          <title>Randomized Incremental Consturction</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.LectureNotes.n25.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.E668481E-91C0-4A67-B511-3816EBA9AABF.0.n25.pdf">
          <title>Trapezoidal Decomposition, Treaps </title>
        </item>
      </item>
      <item identifier="i_6-856JRandomized-AlgorithmsFall2002.Assignments" identifierref="r_OcwWeb.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.Assignments.index.htm" ocw:sectionTemplateType="GenericOther" ocw:sectionTemplateVersion="2007-10-12">
        <title>Assignments</title>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.Assignments.hw1.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.4BB0A30A-B800-4DF4-8F1B-21E7A4270B2B.0.hw1.pdf">
          <title>Homework 1</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.Assignments.ans1.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.377940B7-8052-4F21-B8BD-B7850FB01E51.0.ans1.pdf">
          <title>Homework 1 Solutions</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.Assignments.hw2.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.905D073A-D76F-45E1-9E38-EAA245330274.0.hw2.pdf">
          <title>Homework 2</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.Assignments.ans2.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.A6D4105A-D7D0-433B-930B-16033B353001.0.ans2.pdf">
          <title>Homework 2 Solutions</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.Assignments.hw3.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.898A4116-8BF7-4BFA-9371-9D2A7ACE0411.0.hw3.pdf">
          <title>Homework 3</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.Assignments.ans3.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.C97B8BEF-9028-413C-A24C-51DB037F7AD4.0.ans3.pdf">
          <title>Homework 3 Solutions</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.Assignments.hw4.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.36C501D7-9774-4106-AC8D-35C80BF8AC30.0.hw4.pdf">
          <title>Homework 4</title>
        </item>
        <item identifier="i_6-856JRandomized-AlgorithmsFall2002.Assignments.ans4.pdf" identifierref="r_NR.rdonlyres.Electrical-Engineering-and-Computer-Science.6-856JRandomized-AlgorithmsFall2002.EC4A99D3-465B-4196-88F2-BD647A90A3FC.0.ans4.pdf">
          <title>Homework 4 Solutions</title>
        </item>