<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@7fd59840fb364d7eab2031f230f370a6" data-request-token="5114156ce12311ef99840affe527bd1b">
<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@f936360338864ad69e5960e717b262a4">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@f936360338864ad69e5960e717b262a4" data-request-token="5114156ce12311ef99840affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>Read <a href="/assets/courseware/v1/ec6730f747b31e019f98b20842f6f064/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_Session17.pdf" target="[object Object]">Chapter 9.5 (PDF)</a> of <em>Mathematics for Computer Science</em> for 2.6 Directed Acyclic Graphs.</p>
<p>View the <a href="/assets/courseware/v1/1f5977990f3867d4602d5bec13c56abe/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_cp17.pdf" target="[object Object]">Section 2.6 In-Class Questions (PDF)</a></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@a5fcd0ef181f4e0f81d378ab62105b8a" data-request-token="5114156ce12311ef99840affe527bd1b">
<h2 class="hd hd-2 unit-title">Lecture Video | DAGs</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@video+block@616191e5060443ff983aadc037a2ef4b">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@video+block@616191e5060443ff983aadc037a2ef4b" data-request-token="5114156ce12311ef99840affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">DAGs</h3>
<div
id="video_616191e5060443ff983aadc037a2ef4b"
class="video closed"
data-metadata='{"ytApiUrl": "https://www.youtube.com/iframe_api", "prioritizeHls": false, "streams": "1.00:Sdw8_0RDZuw", "ytTestTimeout": 1500, "end": 0.0, "autoplay": false, "captionDataDir": null, "savedVideoPosition": 0.0, "publishCompletionUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@616191e5060443ff983aadc037a2ef4b/handler/publish_completion", "showCaptions": "true", "completionEnabled": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@616191e5060443ff983aadc037a2ef4b/handler/transcript/available_translations", "completionPercentage": 0.95, "sources": ["https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_dags_video_ipod.mp4"], "transcriptTranslationUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@616191e5060443ff983aadc037a2ef4b/handler/transcript/translation/__lang__", "autoAdvance": false, "start": 0.0, "autohideHtml5": false, "lmsRootURL": "https://openlearninglibrary.mit.edu", "saveStateUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@616191e5060443ff983aadc037a2ef4b/handler/xmodule_handler/save_user_state", "duration": 0.0, "transcriptLanguages": {"en": "English"}, "saveStateEnabled": false, "ytMetadataEndpoint": "", "transcriptLanguage": "en", "speed": null, "generalSpeed": 1.0, "poster": null, "recordedYoutubeIsAvailable": true}'
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="616191e5060443ff983aadc037a2ef4b"></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_616191e5060443ff983aadc037a2ef4b">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_616191e5060443ff983aadc037a2ef4b">
<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_dags_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@616191e5060443ff983aadc037a2ef4b/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@616191e5060443ff983aadc037a2ef4b/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@8e2c5a534e1948d28028751fdf64a405">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@8e2c5a534e1948d28028751fdf64a405" data-request-token="5114156ce12311ef99840affe527bd1b">
<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/37b21232008bdf661cc7e0b8f5455c1a/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_DAGs.pdf" target="[object Object]">DAGs (PDF)</a></p>
<p><a href="/assets/courseware/v1/cbb0d9f1f2e936e54a1ce726364f78ed/asset-v1:OCW+6.042J+2T2019+type@asset+block/DAGS_2.6_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-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@a747089dc6bf4f3e8c53fec7ba598339" data-request-token="5114156ce12311ef99840affe527bd1b">
<h2 class="hd hd-2 unit-title">Exercise | DAGs</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@d7b6cab6554e489bbbc66767c9ef78a8">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-block-type="problem" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="True" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@d7b6cab6554e489bbbc66767c9ef78a8" data-request-token="5114156ce12311ef99840affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_d7b6cab6554e489bbbc66767c9ef78a8" class="problems-wrapper" role="group"
aria-labelledby="d7b6cab6554e489bbbc66767c9ef78a8-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@d7b6cab6554e489bbbc66767c9ef78a8" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@d7b6cab6554e489bbbc66767c9ef78a8/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="d7b6cab6554e489bbbc66767c9ef78a8-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@d7b6cab6554e489bbbc66767c9ef78a8-problem-progress" tabindex="-1">
DAGs Question 1
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@d7b6cab6554e489bbbc66767c9ef78a8-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_d7b6cab6554e489bbbc66767c9ef78a8_2_1">
<fieldset aria-describedby="status_d7b6cab6554e489bbbc66767c9ef78a8_2_1">
<legend id="d7b6cab6554e489bbbc66767c9ef78a8_2_1-legend" class="response-fieldset-legend field-group-hd">1. Which of the following graph features may <em> NOT </em> appear in a diagraph:</legend>
<div class="field">
<input type="checkbox" name="input_d7b6cab6554e489bbbc66767c9ef78a8_2_1[]" id="input_d7b6cab6554e489bbbc66767c9ef78a8_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="d7b6cab6554e489bbbc66767c9ef78a8_2_1-choice_0-label" for="input_d7b6cab6554e489bbbc66767c9ef78a8_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_d7b6cab6554e489bbbc66767c9ef78a8_2_1"> self loops
</label>
</div>
<div class="field">
<input type="checkbox" name="input_d7b6cab6554e489bbbc66767c9ef78a8_2_1[]" id="input_d7b6cab6554e489bbbc66767c9ef78a8_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="d7b6cab6554e489bbbc66767c9ef78a8_2_1-choice_1-label" for="input_d7b6cab6554e489bbbc66767c9ef78a8_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_d7b6cab6554e489bbbc66767c9ef78a8_2_1"> isolated nodes (with no edges in or out)
</label>
</div>
<div class="field">
<input type="checkbox" name="input_d7b6cab6554e489bbbc66767c9ef78a8_2_1[]" id="input_d7b6cab6554e489bbbc66767c9ef78a8_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="d7b6cab6554e489bbbc66767c9ef78a8_2_1-choice_2-label" for="input_d7b6cab6554e489bbbc66767c9ef78a8_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_d7b6cab6554e489bbbc66767c9ef78a8_2_1"> two edges in opposite directions between a pair of nodes
</label>
</div>
<div class="field">
<input type="checkbox" name="input_d7b6cab6554e489bbbc66767c9ef78a8_2_1[]" id="input_d7b6cab6554e489bbbc66767c9ef78a8_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="d7b6cab6554e489bbbc66767c9ef78a8_2_1-choice_3-label" for="input_d7b6cab6554e489bbbc66767c9ef78a8_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_d7b6cab6554e489bbbc66767c9ef78a8_2_1"> two edges in the same direction between a pair of nodes
</label>
</div>
<div class="field">
<input type="checkbox" name="input_d7b6cab6554e489bbbc66767c9ef78a8_2_1[]" id="input_d7b6cab6554e489bbbc66767c9ef78a8_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="d7b6cab6554e489bbbc66767c9ef78a8_2_1-choice_4-label" for="input_d7b6cab6554e489bbbc66767c9ef78a8_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_d7b6cab6554e489bbbc66767c9ef78a8_2_1"> having no edges at all
</label>
</div>
<div class="field">
<input type="checkbox" name="input_d7b6cab6554e489bbbc66767c9ef78a8_2_1[]" id="input_d7b6cab6554e489bbbc66767c9ef78a8_2_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="d7b6cab6554e489bbbc66767c9ef78a8_2_1-choice_5-label" for="input_d7b6cab6554e489bbbc66767c9ef78a8_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_d7b6cab6554e489bbbc66767c9ef78a8_2_1"> having no nodes at all
</label>
</div>
<span id="answer_d7b6cab6554e489bbbc66767c9ef78a8_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_d7b6cab6554e489bbbc66767c9ef78a8_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="DAGs Question 1" />
<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_d7b6cab6554e489bbbc66767c9ef78a8" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_d7b6cab6554e489bbbc66767c9ef78a8">
<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="d7b6cab6554e489bbbc66767c9ef78a8-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="d7b6cab6554e489bbbc66767c9ef78a8-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="d7b6cab6554e489bbbc66767c9ef78a8-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="d7b6cab6554e489bbbc66767c9ef78a8-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 class="vert vert-1" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@fb38b39fd3cb40599e3e3f089ac12b6d">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-block-type="problem" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="True" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@fb38b39fd3cb40599e3e3f089ac12b6d" data-request-token="5114156ce12311ef99840affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_fb38b39fd3cb40599e3e3f089ac12b6d" class="problems-wrapper" role="group"
aria-labelledby="fb38b39fd3cb40599e3e3f089ac12b6d-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@fb38b39fd3cb40599e3e3f089ac12b6d" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@fb38b39fd3cb40599e3e3f089ac12b6d/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="fb38b39fd3cb40599e3e3f089ac12b6d-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@fb38b39fd3cb40599e3e3f089ac12b6d-problem-progress" tabindex="-1">
Question 2
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@fb38b39fd3cb40599e3e3f089ac12b6d-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_fb38b39fd3cb40599e3e3f089ac12b6d_2_1" id="label_fb38b39fd3cb40599e3e3f089ac12b6d_2_1">2. Let <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>V</mi> </math> be a DAG and <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>U</mi> </math> be the DAG with only the covering edges of <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>V</mi> </math>. Then:
<br/>
<br/>
1. compared to the length of the <em>shortest</em> path between two nodes in <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>V</mi>
</math>, the length of the <em>shortest path</em> in <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>U</mi>
</math> between these nodes is:</label>
<select name="input_fb38b39fd3cb40599e3e3f089ac12b6d_2_1" id="input_fb38b39fd3cb40599e3e3f089ac12b6d_2_1" aria-describedby="status_fb38b39fd3cb40599e3e3f089ac12b6d_2_1">
<option value="option_fb38b39fd3cb40599e3e3f089ac12b6d_2_1_dummy_default">Select an option</option>
<option value="the same"> the same</option>
<option value="not longer"> not longer</option>
<option value="not shorter"> not shorter</option>
<option value="may be shorter or longer"> may be shorter or longer</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_fb38b39fd3cb40599e3e3f089ac12b6d_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_fb38b39fd3cb40599e3e3f089ac12b6d_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_fb38b39fd3cb40599e3e3f089ac12b6d_3_1" id="label_fb38b39fd3cb40599e3e3f089ac12b6d_3_1">2. compared to the length of the <em>longest</em> path between two nodes in <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>V</mi>
</math>, the length of the <em>longest path</em> in <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>U</mi>
</math> between these nodes is:</label>
<select name="input_fb38b39fd3cb40599e3e3f089ac12b6d_3_1" id="input_fb38b39fd3cb40599e3e3f089ac12b6d_3_1" aria-describedby="status_fb38b39fd3cb40599e3e3f089ac12b6d_3_1">
<option value="option_fb38b39fd3cb40599e3e3f089ac12b6d_3_1_dummy_default">Select an option</option>
<option value="the same"> the same</option>
<option value="not longer"> not longer</option>
<option value="not shorter"> not shorter</option>
<option value="may be shorter or longer"> may be shorter or longer</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_fb38b39fd3cb40599e3e3f089ac12b6d_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_fb38b39fd3cb40599e3e3f089ac12b6d_3_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Question 2" />
<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_fb38b39fd3cb40599e3e3f089ac12b6d" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_fb38b39fd3cb40599e3e3f089ac12b6d">
<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="fb38b39fd3cb40599e3e3f089ac12b6d-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="fb38b39fd3cb40599e3e3f089ac12b6d-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="fb38b39fd3cb40599e3e3f089ac12b6d-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="fb38b39fd3cb40599e3e3f089ac12b6d-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-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@3f9e1863b83e428fa786b5aaa647e6ab" data-request-token="5114156ce12311ef99840affe527bd1b">
<h2 class="hd hd-2 unit-title">Lecture Video | Scheduling</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@video+block@6d7c62533b904cfd90537beac91d83ee">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@video+block@6d7c62533b904cfd90537beac91d83ee" data-request-token="5114156ce12311ef99840affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Scheduling</h3>
<div
id="video_6d7c62533b904cfd90537beac91d83ee"
class="video closed"
data-metadata='{"ytApiUrl": "https://www.youtube.com/iframe_api", "prioritizeHls": false, "streams": "1.00:1TpzSCMLg08", "ytTestTimeout": 1500, "end": 0.0, "autoplay": false, "captionDataDir": null, "savedVideoPosition": 0.0, "publishCompletionUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@6d7c62533b904cfd90537beac91d83ee/handler/publish_completion", "showCaptions": "true", "completionEnabled": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@6d7c62533b904cfd90537beac91d83ee/handler/transcript/available_translations", "completionPercentage": 0.95, "sources": ["https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_scheduling_ipod.mp4"], "transcriptTranslationUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@6d7c62533b904cfd90537beac91d83ee/handler/transcript/translation/__lang__", "autoAdvance": false, "start": 0.0, "autohideHtml5": false, "lmsRootURL": "https://openlearninglibrary.mit.edu", "saveStateUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@6d7c62533b904cfd90537beac91d83ee/handler/xmodule_handler/save_user_state", "duration": 0.0, "transcriptLanguages": {"en": "English"}, "saveStateEnabled": false, "ytMetadataEndpoint": "", "transcriptLanguage": "en", "speed": null, "generalSpeed": 1.0, "poster": null, "recordedYoutubeIsAvailable": true}'
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="6d7c62533b904cfd90537beac91d83ee"></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_6d7c62533b904cfd90537beac91d83ee">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_6d7c62533b904cfd90537beac91d83ee">
<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_scheduling_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@6d7c62533b904cfd90537beac91d83ee/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@6d7c62533b904cfd90537beac91d83ee/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@a020fd6b9d6f4804ae642142f3f7193e">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@a020fd6b9d6f4804ae642142f3f7193e" data-request-token="5114156ce12311ef99840affe527bd1b">
<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/2efbd5ad05fcdbccf1dbdb789cbb19af/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_Scheduling.pdf" target="[object Object]">Scheduling (PDF)</a></p>
<p><a href="/assets/courseware/v1/61a11a5e1b12b9c957cd3f1be0dcf9c3/asset-v1:OCW+6.042J+2T2019+type@asset+block/Scheduling_2.6_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-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@1b595341cdc9444fbf73ac4160e37bd3" data-request-token="5114156ce12311ef99840affe527bd1b">
<h2 class="hd hd-2 unit-title">Exercise | Scheduling Prerequisites</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@html+block@7a38db4e0a264fb6b2ae478e8bb6fc97">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@7a38db4e0a264fb6b2ae478e8bb6fc97" data-request-token="5114156ce12311ef99840affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p></p>
<p>The prerequisites of some MIT subjects are given in the following table:</p>
<p></p>
<table style="width: 400px;">
<thead>
<tr><th>DIRECT PREREQUISITES</th><th>SUBJECT</th></tr>
</thead>
<tbody>
<tr>
<td>18.01</td>
<td>6.042</td>
</tr>
<tr>
<td>18.01</td>
<td>18.02</td>
</tr>
<tr>
<td>18.01</td>
<td>18.03</td>
</tr>
<tr>
<td>8.01</td>
<td>8.02</td>
</tr>
<tr>
<td>8.01</td>
<td>6.01</td>
</tr>
<tr>
<td>6.042</td>
<td>6.046</td>
</tr>
<tr>
<td>18.02, 18.03, 8.02, 6.01</td>
<td>6.02</td>
</tr>
<tr>
<td>6.01, 6.042</td>
<td>6.006</td>
</tr>
<tr>
<td>6.01</td>
<td>6.034</td>
</tr>
<tr>
<td>6.02</td>
<td>6.004</td>
</tr>
</tbody>
</table>
<p></p>
<p></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@a30e4a9c0eaf456c9a010c4613bfe746">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-block-type="problem" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="True" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@a30e4a9c0eaf456c9a010c4613bfe746" data-request-token="5114156ce12311ef99840affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_a30e4a9c0eaf456c9a010c4613bfe746" class="problems-wrapper" role="group"
aria-labelledby="a30e4a9c0eaf456c9a010c4613bfe746-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@a30e4a9c0eaf456c9a010c4613bfe746" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@a30e4a9c0eaf456c9a010c4613bfe746/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="5"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="a30e4a9c0eaf456c9a010c4613bfe746-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@a30e4a9c0eaf456c9a010c4613bfe746-problem-progress" tabindex="-1">
Questions
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@a30e4a9c0eaf456c9a010c4613bfe746-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p>In the following sets of subjects, specify whether the set is a chain, anti-chain, or neither:
(Hint, draw a DAG for the subjects first!)</p>
<br/>
<div class="inputtype option-input ">
<label class="problem-group-label" for="input_a30e4a9c0eaf456c9a010c4613bfe746_2_1" id="label_a30e4a9c0eaf456c9a010c4613bfe746_2_1">1. 6.042, 6.046, 6.01</label>
<select name="input_a30e4a9c0eaf456c9a010c4613bfe746_2_1" id="input_a30e4a9c0eaf456c9a010c4613bfe746_2_1" aria-describedby="status_a30e4a9c0eaf456c9a010c4613bfe746_2_1">
<option value="option_a30e4a9c0eaf456c9a010c4613bfe746_2_1_dummy_default">Select an option</option>
<option value="chain"> chain</option>
<option value="anti-chain"> anti-chain</option>
<option value="neither"> neither</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_a30e4a9c0eaf456c9a010c4613bfe746_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_a30e4a9c0eaf456c9a010c4613bfe746_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_a30e4a9c0eaf456c9a010c4613bfe746_3_1" id="label_a30e4a9c0eaf456c9a010c4613bfe746_3_1">2. 18.01, 6.02, 6.004</label>
<select name="input_a30e4a9c0eaf456c9a010c4613bfe746_3_1" id="input_a30e4a9c0eaf456c9a010c4613bfe746_3_1" aria-describedby="status_a30e4a9c0eaf456c9a010c4613bfe746_3_1">
<option value="option_a30e4a9c0eaf456c9a010c4613bfe746_3_1_dummy_default">Select an option</option>
<option value="chain"> chain</option>
<option value="anti-chain"> anti-chain</option>
<option value="neither"> neither</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_a30e4a9c0eaf456c9a010c4613bfe746_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_a30e4a9c0eaf456c9a010c4613bfe746_3_1"/>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><div class="inputtype option-input ">
<label class="problem-group-label" for="input_a30e4a9c0eaf456c9a010c4613bfe746_4_1" id="label_a30e4a9c0eaf456c9a010c4613bfe746_4_1">3. 6.042, 6.02, 6.034</label>
<select name="input_a30e4a9c0eaf456c9a010c4613bfe746_4_1" id="input_a30e4a9c0eaf456c9a010c4613bfe746_4_1" aria-describedby="status_a30e4a9c0eaf456c9a010c4613bfe746_4_1">
<option value="option_a30e4a9c0eaf456c9a010c4613bfe746_4_1_dummy_default">Select an option</option>
<option value="chain"> chain</option>
<option value="anti-chain"> anti-chain</option>
<option value="neither"> neither</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_a30e4a9c0eaf456c9a010c4613bfe746_4_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_a30e4a9c0eaf456c9a010c4613bfe746_4_1"/>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 4" role="group"><div id="inputtype_a30e4a9c0eaf456c9a010c4613bfe746_5_1" class=" capa_inputtype textline">
<div class="unanswered ">
<label class="problem-group-label" for="input_a30e4a9c0eaf456c9a010c4613bfe746_5_1" id="label_a30e4a9c0eaf456c9a010c4613bfe746_5_1">4. What is the length of the longest anti-chain?</label>
<input type="text" name="input_a30e4a9c0eaf456c9a010c4613bfe746_5_1" id="input_a30e4a9c0eaf456c9a010c4613bfe746_5_1" aria-describedby="status_a30e4a9c0eaf456c9a010c4613bfe746_5_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_a30e4a9c0eaf456c9a010c4613bfe746_5_1"/>
<span class="status unanswered" id="status_a30e4a9c0eaf456c9a010c4613bfe746_5_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_a30e4a9c0eaf456c9a010c4613bfe746_5_1" class="answer"/>
</div>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 5" role="group"><div id="inputtype_a30e4a9c0eaf456c9a010c4613bfe746_6_1" class=" capa_inputtype textline">
<div class="unanswered ">
<label class="problem-group-label" for="input_a30e4a9c0eaf456c9a010c4613bfe746_6_1" id="label_a30e4a9c0eaf456c9a010c4613bfe746_6_1">5. How many terms do you need to graduate if you take classes following the schedule given by a topological sort of the DAG?</label>
<input type="text" name="input_a30e4a9c0eaf456c9a010c4613bfe746_6_1" id="input_a30e4a9c0eaf456c9a010c4613bfe746_6_1" aria-describedby="status_a30e4a9c0eaf456c9a010c4613bfe746_6_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_a30e4a9c0eaf456c9a010c4613bfe746_6_1"/>
<span class="status unanswered" id="status_a30e4a9c0eaf456c9a010c4613bfe746_6_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_a30e4a9c0eaf456c9a010c4613bfe746_6_1" class="answer"/>
</div>
</div></div>
<div class="solution-span">
<span id="solution_a30e4a9c0eaf456c9a010c4613bfe746_solution_1"/>
</div><div class="solution-span">
<span id="solution_a30e4a9c0eaf456c9a010c4613bfe746_solution_2"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Questions " />
<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_a30e4a9c0eaf456c9a010c4613bfe746" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_a30e4a9c0eaf456c9a010c4613bfe746">
<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="a30e4a9c0eaf456c9a010c4613bfe746-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="a30e4a9c0eaf456c9a010c4613bfe746-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="a30e4a9c0eaf456c9a010c4613bfe746-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="a30e4a9c0eaf456c9a010c4613bfe746-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-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@6fd67438fbd04088805d3a7b3760f823" data-request-token="5114156ce12311ef99840affe527bd1b">
<h2 class="hd hd-2 unit-title">Lecture Video | Time vs. Processors</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@video+block@7485dec9a3ea433b918ec84ec835f381">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@video+block@7485dec9a3ea433b918ec84ec835f381" data-request-token="5114156ce12311ef99840affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Time versus Processors</h3>
<div
id="video_7485dec9a3ea433b918ec84ec835f381"
class="video closed"
data-metadata='{"ytApiUrl": "https://www.youtube.com/iframe_api", "prioritizeHls": false, "streams": "1.00:cUYTlKA8jaw", "ytTestTimeout": 1500, "end": 0.0, "autoplay": false, "captionDataDir": null, "savedVideoPosition": 0.0, "publishCompletionUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@7485dec9a3ea433b918ec84ec835f381/handler/publish_completion", "showCaptions": "true", "completionEnabled": false, "transcriptAvailableTranslationsUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@7485dec9a3ea433b918ec84ec835f381/handler/transcript/available_translations", "completionPercentage": 0.95, "sources": ["https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_paralleltime_ipod.mp4"], "transcriptTranslationUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@7485dec9a3ea433b918ec84ec835f381/handler/transcript/translation/__lang__", "autoAdvance": false, "start": 0.0, "autohideHtml5": false, "lmsRootURL": "https://openlearninglibrary.mit.edu", "saveStateUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@7485dec9a3ea433b918ec84ec835f381/handler/xmodule_handler/save_user_state", "duration": 0.0, "transcriptLanguages": {"en": "English"}, "saveStateEnabled": false, "ytMetadataEndpoint": "", "transcriptLanguage": "en", "speed": null, "generalSpeed": 1.0, "poster": null, "recordedYoutubeIsAvailable": true}'
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="7485dec9a3ea433b918ec84ec835f381"></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_7485dec9a3ea433b918ec84ec835f381">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_7485dec9a3ea433b918ec84ec835f381">
<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_paralleltime_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@7485dec9a3ea433b918ec84ec835f381/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@7485dec9a3ea433b918ec84ec835f381/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@92ceefa045cf4c2a9843132b5b7c498d">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@92ceefa045cf4c2a9843132b5b7c498d" data-request-token="5114156ce12311ef99840affe527bd1b">
<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/46e7ccf54c73df365deda76a6f5fcbb6/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_TimeProcsors.pdf" target="[object Object]">Time vs Processors (PDF)</a></p>
<p><a href="/assets/courseware/v1/e020a92e21b06d4d3f4f2bccb3dce561/asset-v1:OCW+6.042J+2T2019+type@asset+block/TimevsProcess_2.6_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-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@93a6a9720c6c4699a9801aaf7bd96ddb" data-request-token="5114156ce12311ef99840affe527bd1b">
<h2 class="hd hd-2 unit-title">Exercise | Processor Time Bounds</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@9e74a209a25c483d8508d19d3377d994">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-block-type="problem" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="True" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@9e74a209a25c483d8508d19d3377d994" data-request-token="5114156ce12311ef99840affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<p>Could not format HTML for problem. Contact course staff in the discussion forum for assistance.</p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-init="VerticalStudentView" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@6b81a1bd6b3e41899a10b1e03e307f55" data-request-token="5114156ce12311ef99840affe527bd1b">
<h2 class="hd hd-2 unit-title">Exercise | The Divisibility DAG</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@c5181851a67d48ffbbc041aac49543ea">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-block-type="problem" data-init="XBlockToXModuleShim" data-runtime-version="1" data-course-id="course-v1:OCW+6.042J+2T2019" data-graded="False" data-runtime-class="LmsRuntime" data-has-score="True" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@c5181851a67d48ffbbc041aac49543ea" data-request-token="5114156ce12311ef99840affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_c5181851a67d48ffbbc041aac49543ea" class="problems-wrapper" role="group"
aria-labelledby="c5181851a67d48ffbbc041aac49543ea-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@c5181851a67d48ffbbc041aac49543ea" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@c5181851a67d48ffbbc041aac49543ea/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="c5181851a67d48ffbbc041aac49543ea-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@c5181851a67d48ffbbc041aac49543ea-problem-progress" tabindex="-1">
The Divisibility DAG
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@c5181851a67d48ffbbc041aac49543ea-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p/>
<div align="center">
<p><img height="503" width="453" src="/assets/courseware/v1/65c9d4b48bbd60286c3845ec05023795/asset-v1:OCW+6.042J+2T2019+type@asset+block/6.042_Unit_II_2.6.jpg" alt="The Divisibility DAG"/></p>
</div>
<p/>
<div id="inputtype_c5181851a67d48ffbbc041aac49543ea_2_1" class=" capa_inputtype textline">
<div class="unanswered ">
<label class="problem-group-label" for="input_c5181851a67d48ffbbc041aac49543ea_2_1" id="label_c5181851a67d48ffbbc041aac49543ea_2_1">In the above DAG for the divisibility relation on <math xmlns="http://www.w3.org/1998/Math/MathML">
<mo fence="false" stretchy="false">{</mo>
<mn>1</mn>
<mo>,</mo>
<mo>&#8230;<!-- &#8230; --></mo>
<mo>,</mo>
<mn>12</mn>
<mo fence="false" stretchy="false">}</mo>
</math> , there is an upward path from <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>a</mi>
</math> to <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>b</mi>
</math> iff <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>a</mi>
</math> divides <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>b</mi>
</math>. If <math xmlns="http://www.w3.org/1998/Math/MathML">
<mn>24</mn>
</math> was added as a vertex, what is the minimum number of edges that must be added to the DAG to represent divisibility on <math xmlns="http://www.w3.org/1998/Math/MathML">
<mo fence="false" stretchy="false">{</mo>
<mn>1</mn>
<mo>,</mo>
<mo>&#8230;<!-- &#8230; --></mo>
<mo>,</mo>
<mn>12</mn>
<mo>,</mo>
<mn>24</mn>
<mo fence="false" stretchy="false">}</mo>
</math> ?</label>
<input type="text" name="input_c5181851a67d48ffbbc041aac49543ea_2_1" id="input_c5181851a67d48ffbbc041aac49543ea_2_1" aria-describedby="status_c5181851a67d48ffbbc041aac49543ea_2_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_c5181851a67d48ffbbc041aac49543ea_2_1"/>
<span class="status unanswered" id="status_c5181851a67d48ffbbc041aac49543ea_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_c5181851a67d48ffbbc041aac49543ea_2_1" class="answer"/>
</div>
</div></div>
<div class="solution-span">
<span id="solution_c5181851a67d48ffbbc041aac49543ea_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="The Divisibility DAG" />
<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_c5181851a67d48ffbbc041aac49543ea" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_c5181851a67d48ffbbc041aac49543ea">
<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="c5181851a67d48ffbbc041aac49543ea-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="c5181851a67d48ffbbc041aac49543ea-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="c5181851a67d48ffbbc041aac49543ea-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="c5181851a67d48ffbbc041aac49543ea-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>