<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@abf67792c5c44e1888a8c3212fe889b7" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="VerticalStudentView" data-block-type="vertical" data-graded="False" data-has-score="False" data-request-token="af119002c06411ef81320efa3cc2f29f">
<h2 class="hd hd-2 unit-title">Introduction</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@html+block@144821ca60d3494f81c3a052fa048152">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@144821ca60d3494f81c3a052fa048152" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="XBlockToXModuleShim" data-block-type="html" data-graded="False" data-has-score="False" data-request-token="af119002c06411ef81320efa3cc2f29f">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>Read <a href="/assets/courseware/v1/d654c70d7bd563a57216f76bd8bbf308/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_Session22.pdf" target="[object Object]">Chapter 11.6 (PDF)</a> of <em>Mathematics for Computer Science</em> for 2.11 Stable Matching.</p>
<p>View the <a href="/assets/courseware/v1/50fd349418ec06b1623524f760239263/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_cp22.pdf" target="[object Object]">Section 2.11 In-Class Questions (PDF)</a></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@ffd503ba689745c0b0fc4f16bb89ba78" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="VerticalStudentView" data-block-type="vertical" data-graded="False" data-has-score="False" data-request-token="af119002c06411ef81320efa3cc2f29f">
<h2 class="hd hd-2 unit-title">Lecture Video | Stable Matching</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@video+block@8ae053f5a5a04ac9b8c55b6b9825595e">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@video+block@8ae053f5a5a04ac9b8c55b6b9825595e" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="XBlockToXModuleShim" data-block-type="video" data-graded="False" data-has-score="False" data-request-token="af119002c06411ef81320efa3cc2f29f">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Stable Matching </h3>
<div
id="video_8ae053f5a5a04ac9b8c55b6b9825595e"
class="video closed"
data-metadata='{"captionDataDir": null, "end": 0.0, "showCaptions": "true", "start": 0.0, "poster": null, "transcriptLanguages": {"en": "English"}, "streams": "1.00:RE5PmdGNgj0", "lmsRootURL": "https://openlearninglibrary.mit.edu", "autohideHtml5": false, "recordedYoutubeIsAvailable": true, "publishCompletionUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@8ae053f5a5a04ac9b8c55b6b9825595e/handler/publish_completion", "completionPercentage": 0.95, "speed": null, "ytApiUrl": "https://www.youtube.com/iframe_api", "ytMetadataEndpoint": "", "sources": ["https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_stablematch_video2_ipod.mp4"], "duration": 0.0, "prioritizeHls": false, "transcriptTranslationUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@8ae053f5a5a04ac9b8c55b6b9825595e/handler/transcript/translation/__lang__", "autoAdvance": false, "completionEnabled": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@8ae053f5a5a04ac9b8c55b6b9825595e/handler/transcript/available_translations", "ytTestTimeout": 1500, "autoplay": false, "savedVideoPosition": 0.0, "generalSpeed": 1.0, "saveStateUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@8ae053f5a5a04ac9b8c55b6b9825595e/handler/xmodule_handler/save_user_state", "transcriptLanguage": "en", "saveStateEnabled": false}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="8ae053f5a5a04ac9b8c55b6b9825595e"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_8ae053f5a5a04ac9b8c55b6b9825595e">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_8ae053f5a5a04ac9b8c55b6b9825595e">
<div class="wrapper-download-video">
<h4 class="hd hd-5">Video</h4>
<a class="btn-link video-sources video-download-button" href="https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_stablematch_video2_ipod.mp4">
Download video file
</a>
</div>
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@8ae053f5a5a04ac9b8c55b6b9825595e/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@8ae053f5a5a04ac9b8c55b6b9825595e/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:OCW+6.042J+2T2019+type@html+block@75835bd683824b56b7c2e44768dcdbab">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@75835bd683824b56b7c2e44768dcdbab" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="XBlockToXModuleShim" data-block-type="html" data-graded="False" data-has-score="False" data-request-token="af119002c06411ef81320efa3cc2f29f">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>Download a copy of the slides for <a href="/assets/courseware/v1/df88d46bd2d149efb373ff0acf785dd6/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_stablematchg.pdf" target="[object Object]">Stable Matching (PDF)</a></p>
<p><a href="/assets/courseware/v1/aa2758bb818aa7a4ea6195535aa7cd07/asset-v1:OCW+6.042J+2T2019+type@asset+block/StableMatching_2.11_Lectrans.pdf" target="[object Object]">Lecture video transcript (PDF)</a></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@e3ec8d6cca0b4be3a55b7be9988e8d96" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="VerticalStudentView" data-block-type="vertical" data-graded="False" data-has-score="False" data-request-token="af119002c06411ef81320efa3cc2f29f">
<h2 class="hd hd-2 unit-title">Lecture Video | Mating Ritual</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@video+block@7f8b3d2d9ee449ce89bdaaf38fab7617">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@video+block@7f8b3d2d9ee449ce89bdaaf38fab7617" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="XBlockToXModuleShim" data-block-type="video" data-graded="False" data-has-score="False" data-request-token="af119002c06411ef81320efa3cc2f29f">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Mating Ritual</h3>
<div
id="video_7f8b3d2d9ee449ce89bdaaf38fab7617"
class="video closed"
data-metadata='{"captionDataDir": null, "end": 0.0, "showCaptions": "true", "start": 0.0, "poster": null, "transcriptLanguages": {"en": "English"}, "streams": "1.00:6vgHIImFwHo", "lmsRootURL": "https://openlearninglibrary.mit.edu", "autohideHtml5": false, "recordedYoutubeIsAvailable": true, "publishCompletionUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@7f8b3d2d9ee449ce89bdaaf38fab7617/handler/publish_completion", "completionPercentage": 0.95, "speed": null, "ytApiUrl": "https://www.youtube.com/iframe_api", "ytMetadataEndpoint": "", "sources": ["https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_stableritual_video_ipod.mp4"], "duration": 0.0, "prioritizeHls": false, "transcriptTranslationUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@7f8b3d2d9ee449ce89bdaaf38fab7617/handler/transcript/translation/__lang__", "autoAdvance": false, "completionEnabled": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@7f8b3d2d9ee449ce89bdaaf38fab7617/handler/transcript/available_translations", "ytTestTimeout": 1500, "autoplay": false, "savedVideoPosition": 0.0, "generalSpeed": 1.0, "saveStateUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@7f8b3d2d9ee449ce89bdaaf38fab7617/handler/xmodule_handler/save_user_state", "transcriptLanguage": "en", "saveStateEnabled": false}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="7f8b3d2d9ee449ce89bdaaf38fab7617"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_7f8b3d2d9ee449ce89bdaaf38fab7617">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_7f8b3d2d9ee449ce89bdaaf38fab7617">
<div class="wrapper-download-video">
<h4 class="hd hd-5">Video</h4>
<a class="btn-link video-sources video-download-button" href="https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_stableritual_video_ipod.mp4">
Download video file
</a>
</div>
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@7f8b3d2d9ee449ce89bdaaf38fab7617/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@7f8b3d2d9ee449ce89bdaaf38fab7617/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:OCW+6.042J+2T2019+type@html+block@d1f790dee3db4ba396ad43763bc05b26">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@d1f790dee3db4ba396ad43763bc05b26" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="XBlockToXModuleShim" data-block-type="html" data-graded="False" data-has-score="False" data-request-token="af119002c06411ef81320efa3cc2f29f">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>Download a copy of the slides for <a href="/assets/courseware/v1/398204cb2ab212b6b0b69d8afdb1d6fa/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_Mating_ritual.pdf" target="[object Object]">Mating Ritual (PDF)</a></p>
<p><a href="/assets/courseware/v1/a9250dc0e23a114b72b66102bc737470/asset-v1:OCW+6.042J+2T2019+type@asset+block/MatingRitual_2.11_Lectrans.pdf" target="[object Object]">Lecture video transcript (PDF)</a></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@cbbb6210a04144a8b19837c3652146e0" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="VerticalStudentView" data-block-type="vertical" data-graded="False" data-has-score="False" data-request-token="af119002c06411ef81320efa3cc2f29f">
<h2 class="hd hd-2 unit-title">Exercise | Derived Variables</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@a7e33686c4e64f1986b230eaffba15b8">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@a7e33686c4e64f1986b230eaffba15b8" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="XBlockToXModuleShim" data-block-type="problem" data-graded="False" data-has-score="True" data-request-token="af119002c06411ef81320efa3cc2f29f">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_a7e33686c4e64f1986b230eaffba15b8" class="problems-wrapper" role="group"
aria-labelledby="a7e33686c4e64f1986b230eaffba15b8-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@a7e33686c4e64f1986b230eaffba15b8" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@a7e33686c4e64f1986b230eaffba15b8/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="2"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="a7e33686c4e64f1986b230eaffba15b8-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@a7e33686c4e64f1986b230eaffba15b8-problem-progress" tabindex="-1">
Derived Variables
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@a7e33686c4e64f1986b230eaffba15b8-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="inputtype option-input ">
<label class="problem-group-label" for="input_a7e33686c4e64f1986b230eaffba15b8_2_1" id="label_a7e33686c4e64f1986b230eaffba15b8_2_1">1. In the mating ritual, the rank of each girl&#8217;s current best option is:</label>
<select name="input_a7e33686c4e64f1986b230eaffba15b8_2_1" id="input_a7e33686c4e64f1986b230eaffba15b8_2_1" aria-describedby="status_a7e33686c4e64f1986b230eaffba15b8_2_1">
<option value="option_a7e33686c4e64f1986b230eaffba15b8_2_1_dummy_default">Select an option</option>
<option value="strictly increasing"> strictly increasing</option>
<option value="weakly increasing"> weakly increasing</option>
<option value="strictly decreasing"> strictly decreasing</option>
<option value="weakly decreasing"> weakly decreasing</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_a7e33686c4e64f1986b230eaffba15b8_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_a7e33686c4e64f1986b230eaffba15b8_2_1"/>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="inputtype option-input ">
<label class="problem-group-label" for="input_a7e33686c4e64f1986b230eaffba15b8_3_1" id="label_a7e33686c4e64f1986b230eaffba15b8_3_1">2. The rank of each boy&#8217;s current best option is:</label>
<select name="input_a7e33686c4e64f1986b230eaffba15b8_3_1" id="input_a7e33686c4e64f1986b230eaffba15b8_3_1" aria-describedby="status_a7e33686c4e64f1986b230eaffba15b8_3_1">
<option value="option_a7e33686c4e64f1986b230eaffba15b8_3_1_dummy_default">Select an option</option>
<option value="strictly increasing"> strictly increasing</option>
<option value="weakly increasing"> weakly increasing</option>
<option value="strictly decreasing"> strictly decreasing</option>
<option value="weakly decreasing"> weakly decreasing</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_a7e33686c4e64f1986b230eaffba15b8_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_a7e33686c4e64f1986b230eaffba15b8_3_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Derived Variables" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_a7e33686c4e64f1986b230eaffba15b8" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_a7e33686c4e64f1986b230eaffba15b8">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="reset problem-action-btn btn-default btn-small" data-value="Reset"><span class="icon fa fa-refresh" aria-hidden="true"></span><span aria-hidden="true">Reset</span><span class="sr">Reset your answer</span></button>
</span>
<span class="problem-action-button-wrapper">
<button type="button" class="show problem-action-btn btn-default btn-small" aria-describedby="a7e33686c4e64f1986b230eaffba15b8-problem-title"><span class="icon fa fa-info-circle" aria-hidden="true"></span><span class="show-label">Show Answer</span></button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="a7e33686c4e64f1986b230eaffba15b8-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="a7e33686c4e64f1986b230eaffba15b8-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="a7e33686c4e64f1986b230eaffba15b8-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@c858bc7b9637410f9a7947d00abbff38" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="VerticalStudentView" data-block-type="vertical" data-graded="False" data-has-score="False" data-request-token="af119002c06411ef81320efa3cc2f29f">
<h2 class="hd hd-2 unit-title">Exercise | Mating Ritual</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@057047e64eac49b386c7102180fdc517">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@057047e64eac49b386c7102180fdc517" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="XBlockToXModuleShim" data-block-type="problem" data-graded="False" data-has-score="True" data-request-token="af119002c06411ef81320efa3cc2f29f">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_057047e64eac49b386c7102180fdc517" class="problems-wrapper" role="group"
aria-labelledby="057047e64eac49b386c7102180fdc517-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@057047e64eac49b386c7102180fdc517" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@057047e64eac49b386c7102180fdc517/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="2"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="057047e64eac49b386c7102180fdc517-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@057047e64eac49b386c7102180fdc517-problem-progress" tabindex="-1">
Mating Ritual
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@057047e64eac49b386c7102180fdc517-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="inputtype option-input ">
<label class="problem-group-label" for="input_057047e64eac49b386c7102180fdc517_2_1" id="label_057047e64eac49b386c7102180fdc517_2_1">1. The Mating Ritual.....</label>
<select name="input_057047e64eac49b386c7102180fdc517_2_1" id="input_057047e64eac49b386c7102180fdc517_2_1" aria-describedby="status_057047e64eac49b386c7102180fdc517_2_1">
<option value="option_057047e64eac49b386c7102180fdc517_2_1_dummy_default">Select an option</option>
<option value="is deterministic and always produces the same matching, which may or may not be stable"> is deterministic and always produces the same matching, which may or may not be stable</option>
<option value="requires that no two boys have the same list"> requires that no two boys have the same list</option>
<option value="terminates with only stable matchings, but not necessarily the same one"> terminates with only stable matchings, but not necessarily the same one</option>
<option value="is deterministic and always produces the same unique stable matchings"> is deterministic and always produces the same unique stable matchings</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_057047e64eac49b386c7102180fdc517_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_057047e64eac49b386c7102180fdc517_2_1"/>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="inputtype option-input ">
<label class="problem-group-label" for="input_057047e64eac49b386c7102180fdc517_3_1" id="label_057047e64eac49b386c7102180fdc517_3_1">2. The total number of names remaining on each boy's list is:</label>
<select name="input_057047e64eac49b386c7102180fdc517_3_1" id="input_057047e64eac49b386c7102180fdc517_3_1" aria-describedby="status_057047e64eac49b386c7102180fdc517_3_1">
<option value="option_057047e64eac49b386c7102180fdc517_3_1_dummy_default">Select an option</option>
<option value="strictly increasing"> strictly increasing</option>
<option value="weakly increasing"> weakly increasing</option>
<option value="strictly decreasing"> strictly decreasing</option>
<option value="weakly decreasing"> weakly decreasing</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_057047e64eac49b386c7102180fdc517_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_057047e64eac49b386c7102180fdc517_3_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Mating Ritual" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_057047e64eac49b386c7102180fdc517" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_057047e64eac49b386c7102180fdc517">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="reset problem-action-btn btn-default btn-small" data-value="Reset"><span class="icon fa fa-refresh" aria-hidden="true"></span><span aria-hidden="true">Reset</span><span class="sr">Reset your answer</span></button>
</span>
<span class="problem-action-button-wrapper">
<button type="button" class="show problem-action-btn btn-default btn-small" aria-describedby="057047e64eac49b386c7102180fdc517-problem-title"><span class="icon fa fa-info-circle" aria-hidden="true"></span><span class="show-label">Show Answer</span></button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="057047e64eac49b386c7102180fdc517-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="057047e64eac49b386c7102180fdc517-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="057047e64eac49b386c7102180fdc517-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@8d6537a7ab3d4447be241e04dc8154d5" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="VerticalStudentView" data-block-type="vertical" data-graded="False" data-has-score="False" data-request-token="af119002c06411ef81320efa3cc2f29f">
<h2 class="hd hd-2 unit-title">Lecture Video | Optimal Stable Matching</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@video+block@28884c71b9ec429fa2c979ed31038b48">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@video+block@28884c71b9ec429fa2c979ed31038b48" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="XBlockToXModuleShim" data-block-type="video" data-graded="False" data-has-score="False" data-request-token="af119002c06411ef81320efa3cc2f29f">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Optimal Stable Matching </h3>
<div
id="video_28884c71b9ec429fa2c979ed31038b48"
class="video closed"
data-metadata='{"captionDataDir": null, "end": 0.0, "showCaptions": "true", "start": 0.0, "poster": null, "transcriptLanguages": {"en": "English"}, "streams": "1.00:n4KKgKpp--0", "lmsRootURL": "https://openlearninglibrary.mit.edu", "autohideHtml5": false, "recordedYoutubeIsAvailable": true, "publishCompletionUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@28884c71b9ec429fa2c979ed31038b48/handler/publish_completion", "completionPercentage": 0.95, "speed": null, "ytApiUrl": "https://www.youtube.com/iframe_api", "ytMetadataEndpoint": "", "sources": ["https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_stableoptimal_ipod.mp4"], "duration": 0.0, "prioritizeHls": false, "transcriptTranslationUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@28884c71b9ec429fa2c979ed31038b48/handler/transcript/translation/__lang__", "autoAdvance": false, "completionEnabled": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@28884c71b9ec429fa2c979ed31038b48/handler/transcript/available_translations", "ytTestTimeout": 1500, "autoplay": false, "savedVideoPosition": 0.0, "generalSpeed": 1.0, "saveStateUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@28884c71b9ec429fa2c979ed31038b48/handler/xmodule_handler/save_user_state", "transcriptLanguage": "en", "saveStateEnabled": false}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="28884c71b9ec429fa2c979ed31038b48"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_28884c71b9ec429fa2c979ed31038b48">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_28884c71b9ec429fa2c979ed31038b48">
<div class="wrapper-download-video">
<h4 class="hd hd-5">Video</h4>
<a class="btn-link video-sources video-download-button" href="https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_stableoptimal_ipod.mp4">
Download video file
</a>
</div>
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@28884c71b9ec429fa2c979ed31038b48/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@28884c71b9ec429fa2c979ed31038b48/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:OCW+6.042J+2T2019+type@html+block@853f13d5459c4735b68dfca3d755bf9c">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@853f13d5459c4735b68dfca3d755bf9c" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="XBlockToXModuleShim" data-block-type="html" data-graded="False" data-has-score="False" data-request-token="af119002c06411ef81320efa3cc2f29f">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>Download a copy of the slides for <a href="/assets/courseware/v1/9f7960a083c2a9a8d0580a01cad35395/asset-v1:OCW+6.042J+2T2019+type@asset+block/Unit_II_2.11_Optimal_Stable_Matching_Slides.pdf" target="[object Object]">Optimal Stable Matching (PDF)</a></p>
<p><a href="/assets/courseware/v1/8f752c35c06afae7db5abaa987a97c4a/asset-v1:OCW+6.042J+2T2019+type@asset+block/OptimalStableMatching_2.11_Lectrans.pdf" target="[object Object]">Lecture video transcript (PDF)</a></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@0680f65a8c1245d3a4b633b120337cd7" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="VerticalStudentView" data-block-type="vertical" data-graded="False" data-has-score="False" data-request-token="af119002c06411ef81320efa3cc2f29f">
<h2 class="hd hd-2 unit-title">Exercise | Boy Optimal</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@c970c2898018401da0225942b3938bc0">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@c970c2898018401da0225942b3938bc0" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="XBlockToXModuleShim" data-block-type="problem" data-graded="False" data-has-score="True" data-request-token="af119002c06411ef81320efa3cc2f29f">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_c970c2898018401da0225942b3938bc0" class="problems-wrapper" role="group"
aria-labelledby="c970c2898018401da0225942b3938bc0-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@c970c2898018401da0225942b3938bc0" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@c970c2898018401da0225942b3938bc0/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="c970c2898018401da0225942b3938bc0-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@c970c2898018401da0225942b3938bc0-problem-progress" tabindex="-1">
Boy Optimal
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@c970c2898018401da0225942b3938bc0-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="inputtype option-input ">
<label class="problem-group-label" for="input_c970c2898018401da0225942b3938bc0_2_1" id="label_c970c2898018401da0225942b3938bc0_2_1">What is the definition of a "boy optimal" marriage?</label>
<select name="input_c970c2898018401da0225942b3938bc0_2_1" id="input_c970c2898018401da0225942b3938bc0_2_1" aria-describedby="status_c970c2898018401da0225942b3938bc0_2_1">
<option value="option_c970c2898018401da0225942b3938bc0_2_1_dummy_default">Select an option</option>
<option value="The boy is married to the highest ranked girl he can stably marry"> The boy is married to the highest ranked girl he can stably marry</option>
<option value="All boys get married to the girl at the top of their lists"> All boys get married to the girl at the top of their lists</option>
<option value="Each girl is married to the lowest ranked boy she can stably marry"> Each girl is married to the lowest ranked boy she can stably marry</option>
<option value="A rogue marriage, but the boy is satisfied"> A rogue marriage, but the boy is satisfied</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_c970c2898018401da0225942b3938bc0_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_c970c2898018401da0225942b3938bc0_2_1"/>
</div></div>
<div class="solution-span">
<span id="solution_c970c2898018401da0225942b3938bc0_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Boy Optimal" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_c970c2898018401da0225942b3938bc0" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_c970c2898018401da0225942b3938bc0">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="reset problem-action-btn btn-default btn-small" data-value="Reset"><span class="icon fa fa-refresh" aria-hidden="true"></span><span aria-hidden="true">Reset</span><span class="sr">Reset your answer</span></button>
</span>
<span class="problem-action-button-wrapper">
<button type="button" class="show problem-action-btn btn-default btn-small" aria-describedby="c970c2898018401da0225942b3938bc0-problem-title"><span class="icon fa fa-info-circle" aria-hidden="true"></span><span class="show-label">Show Answer</span></button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="c970c2898018401da0225942b3938bc0-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="c970c2898018401da0225942b3938bc0-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="c970c2898018401da0225942b3938bc0-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@ff3bf3b8373149779807fe67a5840f24" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="VerticalStudentView" data-block-type="vertical" data-graded="False" data-has-score="False" data-request-token="af119002c06411ef81320efa3cc2f29f">
<h2 class="hd hd-2 unit-title">Lecture Video | Bipartite Matching</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@video+block@27ab97efa43a400aa231ffeb94bbc2d7">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@video+block@27ab97efa43a400aa231ffeb94bbc2d7" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="XBlockToXModuleShim" data-block-type="video" data-graded="False" data-has-score="False" data-request-token="af119002c06411ef81320efa3cc2f29f">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Bipartite Matching </h3>
<div
id="video_27ab97efa43a400aa231ffeb94bbc2d7"
class="video closed"
data-metadata='{"captionDataDir": null, "end": 0.0, "showCaptions": "true", "start": 0.0, "poster": null, "transcriptLanguages": {"en": "English"}, "streams": "1.00:HZLKDC9OSaQ", "lmsRootURL": "https://openlearninglibrary.mit.edu", "autohideHtml5": false, "recordedYoutubeIsAvailable": true, "publishCompletionUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@27ab97efa43a400aa231ffeb94bbc2d7/handler/publish_completion", "completionPercentage": 0.95, "speed": null, "ytApiUrl": "https://www.youtube.com/iframe_api", "ytMetadataEndpoint": "", "sources": ["https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_bipartitematch_video_ipod.mp4"], "duration": 0.0, "prioritizeHls": false, "transcriptTranslationUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@27ab97efa43a400aa231ffeb94bbc2d7/handler/transcript/translation/__lang__", "autoAdvance": false, "completionEnabled": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@27ab97efa43a400aa231ffeb94bbc2d7/handler/transcript/available_translations", "ytTestTimeout": 1500, "autoplay": false, "savedVideoPosition": 0.0, "generalSpeed": 1.0, "saveStateUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@27ab97efa43a400aa231ffeb94bbc2d7/handler/xmodule_handler/save_user_state", "transcriptLanguage": "en", "saveStateEnabled": false}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="27ab97efa43a400aa231ffeb94bbc2d7"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_27ab97efa43a400aa231ffeb94bbc2d7">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_27ab97efa43a400aa231ffeb94bbc2d7">
<div class="wrapper-download-video">
<h4 class="hd hd-5">Video</h4>
<a class="btn-link video-sources video-download-button" href="https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_bipartitematch_video_ipod.mp4">
Download video file
</a>
</div>
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@27ab97efa43a400aa231ffeb94bbc2d7/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@27ab97efa43a400aa231ffeb94bbc2d7/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:OCW+6.042J+2T2019+type@html+block@1cc111ff6488497eaaade4efeecacd45">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@1cc111ff6488497eaaade4efeecacd45" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="XBlockToXModuleShim" data-block-type="html" data-graded="False" data-has-score="False" data-request-token="af119002c06411ef81320efa3cc2f29f">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>Download a copy of the slides for <a href="/assets/courseware/v1/d7106c6c29442fb846adf23d1168c4a6/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_bip_mtchig.pdf" target="[object Object]">Bipartite Matching (PDF)</a></p>
<p><a href="/assets/courseware/v1/85a2d1feab2f2ba23fa0d67e56a435a2/asset-v1:OCW+6.042J+2T2019+type@asset+block/BipartiteMatching_2.11_Lectrans.pdf" target="[object Object]">Lecture video transcript (PDF)</a></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@21fc939964cd437aa7bcb9ccc7648734" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="VerticalStudentView" data-block-type="vertical" data-graded="False" data-has-score="False" data-request-token="af119002c06411ef81320efa3cc2f29f">
<h2 class="hd hd-2 unit-title">Exercise | Bipartite Equivalence Relation</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@cb05eafffe784ec392cb12897ba1bed5">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@cb05eafffe784ec392cb12897ba1bed5" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="XBlockToXModuleShim" data-block-type="problem" data-graded="False" data-has-score="True" data-request-token="af119002c06411ef81320efa3cc2f29f">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_cb05eafffe784ec392cb12897ba1bed5" class="problems-wrapper" role="group"
aria-labelledby="cb05eafffe784ec392cb12897ba1bed5-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@cb05eafffe784ec392cb12897ba1bed5" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@cb05eafffe784ec392cb12897ba1bed5/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="cb05eafffe784ec392cb12897ba1bed5-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@cb05eafffe784ec392cb12897ba1bed5-problem-progress" tabindex="-1">
Bipartite Equivalence Relation
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@cb05eafffe784ec392cb12897ba1bed5-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="inputtype option-input ">
<label class="problem-group-label" for="input_cb05eafffe784ec392cb12897ba1bed5_2_1" id="label_cb05eafffe784ec392cb12897ba1bed5_2_1">When mapping girls to boys in a bipartite graph with more boys than girls, what sort of equivalence relation are we looking to find?</label>
<select name="input_cb05eafffe784ec392cb12897ba1bed5_2_1" id="input_cb05eafffe784ec392cb12897ba1bed5_2_1" aria-describedby="status_cb05eafffe784ec392cb12897ba1bed5_2_1">
<option value="option_cb05eafffe784ec392cb12897ba1bed5_2_1_dummy_default">Select an option</option>
<option value="total surjection"> total surjection</option>
<option value="total injection"> total injection</option>
<option value="total bijection"> total bijection</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_cb05eafffe784ec392cb12897ba1bed5_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
<p class="answer" id="answer_cb05eafffe784ec392cb12897ba1bed5_2_1"/>
</div></div>
<div class="solution-span">
<span id="solution_cb05eafffe784ec392cb12897ba1bed5_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Bipartite Equivalence Relation" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_cb05eafffe784ec392cb12897ba1bed5" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_cb05eafffe784ec392cb12897ba1bed5">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="reset problem-action-btn btn-default btn-small" data-value="Reset"><span class="icon fa fa-refresh" aria-hidden="true"></span><span aria-hidden="true">Reset</span><span class="sr">Reset your answer</span></button>
</span>
<span class="problem-action-button-wrapper">
<button type="button" class="show problem-action-btn btn-default btn-small" aria-describedby="cb05eafffe784ec392cb12897ba1bed5-problem-title"><span class="icon fa fa-info-circle" aria-hidden="true"></span><span class="show-label">Show Answer</span></button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="cb05eafffe784ec392cb12897ba1bed5-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="cb05eafffe784ec392cb12897ba1bed5-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="cb05eafffe784ec392cb12897ba1bed5-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@074f0e523b3d43efbb9dca2e542520c4" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="VerticalStudentView" data-block-type="vertical" data-graded="False" data-has-score="False" data-request-token="af119002c06411ef81320efa3cc2f29f">
<h2 class="hd hd-2 unit-title">Lecture Video | Hall's Theorem</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@video+block@1cd0f5a66704444c834b86d929072caa">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@video+block@1cd0f5a66704444c834b86d929072caa" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="XBlockToXModuleShim" data-block-type="video" data-graded="False" data-has-score="False" data-request-token="af119002c06411ef81320efa3cc2f29f">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Hall's Theorem</h3>
<div
id="video_1cd0f5a66704444c834b86d929072caa"
class="video closed"
data-metadata='{"captionDataDir": null, "end": 0.0, "showCaptions": "true", "start": 0.0, "poster": null, "transcriptLanguages": {"en": "English"}, "streams": "1.00:i5AWE-OoOsY", "lmsRootURL": "https://openlearninglibrary.mit.edu", "autohideHtml5": false, "recordedYoutubeIsAvailable": true, "publishCompletionUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@1cd0f5a66704444c834b86d929072caa/handler/publish_completion", "completionPercentage": 0.95, "speed": null, "ytApiUrl": "https://www.youtube.com/iframe_api", "ytMetadataEndpoint": "", "sources": ["https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_halltheorem_ipod.mp4"], "duration": 0.0, "prioritizeHls": false, "transcriptTranslationUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@1cd0f5a66704444c834b86d929072caa/handler/transcript/translation/__lang__", "autoAdvance": false, "completionEnabled": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@1cd0f5a66704444c834b86d929072caa/handler/transcript/available_translations", "ytTestTimeout": 1500, "autoplay": false, "savedVideoPosition": 0.0, "generalSpeed": 1.0, "saveStateUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@1cd0f5a66704444c834b86d929072caa/handler/xmodule_handler/save_user_state", "transcriptLanguage": "en", "saveStateEnabled": false}'
data-bumper-metadata='null'
data-autoadvance-enabled="False"
data-poster='null'
tabindex="-1"
>
<div class="focus_grabber first"></div>
<div class="tc-wrapper">
<div class="video-wrapper">
<span tabindex="0" class="spinner" aria-hidden="false" aria-label="Loading video player"></span>
<span tabindex="-1" class="btn-play fa fa-youtube-play fa-2x is-hidden" aria-hidden="true" aria-label="Play video"></span>
<div class="video-player-pre"></div>
<div class="video-player">
<div id="1cd0f5a66704444c834b86d929072caa"></div>
<h4 class="hd hd-4 video-error is-hidden">No playable video sources found.</h4>
<h4 class="hd hd-4 video-hls-error is-hidden">
Your browser does not support this video format. Try using a different browser.
</h4>
</div>
<div class="video-player-post"></div>
<div class="closed-captions"></div>
<div class="video-controls is-hidden">
<div>
<div class="vcr"><div class="vidtime">0:00 / 0:00</div></div>
<div class="secondary-controls"></div>
</div>
</div>
</div>
</div>
<div class="focus_grabber last"></div>
<h3 class="hd hd-4 downloads-heading sr" id="video-download-transcripts_1cd0f5a66704444c834b86d929072caa">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_1cd0f5a66704444c834b86d929072caa">
<div class="wrapper-download-video">
<h4 class="hd hd-5">Video</h4>
<a class="btn-link video-sources video-download-button" href="https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_halltheorem_ipod.mp4">
Download video file
</a>
</div>
<div class="wrapper-download-transcripts">
<h4 class="hd hd-5">Transcripts</h4>
<ul class="list-download-transcripts">
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@1cd0f5a66704444c834b86d929072caa/handler/transcript/download" data-value="srt">Download SubRip (.srt) file</a>
</li>
<li class="transcript-option">
<a class="btn btn-link" href="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@1cd0f5a66704444c834b86d929072caa/handler/transcript/download" data-value="txt">Download Text (.txt) file</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:OCW+6.042J+2T2019+type@html+block@dd658d290bd84dd78f6c25eb7c95080e">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@dd658d290bd84dd78f6c25eb7c95080e" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="XBlockToXModuleShim" data-block-type="html" data-graded="False" data-has-score="False" data-request-token="af119002c06411ef81320efa3cc2f29f">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>Download a copy of the slides for <a href="/assets/courseware/v1/1a2d2d431f17caa0aedad26e2a42222a/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_halls_thorem.pdf" target="[object Object]">Hall's Theorem (PDF)</a></p>
<p><a href="/assets/courseware/v1/39ca99752af2eed993936150cd0f4386/asset-v1:OCW+6.042J+2T2019+type@asset+block/HallsTheorem_2.11_Lectrans.pdf" target="[object Object]">Lecture video transcript (PDF)</a></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@0ea809a29921421b8fe054468a255c5c" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="VerticalStudentView" data-block-type="vertical" data-graded="False" data-has-score="False" data-request-token="af119002c06411ef81320efa3cc2f29f">
<h2 class="hd hd-2 unit-title">Exercise | Bottleneck</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@3be1889d56f2498a9a31c49ebf5a07dc">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@3be1889d56f2498a9a31c49ebf5a07dc" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="XBlockToXModuleShim" data-block-type="problem" data-graded="False" data-has-score="True" data-request-token="af119002c06411ef81320efa3cc2f29f">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_3be1889d56f2498a9a31c49ebf5a07dc" class="problems-wrapper" role="group"
aria-labelledby="3be1889d56f2498a9a31c49ebf5a07dc-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@3be1889d56f2498a9a31c49ebf5a07dc" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@3be1889d56f2498a9a31c49ebf5a07dc/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="3be1889d56f2498a9a31c49ebf5a07dc-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@3be1889d56f2498a9a31c49ebf5a07dc-problem-progress" tabindex="-1">
Bottleneck
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@3be1889d56f2498a9a31c49ebf5a07dc-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p> What is the definition of a bottleneck?</p>
<div class="choicegroup capa_inputtype" id="inputtype_3be1889d56f2498a9a31c49ebf5a07dc_2_1">
<fieldset aria-describedby="status_3be1889d56f2498a9a31c49ebf5a07dc_2_1">
<div class="field">
<input type="radio" name="input_3be1889d56f2498a9a31c49ebf5a07dc_2_1" id="input_3be1889d56f2498a9a31c49ebf5a07dc_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="3be1889d56f2498a9a31c49ebf5a07dc_2_1-choice_0-label" for="input_3be1889d56f2498a9a31c49ebf5a07dc_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_3be1889d56f2498a9a31c49ebf5a07dc_2_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mo stretchy="false">&#8739;<!-- &#8739; --></mo>
<mi>S</mi>
<mo>&#8739;<!-- &#8739; -->&lt;&#8739;<!-- &#8739; --></mo>
<mi>E</mi>
<mo stretchy="false">(</mo>
<mi>S</mi>
<mo stretchy="false">)</mo>
<mo stretchy="false">&#8739;<!-- &#8739; --></mo>
</math>
</label>
</div>
<div class="field">
<input type="radio" name="input_3be1889d56f2498a9a31c49ebf5a07dc_2_1" id="input_3be1889d56f2498a9a31c49ebf5a07dc_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="3be1889d56f2498a9a31c49ebf5a07dc_2_1-choice_1-label" for="input_3be1889d56f2498a9a31c49ebf5a07dc_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_3be1889d56f2498a9a31c49ebf5a07dc_2_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mo stretchy="false">&#8739;<!-- &#8739; --></mo>
<mi>S</mi>
<mo>&#8739;<!-- &#8739; -->&gt;&#8739;<!-- &#8739; --></mo>
<mi>E</mi>
<mo stretchy="false">(</mo>
<mi>S</mi>
<mo stretchy="false">)</mo>
<mo stretchy="false">&#8739;<!-- &#8739; --></mo>
</math>
</label>
</div>
<div class="field">
<input type="radio" name="input_3be1889d56f2498a9a31c49ebf5a07dc_2_1" id="input_3be1889d56f2498a9a31c49ebf5a07dc_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="3be1889d56f2498a9a31c49ebf5a07dc_2_1-choice_2-label" for="input_3be1889d56f2498a9a31c49ebf5a07dc_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_3be1889d56f2498a9a31c49ebf5a07dc_2_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mo stretchy="false">&#8739;<!-- &#8739; --></mo>
<mi>S</mi>
<mo>&#8739;<!-- &#8739; -->=&#8739;<!-- &#8739; --></mo>
<mi>E</mi>
<mo stretchy="false">(</mo>
<mi>S</mi>
<mo stretchy="false">)</mo>
<mo stretchy="false">&#8739;<!-- &#8739; --></mo>
</math>
</label>
</div>
<div class="field">
<input type="radio" name="input_3be1889d56f2498a9a31c49ebf5a07dc_2_1" id="input_3be1889d56f2498a9a31c49ebf5a07dc_2_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="3be1889d56f2498a9a31c49ebf5a07dc_2_1-choice_3-label" for="input_3be1889d56f2498a9a31c49ebf5a07dc_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_3be1889d56f2498a9a31c49ebf5a07dc_2_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mo stretchy="false">&#8739;<!-- &#8739; --></mo>
<mi>S</mi>
<mo>&#8739;<!-- &#8739; -->&#8805;&#8739;<!-- &#8739; --></mo>
<mi>E</mi>
<mo stretchy="false">(</mo>
<mi>S</mi>
<mo stretchy="false">)</mo>
<mo stretchy="false">&#8739;<!-- &#8739; --></mo>
</math>
</label>
</div>
<div class="field">
<input type="radio" name="input_3be1889d56f2498a9a31c49ebf5a07dc_2_1" id="input_3be1889d56f2498a9a31c49ebf5a07dc_2_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="3be1889d56f2498a9a31c49ebf5a07dc_2_1-choice_4-label" for="input_3be1889d56f2498a9a31c49ebf5a07dc_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_3be1889d56f2498a9a31c49ebf5a07dc_2_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mo stretchy="false">&#8739;<!-- &#8739; --></mo>
<mi>S</mi>
<mo>&#8739;<!-- &#8739; -->&#8804;&#8739;<!-- &#8739; --></mo>
<mi>E</mi>
<mo stretchy="false">(</mo>
<mi>S</mi>
<mo stretchy="false">)</mo>
<mo stretchy="false">&#8739;<!-- &#8739; --></mo>
</math>
</label>
</div>
<span id="answer_3be1889d56f2498a9a31c49ebf5a07dc_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_3be1889d56f2498a9a31c49ebf5a07dc_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Bottleneck" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_3be1889d56f2498a9a31c49ebf5a07dc" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_3be1889d56f2498a9a31c49ebf5a07dc">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="reset problem-action-btn btn-default btn-small" data-value="Reset"><span class="icon fa fa-refresh" aria-hidden="true"></span><span aria-hidden="true">Reset</span><span class="sr">Reset your answer</span></button>
</span>
<span class="problem-action-button-wrapper">
<button type="button" class="show problem-action-btn btn-default btn-small" aria-describedby="3be1889d56f2498a9a31c49ebf5a07dc-problem-title"><span class="icon fa fa-info-circle" aria-hidden="true"></span><span class="show-label">Show Answer</span></button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="3be1889d56f2498a9a31c49ebf5a07dc-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="3be1889d56f2498a9a31c49ebf5a07dc-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="3be1889d56f2498a9a31c49ebf5a07dc-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@9e46de99c39e478bbcb8b7f9d6c9837e" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="VerticalStudentView" data-block-type="vertical" data-graded="False" data-has-score="False" data-request-token="af119002c06411ef81320efa3cc2f29f">
<h2 class="hd hd-2 unit-title">Exercise | Bipartite Graphs</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@b438b297eda1453f9a6d7fa1f62cbabe">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@b438b297eda1453f9a6d7fa1f62cbabe" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="XBlockToXModuleShim" data-block-type="problem" data-graded="False" data-has-score="True" data-request-token="af119002c06411ef81320efa3cc2f29f">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_b438b297eda1453f9a6d7fa1f62cbabe" class="problems-wrapper" role="group"
aria-labelledby="b438b297eda1453f9a6d7fa1f62cbabe-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@b438b297eda1453f9a6d7fa1f62cbabe" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@b438b297eda1453f9a6d7fa1f62cbabe/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="b438b297eda1453f9a6d7fa1f62cbabe-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@b438b297eda1453f9a6d7fa1f62cbabe-problem-progress" tabindex="-1">
Bipartite Graphs
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@b438b297eda1453f9a6d7fa1f62cbabe-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p><img height="206" width="298" src="/assets/courseware/v1/b8b40ed8f55d80ee02d50bcf5df33a69/asset-v1:OCW+6.042J+2T2019+type@asset+block/6.042_Unit_II_2.11._1.jpg" alt="Bipartite Graphs Image 1"/><img height="207" width="359" src="/assets/courseware/v1/454f248e14112157665c2c6fa64cc1dd/asset-v1:OCW+6.042J+2T2019+type@asset+block/6.042_Unit_II_2.11._2.jpg" alt="Bipartite Graphs Image 2"/><img height="210" width="216" src="/assets/courseware/v1/a4857c8804bd090a0e54077cc369d4d6/asset-v1:OCW+6.042J+2T2019+type@asset+block/6.042_Unit_II_2.11._3.jpg" alt="Bipartite Graphs Image 3"/></p>
<p> Which of the graphs above are bipartite?
<br/>
<br/>
<em> Give your answer as a sequence of the labels separated by some spaces in any order such as "b a". Don't use commas or parentheses.</em></p>
<div id="inputtype_b438b297eda1453f9a6d7fa1f62cbabe_2_1" class=" capa_inputtype textline">
<div class="unanswered ">
<input type="text" name="input_b438b297eda1453f9a6d7fa1f62cbabe_2_1" id="input_b438b297eda1453f9a6d7fa1f62cbabe_2_1" aria-describedby="status_b438b297eda1453f9a6d7fa1f62cbabe_2_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_b438b297eda1453f9a6d7fa1f62cbabe_2_1"/>
<span class="status unanswered" id="status_b438b297eda1453f9a6d7fa1f62cbabe_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_b438b297eda1453f9a6d7fa1f62cbabe_2_1" class="answer"/>
</div>
</div></div>
<div class="solution-span">
<span id="solution_b438b297eda1453f9a6d7fa1f62cbabe_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Bipartite Graphs" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_b438b297eda1453f9a6d7fa1f62cbabe" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_b438b297eda1453f9a6d7fa1f62cbabe">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="reset problem-action-btn btn-default btn-small" data-value="Reset"><span class="icon fa fa-refresh" aria-hidden="true"></span><span aria-hidden="true">Reset</span><span class="sr">Reset your answer</span></button>
</span>
<span class="problem-action-button-wrapper">
<button type="button" class="show problem-action-btn btn-default btn-small" aria-describedby="b438b297eda1453f9a6d7fa1f62cbabe-problem-title"><span class="icon fa fa-info-circle" aria-hidden="true"></span><span class="show-label">Show Answer</span></button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="b438b297eda1453f9a6d7fa1f62cbabe-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="b438b297eda1453f9a6d7fa1f62cbabe-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="b438b297eda1453f9a6d7fa1f62cbabe-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@6d7c231302c140b4a182e0953f5da1ad" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="VerticalStudentView" data-block-type="vertical" data-graded="False" data-has-score="False" data-request-token="af119002c06411ef81320efa3cc2f29f">
<h2 class="hd hd-2 unit-title">Exercise | Matching</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@71485134661c4f5d8d99c6785871f759">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@71485134661c4f5d8d99c6785871f759" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="XBlockToXModuleShim" data-block-type="problem" data-graded="False" data-has-score="True" data-request-token="af119002c06411ef81320efa3cc2f29f">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_71485134661c4f5d8d99c6785871f759" class="problems-wrapper" role="group"
aria-labelledby="71485134661c4f5d8d99c6785871f759-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@71485134661c4f5d8d99c6785871f759" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@71485134661c4f5d8d99c6785871f759/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="2"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="71485134661c4f5d8d99c6785871f759-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@71485134661c4f5d8d99c6785871f759-problem-progress" tabindex="-1">
Match or No Match
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@71485134661c4f5d8d99c6785871f759-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div align="center">
<p>1. A Perfect Matching </p>
</div>
<div id="inputtype_71485134661c4f5d8d99c6785871f759_2_1" class=" capa_inputtype textline">
<div class="unanswered ">
<label class="problem-group-label" for="input_71485134661c4f5d8d99c6785871f759_2_1" id="label_71485134661c4f5d8d99c6785871f759_2_1">Find a perfect matching the bipartite simple graph <em>G</em> whose vertices and edges are given by the following sets:</label>
<input type="text" name="input_71485134661c4f5d8d99c6785871f759_2_1" id="input_71485134661c4f5d8d99c6785871f759_2_1" aria-describedby="status_71485134661c4f5d8d99c6785871f759_2_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_71485134661c4f5d8d99c6785871f759_2_1"/>
<span class="status unanswered" id="status_71485134661c4f5d8d99c6785871f759_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_71485134661c4f5d8d99c6785871f759_2_1" class="answer"/>
</div>
</div><div align="center">
V := {a,b,c,d} &#8746; {1,2,3,4}
<br/>
E := {{a,1}, {a,3}, {b,2}, {c,3}, {c,4}, {d,1}, {d,2}}
</div>
<br/>
<strong> <p> Input the edges of the matching in increasing alphabetic order, i.e. for each edge, you should write the letter in the pair first. Also list the edges separated by spaces. For example, if you want to answer {d, 1} and {c, 3}, type (c 3) (d 1).</p></strong>
</div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div align="center">
<p>2. No Perfect Matching </p>
</div>
<div id="inputtype_71485134661c4f5d8d99c6785871f759_3_1" class=" capa_inputtype textline">
<div class="unanswered ">
<label class="problem-group-label" for="input_71485134661c4f5d8d99c6785871f759_3_1" id="label_71485134661c4f5d8d99c6785871f759_3_1">The bipartite simple graph <em>G</em> whose vertices and edges are given by the folowing sets:</label>
<input type="text" name="input_71485134661c4f5d8d99c6785871f759_3_1" id="input_71485134661c4f5d8d99c6785871f759_3_1" aria-describedby="status_71485134661c4f5d8d99c6785871f759_3_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_71485134661c4f5d8d99c6785871f759_3_1"/>
<span class="status unanswered" id="status_71485134661c4f5d8d99c6785871f759_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_71485134661c4f5d8d99c6785871f759_3_1" class="answer"/>
</div>
</div><div align="center">
V := {a,b,c,d} &#8746; {1,2,3,4}
<br/>
E := {{a,3}, {a,4}, {b,1}, {b,2}, {c,1}, {c,2}, {d,1},{d,2}}
</div>
<br/>
<div align="center">
<p> does not have perfect matching.</p>
<strong> <p> Give your answer as a sequence of numbers separated by some spaces
(e.g., "6 9"). Don't use commas or parentheses. </p></strong>
</div>
<p> Which of the following properties of <em>G</em> make a perfect matching impossible? </p>
<ol>
<li> The set {1,3,4} has only 2 neighbors. </li>
<li> The vertices a,b,c,d, on the "left" side, all have degree 2, but none of the vertices 1,2,3,4, on the "right" side, has degree 2.
</li>
<li> The set {b,c,d} has only 2 neighbors.</li>
<li> <em> G </em> has 8 edges. </li>
<li> The set {3,4} has only 1 neighbor. </li>
<li> Vertex 1 has degree 3, but each of its neighbors only has degree 2.
</li>
<li> The set {a,b} has 4 neighbors.
</li>
</ol>
</div>
<div class="solution-span">
<span id="solution_71485134661c4f5d8d99c6785871f759_solution_1"/>
</div><div class="solution-span">
<span id="solution_71485134661c4f5d8d99c6785871f759_solution_2"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Match or No Match" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_71485134661c4f5d8d99c6785871f759" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_71485134661c4f5d8d99c6785871f759">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="reset problem-action-btn btn-default btn-small" data-value="Reset"><span class="icon fa fa-refresh" aria-hidden="true"></span><span aria-hidden="true">Reset</span><span class="sr">Reset your answer</span></button>
</span>
<span class="problem-action-button-wrapper">
<button type="button" class="show problem-action-btn btn-default btn-small" aria-describedby="71485134661c4f5d8d99c6785871f759-problem-title"><span class="icon fa fa-info-circle" aria-hidden="true"></span><span class="show-label">Show Answer</span></button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="71485134661c4f5d8d99c6785871f759-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="71485134661c4f5d8d99c6785871f759-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="71485134661c4f5d8d99c6785871f759-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@a906cc3c0e6e4a80af50101384aa5dbc" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="VerticalStudentView" data-block-type="vertical" data-graded="False" data-has-score="False" data-request-token="af119002c06411ef81320efa3cc2f29f">
<h2 class="hd hd-2 unit-title">Exercise | Stable Matching Invariants</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@6df6ed9ba4034e63a587adc149ff6645">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-runtime-class="LmsRuntime" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@6df6ed9ba4034e63a587adc149ff6645" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-init="XBlockToXModuleShim" data-block-type="problem" data-graded="False" data-has-score="True" data-request-token="af119002c06411ef81320efa3cc2f29f">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_6df6ed9ba4034e63a587adc149ff6645" class="problems-wrapper" role="group"
aria-labelledby="6df6ed9ba4034e63a587adc149ff6645-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@6df6ed9ba4034e63a587adc149ff6645" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@6df6ed9ba4034e63a587adc149ff6645/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="6df6ed9ba4034e63a587adc149ff6645-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@6df6ed9ba4034e63a587adc149ff6645-problem-progress" tabindex="-1">
Stable Matching Invariants
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@6df6ed9ba4034e63a587adc149ff6645-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p> We are interested in invariants of the Mating Ritual described in the Notes for finding stable marriages when there are an equal number of boys and girls. Let Angelina and Jen be two of the girls, and Keith and Tom be two of the boys. </p>
<p> Which of the following predicates are <strong>preserved invariants</strong> of the Mating Ritual no matter what the preferences are among the boys and girls? (Remember that a predicate that is always false is a preserved invariant &#65293;check the definition to see why. Also, a preserved invariant doesn't need to be true initially, it just needs to <em>stay</em> true once it <em>starts</em> being true.)</p>
<strong><p> Express your answer as a sequence of digits in increasing order separated by a space between each number, for example, 1 4 5.</p> </strong>
<div id="inputtype_6df6ed9ba4034e63a587adc149ff6645_2_1" class=" capa_inputtype textline">
<div class="unanswered ">
<input type="text" name="input_6df6ed9ba4034e63a587adc149ff6645_2_1" id="input_6df6ed9ba4034e63a587adc149ff6645_2_1" aria-describedby="status_6df6ed9ba4034e63a587adc149ff6645_2_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_6df6ed9ba4034e63a587adc149ff6645_2_1"/>
<span class="status unanswered" id="status_6df6ed9ba4034e63a587adc149ff6645_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_6df6ed9ba4034e63a587adc149ff6645_2_1" class="answer"/>
</div>
</div><br/>
<ol>
<li> Angelina is crossed off Tom's list, and she has a suitor that she prefers to Tom. </li>
<li> Tom is serenading Jen.</li>
<li> Tom is not serenading Jen.</li>
<li> Tom's list of girls to serenade is empty.</li>
<li> All the boys have the same number of girls left uncrossed in their lists.</li>
<li> Jen is crossed off Keith's list, and Keith prefers Jen to anyone he is serenading.</li>
<li>Jen is the only girl on Keith's list.</li>
<li> Jen is crossed off Keith's list, and there is no set of stable marriages &#65293;not just the set produced by the Mating Ritual &#65293;in which Jen is married to Keith.</li>
</ol>
<div class="solution-span">
<span id="solution_6df6ed9ba4034e63a587adc149ff6645_solution_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Stable Matching Invariants" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_6df6ed9ba4034e63a587adc149ff6645" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_6df6ed9ba4034e63a587adc149ff6645">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
<span class="problem-action-button-wrapper">
<button type="button" class="reset problem-action-btn btn-default btn-small" data-value="Reset"><span class="icon fa fa-refresh" aria-hidden="true"></span><span aria-hidden="true">Reset</span><span class="sr">Reset your answer</span></button>
</span>
<span class="problem-action-button-wrapper">
<button type="button" class="show problem-action-btn btn-default btn-small" aria-describedby="6df6ed9ba4034e63a587adc149ff6645-problem-title"><span class="icon fa fa-info-circle" aria-hidden="true"></span><span class="show-label">Show Answer</span></button>
</span>
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="6df6ed9ba4034e63a587adc149ff6645-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="6df6ed9ba4034e63a587adc149ff6645-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="6df6ed9ba4034e63a587adc149ff6645-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="False">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>