<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@bc15e50962e64e91be50c6094ca51ef1" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<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@1a5a2668241448a9922d754e3141b6eb">
<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@1a5a2668241448a9922d754e3141b6eb" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>Read <a href="/assets/courseware/v1/e975c2cd707e80a2149dadb69f7ddfd8/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_Session21.pdf" target="[object Object]">Chapter 11. 9–11.10 (PDF)</a> of <em>Mathematics for Computer Science</em> for 2.10 Trees. </p>
<p>View the <a href="/assets/courseware/v1/88c4180bafc5bd1ededd3973d018f6de/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_cp21.pdf" target="[object Object]">Section 2.10 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@ca6acb0ffbf04358b5d721b79a9c8751" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<h2 class="hd hd-2 unit-title">Lecture Video | Trees</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@video+block@e367a6afec804a20a0d8b59d9a13b108">
<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@e367a6afec804a20a0d8b59d9a13b108" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Trees</h3>
<div
id="video_e367a6afec804a20a0d8b59d9a13b108"
class="video closed"
data-metadata='{"ytApiUrl": "https://www.youtube.com/iframe_api", "prioritizeHls": false, "streams": "1.00:ZEsk64C0fJg", "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@e367a6afec804a20a0d8b59d9a13b108/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@e367a6afec804a20a0d8b59d9a13b108/handler/transcript/available_translations", "completionPercentage": 0.95, "sources": ["https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_treedefs_video_ipod.mp4"], "transcriptTranslationUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@e367a6afec804a20a0d8b59d9a13b108/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@e367a6afec804a20a0d8b59d9a13b108/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="e367a6afec804a20a0d8b59d9a13b108"></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_e367a6afec804a20a0d8b59d9a13b108">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_e367a6afec804a20a0d8b59d9a13b108">
<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_treedefs_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@e367a6afec804a20a0d8b59d9a13b108/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@e367a6afec804a20a0d8b59d9a13b108/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@c8093e936c6243069d27d36543ee30d5">
<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@c8093e936c6243069d27d36543ee30d5" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<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/a77764884fafa491353daf7a08d21a10/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_trees.pdf" target="[object Object]">Trees (PDF)<br /></a></p>
<p><a href="/assets/courseware/v1/22d1ee248d2c885032efd9d658d62df4/asset-v1:OCW+6.042J+2T2019+type@asset+block/Trees_2.10_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@98ce4308625d444ea913c248277fa467" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<h2 class="hd hd-2 unit-title">Exercise | Trees: Many Definitions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@0714e7b8cb0b46ccb792f78854b7e9e0">
<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@0714e7b8cb0b46ccb792f78854b7e9e0" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_0714e7b8cb0b46ccb792f78854b7e9e0" class="problems-wrapper" role="group"
aria-labelledby="0714e7b8cb0b46ccb792f78854b7e9e0-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@0714e7b8cb0b46ccb792f78854b7e9e0" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@0714e7b8cb0b46ccb792f78854b7e9e0/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="0714e7b8cb0b46ccb792f78854b7e9e0-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@0714e7b8cb0b46ccb792f78854b7e9e0-problem-progress" tabindex="-1">
Trees: Many Definitions
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@0714e7b8cb0b46ccb792f78854b7e9e0-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_0714e7b8cb0b46ccb792f78854b7e9e0_2_1">
<fieldset aria-describedby="status_0714e7b8cb0b46ccb792f78854b7e9e0_2_1">
<legend id="0714e7b8cb0b46ccb792f78854b7e9e0_2_1-legend" class="response-fieldset-legend field-group-hd">Which of the following statements is a valid definition of a tree?</legend>
<div class="field">
<input type="checkbox" name="input_0714e7b8cb0b46ccb792f78854b7e9e0_2_1[]" id="input_0714e7b8cb0b46ccb792f78854b7e9e0_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="0714e7b8cb0b46ccb792f78854b7e9e0_2_1-choice_0-label" for="input_0714e7b8cb0b46ccb792f78854b7e9e0_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_0714e7b8cb0b46ccb792f78854b7e9e0_2_1"> a connected simple graph with no cycles
</label>
</div>
<div class="field">
<input type="checkbox" name="input_0714e7b8cb0b46ccb792f78854b7e9e0_2_1[]" id="input_0714e7b8cb0b46ccb792f78854b7e9e0_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="0714e7b8cb0b46ccb792f78854b7e9e0_2_1-choice_1-label" for="input_0714e7b8cb0b46ccb792f78854b7e9e0_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_0714e7b8cb0b46ccb792f78854b7e9e0_2_1"> a connected simple graph in which every edge is a cut edge
</label>
</div>
<div class="field">
<input type="checkbox" name="input_0714e7b8cb0b46ccb792f78854b7e9e0_2_1[]" id="input_0714e7b8cb0b46ccb792f78854b7e9e0_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="0714e7b8cb0b46ccb792f78854b7e9e0_2_1-choice_2-label" for="input_0714e7b8cb0b46ccb792f78854b7e9e0_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_0714e7b8cb0b46ccb792f78854b7e9e0_2_1"> a simple graph that is connected and vertex-minimal
</label>
</div>
<div class="field">
<input type="checkbox" name="input_0714e7b8cb0b46ccb792f78854b7e9e0_2_1[]" id="input_0714e7b8cb0b46ccb792f78854b7e9e0_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="0714e7b8cb0b46ccb792f78854b7e9e0_2_1-choice_3-label" for="input_0714e7b8cb0b46ccb792f78854b7e9e0_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_0714e7b8cb0b46ccb792f78854b7e9e0_2_1"> a simple graph that is connected and edge-minimal
</label>
</div>
<div class="field">
<input type="checkbox" name="input_0714e7b8cb0b46ccb792f78854b7e9e0_2_1[]" id="input_0714e7b8cb0b46ccb792f78854b7e9e0_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="0714e7b8cb0b46ccb792f78854b7e9e0_2_1-choice_4-label" for="input_0714e7b8cb0b46ccb792f78854b7e9e0_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_0714e7b8cb0b46ccb792f78854b7e9e0_2_1"> an edge-maximal acyclic graph
</label>
</div>
<div class="field">
<input type="checkbox" name="input_0714e7b8cb0b46ccb792f78854b7e9e0_2_1[]" id="input_0714e7b8cb0b46ccb792f78854b7e9e0_2_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="0714e7b8cb0b46ccb792f78854b7e9e0_2_1-choice_5-label" for="input_0714e7b8cb0b46ccb792f78854b7e9e0_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_0714e7b8cb0b46ccb792f78854b7e9e0_2_1"> a connected simple graph with <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
</math> vertices and <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
<mo>&#8722;<!-- &#8722; --></mo>
<mn>1</mn>
</math> edges
</label>
</div>
<div class="field">
<input type="checkbox" name="input_0714e7b8cb0b46ccb792f78854b7e9e0_2_1[]" id="input_0714e7b8cb0b46ccb792f78854b7e9e0_2_1_choice_6" class="field-input input-checkbox" value="choice_6"/><label id="0714e7b8cb0b46ccb792f78854b7e9e0_2_1-choice_6-label" for="input_0714e7b8cb0b46ccb792f78854b7e9e0_2_1_choice_6" class="response-label field-label label-inline" aria-describedby="status_0714e7b8cb0b46ccb792f78854b7e9e0_2_1"> a simple graph with a unique path between any 2 vertices
</label>
</div>
<span id="answer_0714e7b8cb0b46ccb792f78854b7e9e0_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_0714e7b8cb0b46ccb792f78854b7e9e0_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="Trees: Many Definitions" />
<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_0714e7b8cb0b46ccb792f78854b7e9e0" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_0714e7b8cb0b46ccb792f78854b7e9e0">
<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="0714e7b8cb0b46ccb792f78854b7e9e0-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="0714e7b8cb0b46ccb792f78854b7e9e0-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="0714e7b8cb0b46ccb792f78854b7e9e0-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="0714e7b8cb0b46ccb792f78854b7e9e0-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@46b4879482264c73905745e05d0b4c4f" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<h2 class="hd hd-2 unit-title">Lecture Video | Tree Coloring</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@video+block@be5c1c9d93b84cb49fb152397e9b5bc6">
<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@be5c1c9d93b84cb49fb152397e9b5bc6" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Tree Coloring</h3>
<div
id="video_be5c1c9d93b84cb49fb152397e9b5bc6"
class="video closed"
data-metadata='{"ytApiUrl": "https://www.youtube.com/iframe_api", "prioritizeHls": false, "streams": "1.00:g2mOvmC1TKc", "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@be5c1c9d93b84cb49fb152397e9b5bc6/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@be5c1c9d93b84cb49fb152397e9b5bc6/handler/transcript/available_translations", "completionPercentage": 0.95, "sources": ["https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_treecoloring_video_ipod.mp4"], "transcriptTranslationUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@be5c1c9d93b84cb49fb152397e9b5bc6/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@be5c1c9d93b84cb49fb152397e9b5bc6/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="be5c1c9d93b84cb49fb152397e9b5bc6"></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_be5c1c9d93b84cb49fb152397e9b5bc6">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_be5c1c9d93b84cb49fb152397e9b5bc6">
<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_treecoloring_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@be5c1c9d93b84cb49fb152397e9b5bc6/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@be5c1c9d93b84cb49fb152397e9b5bc6/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@0acdf13c07be41b7a49cf681ace4880a">
<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@0acdf13c07be41b7a49cf681ace4880a" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<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/0e587c4091b12a9545e0be39bd7d5a7c/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_treescoloring.pdf" target="[object Object]">Tree Coloring (PDF)</a></p>
<p><a href="/assets/courseware/v1/0b3c64d4369d63b013fcfc21f52317eb/asset-v1:OCW+6.042J+2T2019+type@asset+block/TreeColoring_2.10_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@78aeb20f12bd4b419396a1ffe0e167f6" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<h2 class="hd hd-2 unit-title">Exercise | 2-Colorable Trees</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@57f71903a86e44628cabe5d9bbdbb860">
<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@57f71903a86e44628cabe5d9bbdbb860" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_57f71903a86e44628cabe5d9bbdbb860" class="problems-wrapper" role="group"
aria-labelledby="57f71903a86e44628cabe5d9bbdbb860-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@57f71903a86e44628cabe5d9bbdbb860" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@57f71903a86e44628cabe5d9bbdbb860/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="57f71903a86e44628cabe5d9bbdbb860-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@57f71903a86e44628cabe5d9bbdbb860-problem-progress" tabindex="-1">
2-Colorable Trees
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@57f71903a86e44628cabe5d9bbdbb860-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_57f71903a86e44628cabe5d9bbdbb860_2_1" id="label_57f71903a86e44628cabe5d9bbdbb860_2_1">State the strongest applicable property: "_____ trees are 2-colorable."</label>
<select name="input_57f71903a86e44628cabe5d9bbdbb860_2_1" id="input_57f71903a86e44628cabe5d9bbdbb860_2_1" aria-describedby="status_57f71903a86e44628cabe5d9bbdbb860_2_1">
<option value="option_57f71903a86e44628cabe5d9bbdbb860_2_1_dummy_default">Select an option</option>
<option value="Binary"> Binary</option>
<option value="All"> All</option>
<option value="Even-length"> Even-length</option>
<option value="Odd-length"> Odd-length</option>
<option value="No"> No</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_57f71903a86e44628cabe5d9bbdbb860_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_57f71903a86e44628cabe5d9bbdbb860_2_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="2-Colorable Trees" />
<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_57f71903a86e44628cabe5d9bbdbb860" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_57f71903a86e44628cabe5d9bbdbb860">
<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="57f71903a86e44628cabe5d9bbdbb860-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="57f71903a86e44628cabe5d9bbdbb860-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="57f71903a86e44628cabe5d9bbdbb860-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="57f71903a86e44628cabe5d9bbdbb860-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@864dc79db4c44c299034029c0854abfd" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<h2 class="hd hd-2 unit-title">Lecture Video | Spanning Trees</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@video+block@b65bc752c131474d80eab17e6582dba2">
<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@b65bc752c131474d80eab17e6582dba2" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Spanning Trees</h3>
<div
id="video_b65bc752c131474d80eab17e6582dba2"
class="video closed"
data-metadata='{"ytApiUrl": "https://www.youtube.com/iframe_api", "prioritizeHls": false, "streams": "1.00:_RqqzyWDVMA", "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@b65bc752c131474d80eab17e6582dba2/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@b65bc752c131474d80eab17e6582dba2/handler/transcript/available_translations", "completionPercentage": 0.95, "sources": ["https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_spanningtrees_video_ipod.mp4"], "transcriptTranslationUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@b65bc752c131474d80eab17e6582dba2/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@b65bc752c131474d80eab17e6582dba2/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="b65bc752c131474d80eab17e6582dba2"></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_b65bc752c131474d80eab17e6582dba2">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_b65bc752c131474d80eab17e6582dba2">
<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_spanningtrees_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@b65bc752c131474d80eab17e6582dba2/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@b65bc752c131474d80eab17e6582dba2/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@c7b2d42c1e874c0aa17248468ce8bbf9">
<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@c7b2d42c1e874c0aa17248468ce8bbf9" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<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/2608abe2e67ef5e6ee1306cf4a72e75d/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_SpaingTrees.pdf" target="[object Object]">Spanning Trees (PDF)</a></p>
<p><a href="/assets/courseware/v1/05563f5825bf025f62380b01da5d49a1/asset-v1:OCW+6.042J+2T2019+type@asset+block/SpanningTrees_2.10_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@af6a138e1c6e4d5fb0763c79a22f42c9" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<h2 class="hd hd-2 unit-title">Exercise | Span all the Graphs!</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@073d18e097ff4bfc9b595b6d80d9aaec">
<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@073d18e097ff4bfc9b595b6d80d9aaec" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_073d18e097ff4bfc9b595b6d80d9aaec" class="problems-wrapper" role="group"
aria-labelledby="073d18e097ff4bfc9b595b6d80d9aaec-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@073d18e097ff4bfc9b595b6d80d9aaec" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@073d18e097ff4bfc9b595b6d80d9aaec/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="4"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="073d18e097ff4bfc9b595b6d80d9aaec-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@073d18e097ff4bfc9b595b6d80d9aaec-problem-progress" tabindex="-1">
Span all the Graphs!
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@073d18e097ff4bfc9b595b6d80d9aaec-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p> Fill in the blanks!</p>
<div class="inputtype option-input ">
<label class="problem-group-label" for="input_073d18e097ff4bfc9b595b6d80d9aaec_2_1" id="label_073d18e097ff4bfc9b595b6d80d9aaec_2_1">1. If a graph is _____, then it is guaranteed to have a spanning tree.</label>
<select name="input_073d18e097ff4bfc9b595b6d80d9aaec_2_1" id="input_073d18e097ff4bfc9b595b6d80d9aaec_2_1" aria-describedby="status_073d18e097ff4bfc9b595b6d80d9aaec_2_1">
<option value="option_073d18e097ff4bfc9b595b6d80d9aaec_2_1_dummy_default">Select an option</option>
<option value="simple"> simple</option>
<option value="acyclic"> acyclic</option>
<option value="2-colorable"> 2-colorable</option>
<option value="connected"> connected</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_073d18e097ff4bfc9b595b6d80d9aaec_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_073d18e097ff4bfc9b595b6d80d9aaec_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_073d18e097ff4bfc9b595b6d80d9aaec_3_1" id="label_073d18e097ff4bfc9b595b6d80d9aaec_3_1">2. A _____ of graph <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>G</mi>
</math> has all the vertices of <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>G</mi>
</math>
.</label>
<select name="input_073d18e097ff4bfc9b595b6d80d9aaec_3_1" id="input_073d18e097ff4bfc9b595b6d80d9aaec_3_1" aria-describedby="status_073d18e097ff4bfc9b595b6d80d9aaec_3_1">
<option value="option_073d18e097ff4bfc9b595b6d80d9aaec_3_1_dummy_default">Select an option</option>
<option value="exact copy"> exact copy</option>
<option value="spanning tree"> spanning tree</option>
<option value="spanning subgraph"> spanning subgraph</option>
<option value="{all of the above}"> {all of the above}</option>
<option value="{none of the above}"> {none of the above}</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_073d18e097ff4bfc9b595b6d80d9aaec_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_073d18e097ff4bfc9b595b6d80d9aaec_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_073d18e097ff4bfc9b595b6d80d9aaec_4_1" id="label_073d18e097ff4bfc9b595b6d80d9aaec_4_1">3. Any minimum _____ connected spanning _____ is a spanning _____, as proved by the Well-Ordering Principle.</label>
<select name="input_073d18e097ff4bfc9b595b6d80d9aaec_4_1" id="input_073d18e097ff4bfc9b595b6d80d9aaec_4_1" aria-describedby="status_073d18e097ff4bfc9b595b6d80d9aaec_4_1">
<option value="option_073d18e097ff4bfc9b595b6d80d9aaec_4_1_dummy_default">Select an option</option>
<option value="edge, tree, graph"> edge, tree, graph</option>
<option value="weight, tree, graph"> weight, tree, graph</option>
<option value="edge, graph, tree"> edge, graph, tree</option>
<option value="weight, graph, tree"> weight, graph, tree</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_073d18e097ff4bfc9b595b6d80d9aaec_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_073d18e097ff4bfc9b595b6d80d9aaec_4_1"/>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 4" role="group"><div class="inputtype option-input ">
<label class="problem-group-label" for="input_073d18e097ff4bfc9b595b6d80d9aaec_5_1" id="label_073d18e097ff4bfc9b595b6d80d9aaec_5_1">4. We can build a minimum spanning tree using the gray-edges technique, which involves coloring _____ black and white, selecting the _____ gray edge, and reiterating until we obtain a tree.</label>
<select name="input_073d18e097ff4bfc9b595b6d80d9aaec_5_1" id="input_073d18e097ff4bfc9b595b6d80d9aaec_5_1" aria-describedby="status_073d18e097ff4bfc9b595b6d80d9aaec_5_1">
<option value="option_073d18e097ff4bfc9b595b6d80d9aaec_5_1_dummy_default">Select an option</option>
<option value="vertices, minimum-weight"> vertices, minimum-weight</option>
<option value="components, minimum-weight"> components, minimum-weight</option>
<option value="edges, minimum-length"> edges, minimum-length</option>
<option value="edges, shortest"> edges, shortest</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_073d18e097ff4bfc9b595b6d80d9aaec_5_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_073d18e097ff4bfc9b595b6d80d9aaec_5_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Span all the 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_073d18e097ff4bfc9b595b6d80d9aaec" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_073d18e097ff4bfc9b595b6d80d9aaec">
<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="073d18e097ff4bfc9b595b6d80d9aaec-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="073d18e097ff4bfc9b595b6d80d9aaec-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="073d18e097ff4bfc9b595b6d80d9aaec-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="073d18e097ff4bfc9b595b6d80d9aaec-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@b022e165864f4acc975d0c2dab4348f8" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<h2 class="hd hd-2 unit-title">Exercise | Tree or Not Tree?</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@html+block@f0065cd7e71e4e3482748cb7c55702cc">
<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@f0065cd7e71e4e3482748cb7c55702cc" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p style="text-align: center;">Which of the following graphs are trees?</p>
<p style="text-align: center;"></p>
<h3 style="text-align: center;">Box 1</h3>
<p style="text-align: center;"><img height="310" width="425" src="/assets/courseware/v1/4cf2762be9993032e03464bf7765d6ec/asset-v1:OCW+6.042J+2T2019+type@asset+block/6.042_Unit_II_2.10_1.jpg" alt="Tree or not Tree image 1" /></p>
<p style="text-align: center;"></p>
<h3 style="text-align: center;">Box 2</h3>
<p style="text-align: center;"><img height="350" width="386" src="/assets/courseware/v1/fb36f21b36899baefd13707f47bda346/asset-v1:OCW+6.042J+2T2019+type@asset+block/6.042_Unit_II_2.10_.jpg" alt="Tree or Not Tree? Image 2" /></p>
<p style="text-align: center;"></p>
<h3 style="text-align: center;">Box 3</h3>
<p style="text-align: center;"><img height="310" width="425" src="/assets/courseware/v1/571cb8c9816c08f1d536c093b564f19b/asset-v1:OCW+6.042J+2T2019+type@asset+block/6.042_Unit_II_2.10_3.jpg" alt="Tree or Not Tree? Image 3" /></p>
<h3 style="text-align: center;">Box 4</h3>
<p style="text-align: center;"><img height="310" width="425" src="/assets/courseware/v1/98bdff799425e47f96a8600eedd6b383/asset-v1:OCW+6.042J+2T2019+type@asset+block/6.042_Unit_II_2.10_4.jpg" alt="Tree or Not Tree? Image 4" /></p>
<p style="text-align: center;"></p>
<p style="text-align: center;"></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@be7fc02a4cf94c67ba5a4cbdfe2e7b4e">
<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@be7fc02a4cf94c67ba5a4cbdfe2e7b4e" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_be7fc02a4cf94c67ba5a4cbdfe2e7b4e" class="problems-wrapper" role="group"
aria-labelledby="be7fc02a4cf94c67ba5a4cbdfe2e7b4e-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@be7fc02a4cf94c67ba5a4cbdfe2e7b4e" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@be7fc02a4cf94c67ba5a4cbdfe2e7b4e/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="be7fc02a4cf94c67ba5a4cbdfe2e7b4e-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@be7fc02a4cf94c67ba5a4cbdfe2e7b4e-problem-progress" tabindex="-1">
Tree or Not Tree?
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@be7fc02a4cf94c67ba5a4cbdfe2e7b4e-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_be7fc02a4cf94c67ba5a4cbdfe2e7b4e_2_1">
<fieldset aria-describedby="status_be7fc02a4cf94c67ba5a4cbdfe2e7b4e_2_1">
<div class="field">
<input type="checkbox" name="input_be7fc02a4cf94c67ba5a4cbdfe2e7b4e_2_1[]" id="input_be7fc02a4cf94c67ba5a4cbdfe2e7b4e_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="be7fc02a4cf94c67ba5a4cbdfe2e7b4e_2_1-choice_0-label" for="input_be7fc02a4cf94c67ba5a4cbdfe2e7b4e_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_be7fc02a4cf94c67ba5a4cbdfe2e7b4e_2_1"> Box 1
</label>
</div>
<div class="field">
<input type="checkbox" name="input_be7fc02a4cf94c67ba5a4cbdfe2e7b4e_2_1[]" id="input_be7fc02a4cf94c67ba5a4cbdfe2e7b4e_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="be7fc02a4cf94c67ba5a4cbdfe2e7b4e_2_1-choice_1-label" for="input_be7fc02a4cf94c67ba5a4cbdfe2e7b4e_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_be7fc02a4cf94c67ba5a4cbdfe2e7b4e_2_1"> Box 2
</label>
</div>
<div class="field">
<input type="checkbox" name="input_be7fc02a4cf94c67ba5a4cbdfe2e7b4e_2_1[]" id="input_be7fc02a4cf94c67ba5a4cbdfe2e7b4e_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="be7fc02a4cf94c67ba5a4cbdfe2e7b4e_2_1-choice_2-label" for="input_be7fc02a4cf94c67ba5a4cbdfe2e7b4e_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_be7fc02a4cf94c67ba5a4cbdfe2e7b4e_2_1"> Box 3
</label>
</div>
<div class="field">
<input type="checkbox" name="input_be7fc02a4cf94c67ba5a4cbdfe2e7b4e_2_1[]" id="input_be7fc02a4cf94c67ba5a4cbdfe2e7b4e_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="be7fc02a4cf94c67ba5a4cbdfe2e7b4e_2_1-choice_3-label" for="input_be7fc02a4cf94c67ba5a4cbdfe2e7b4e_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_be7fc02a4cf94c67ba5a4cbdfe2e7b4e_2_1"> Box 4
</label>
</div>
<span id="answer_be7fc02a4cf94c67ba5a4cbdfe2e7b4e_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_be7fc02a4cf94c67ba5a4cbdfe2e7b4e_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_be7fc02a4cf94c67ba5a4cbdfe2e7b4e_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Tree or Not Tree?" />
<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_be7fc02a4cf94c67ba5a4cbdfe2e7b4e" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_be7fc02a4cf94c67ba5a4cbdfe2e7b4e">
<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="be7fc02a4cf94c67ba5a4cbdfe2e7b4e-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="be7fc02a4cf94c67ba5a4cbdfe2e7b4e-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="be7fc02a4cf94c67ba5a4cbdfe2e7b4e-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="be7fc02a4cf94c67ba5a4cbdfe2e7b4e-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@487df0e9047d43e3a553c154bf80edf4" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<h2 class="hd hd-2 unit-title">Exercise | Leaves</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@c54583267fc04d8fabf774cb5d88ec04">
<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@c54583267fc04d8fabf774cb5d88ec04" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_c54583267fc04d8fabf774cb5d88ec04" class="problems-wrapper" role="group"
aria-labelledby="c54583267fc04d8fabf774cb5d88ec04-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@c54583267fc04d8fabf774cb5d88ec04" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@c54583267fc04d8fabf774cb5d88ec04/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="4"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="c54583267fc04d8fabf774cb5d88ec04-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@c54583267fc04d8fabf774cb5d88ec04-problem-progress" tabindex="-1">
Leaves
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@c54583267fc04d8fabf774cb5d88ec04-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_c54583267fc04d8fabf774cb5d88ec04_2_1" class=" capa_inputtype textline">
<div class="unanswered ">
<label class="problem-group-label" for="input_c54583267fc04d8fabf774cb5d88ec04_2_1" id="label_c54583267fc04d8fabf774cb5d88ec04_2_1">1. What is the largest possible number of vertices in a tree whose vertices are all leaves?</label>
<input type="text" name="input_c54583267fc04d8fabf774cb5d88ec04_2_1" id="input_c54583267fc04d8fabf774cb5d88ec04_2_1" aria-describedby="status_c54583267fc04d8fabf774cb5d88ec04_2_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_c54583267fc04d8fabf774cb5d88ec04_2_1"/>
<span class="status unanswered" id="status_c54583267fc04d8fabf774cb5d88ec04_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_c54583267fc04d8fabf774cb5d88ec04_2_1" class="answer"/>
</div>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div id="inputtype_c54583267fc04d8fabf774cb5d88ec04_3_1" class=" capa_inputtype textline">
<div class="unanswered ">
<label class="problem-group-label" for="input_c54583267fc04d8fabf774cb5d88ec04_3_1" id="label_c54583267fc04d8fabf774cb5d88ec04_3_1">2. What is the smallest possible number of leaves in a tree with 99 vertices?</label>
<input type="text" name="input_c54583267fc04d8fabf774cb5d88ec04_3_1" id="input_c54583267fc04d8fabf774cb5d88ec04_3_1" aria-describedby="status_c54583267fc04d8fabf774cb5d88ec04_3_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_c54583267fc04d8fabf774cb5d88ec04_3_1"/>
<span class="status unanswered" id="status_c54583267fc04d8fabf774cb5d88ec04_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_c54583267fc04d8fabf774cb5d88ec04_3_1" class="answer"/>
</div>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><div id="inputtype_c54583267fc04d8fabf774cb5d88ec04_4_1" class=" capa_inputtype textline">
<div class="unanswered ">
<label class="problem-group-label" for="input_c54583267fc04d8fabf774cb5d88ec04_4_1" id="label_c54583267fc04d8fabf774cb5d88ec04_4_1">3. What is the largest possible number of leaves in a tree with 99 vertices?</label>
<input type="text" name="input_c54583267fc04d8fabf774cb5d88ec04_4_1" id="input_c54583267fc04d8fabf774cb5d88ec04_4_1" aria-describedby="status_c54583267fc04d8fabf774cb5d88ec04_4_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_c54583267fc04d8fabf774cb5d88ec04_4_1"/>
<span class="status unanswered" id="status_c54583267fc04d8fabf774cb5d88ec04_4_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_c54583267fc04d8fabf774cb5d88ec04_4_1" class="answer"/>
</div>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 4" role="group"><div id="inputtype_c54583267fc04d8fabf774cb5d88ec04_5_1" class=" capa_inputtype textline">
<div class="unanswered ">
<label class="problem-group-label" for="input_c54583267fc04d8fabf774cb5d88ec04_5_1" id="label_c54583267fc04d8fabf774cb5d88ec04_5_1">4. What is the largest possible number of leaves in a forest with 1000 vertices?</label>
<input type="text" name="input_c54583267fc04d8fabf774cb5d88ec04_5_1" id="input_c54583267fc04d8fabf774cb5d88ec04_5_1" aria-describedby="status_c54583267fc04d8fabf774cb5d88ec04_5_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_c54583267fc04d8fabf774cb5d88ec04_5_1"/>
<span class="status unanswered" id="status_c54583267fc04d8fabf774cb5d88ec04_5_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_c54583267fc04d8fabf774cb5d88ec04_5_1" class="answer"/>
</div>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Leaves" />
<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_c54583267fc04d8fabf774cb5d88ec04" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_c54583267fc04d8fabf774cb5d88ec04">
<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="c54583267fc04d8fabf774cb5d88ec04-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="c54583267fc04d8fabf774cb5d88ec04-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="c54583267fc04d8fabf774cb5d88ec04-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="c54583267fc04d8fabf774cb5d88ec04-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@6ee0b9bcdcbe4c56aff3eb9e66dbaa8c" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<h2 class="hd hd-2 unit-title">Exercise | Minimum Spanning Trees</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@c806a369efd14fa9aabb18bb14c880fc">
<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@c806a369efd14fa9aabb18bb14c880fc" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_c806a369efd14fa9aabb18bb14c880fc" class="problems-wrapper" role="group"
aria-labelledby="c806a369efd14fa9aabb18bb14c880fc-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@c806a369efd14fa9aabb18bb14c880fc" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@c806a369efd14fa9aabb18bb14c880fc/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="c806a369efd14fa9aabb18bb14c880fc-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@c806a369efd14fa9aabb18bb14c880fc-problem-progress" tabindex="-1">
Minimum Spanning Trees
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@c806a369efd14fa9aabb18bb14c880fc-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_c806a369efd14fa9aabb18bb14c880fc_2_1">
<fieldset aria-describedby="status_c806a369efd14fa9aabb18bb14c880fc_2_1">
<legend id="c806a369efd14fa9aabb18bb14c880fc_2_1-legend" class="response-fieldset-legend field-group-hd">1. An MST of a graph G is always unique.</legend>
<div class="field">
<input type="radio" name="input_c806a369efd14fa9aabb18bb14c880fc_2_1" id="input_c806a369efd14fa9aabb18bb14c880fc_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="c806a369efd14fa9aabb18bb14c880fc_2_1-choice_0-label" for="input_c806a369efd14fa9aabb18bb14c880fc_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_c806a369efd14fa9aabb18bb14c880fc_2_1"> True
</label>
</div>
<div class="field">
<input type="radio" name="input_c806a369efd14fa9aabb18bb14c880fc_2_1" id="input_c806a369efd14fa9aabb18bb14c880fc_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="c806a369efd14fa9aabb18bb14c880fc_2_1-choice_1-label" for="input_c806a369efd14fa9aabb18bb14c880fc_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_c806a369efd14fa9aabb18bb14c880fc_2_1"> False
</label>
</div>
<span id="answer_c806a369efd14fa9aabb18bb14c880fc_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_c806a369efd14fa9aabb18bb14c880fc_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_c806a369efd14fa9aabb18bb14c880fc_3_1">
<fieldset aria-describedby="status_c806a369efd14fa9aabb18bb14c880fc_3_1">
<legend id="c806a369efd14fa9aabb18bb14c880fc_3_1-legend" class="response-fieldset-legend field-group-hd">2. Which of following statements must be true about an MST of a connected graph G with distinct edge weights:</legend>
<div class="field">
<input type="checkbox" name="input_c806a369efd14fa9aabb18bb14c880fc_3_1[]" id="input_c806a369efd14fa9aabb18bb14c880fc_3_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="c806a369efd14fa9aabb18bb14c880fc_3_1-choice_0-label" for="input_c806a369efd14fa9aabb18bb14c880fc_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_c806a369efd14fa9aabb18bb14c880fc_3_1"> The MST is unique
</label>
</div>
<div class="field">
<input type="checkbox" name="input_c806a369efd14fa9aabb18bb14c880fc_3_1[]" id="input_c806a369efd14fa9aabb18bb14c880fc_3_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="c806a369efd14fa9aabb18bb14c880fc_3_1-choice_1-label" for="input_c806a369efd14fa9aabb18bb14c880fc_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_c806a369efd14fa9aabb18bb14c880fc_3_1"> The smallest edge is in the MST
</label>
</div>
<div class="field">
<input type="checkbox" name="input_c806a369efd14fa9aabb18bb14c880fc_3_1[]" id="input_c806a369efd14fa9aabb18bb14c880fc_3_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="c806a369efd14fa9aabb18bb14c880fc_3_1-choice_2-label" for="input_c806a369efd14fa9aabb18bb14c880fc_3_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_c806a369efd14fa9aabb18bb14c880fc_3_1"> The largest edge is not in the MST
</label>
</div>
<div class="field">
<input type="checkbox" name="input_c806a369efd14fa9aabb18bb14c880fc_3_1[]" id="input_c806a369efd14fa9aabb18bb14c880fc_3_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="c806a369efd14fa9aabb18bb14c880fc_3_1-choice_3-label" for="input_c806a369efd14fa9aabb18bb14c880fc_3_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_c806a369efd14fa9aabb18bb14c880fc_3_1"> None of the above
</label>
</div>
<span id="answer_c806a369efd14fa9aabb18bb14c880fc_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_c806a369efd14fa9aabb18bb14c880fc_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_c806a369efd14fa9aabb18bb14c880fc_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Minimum Spanning Trees" />
<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_c806a369efd14fa9aabb18bb14c880fc" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_c806a369efd14fa9aabb18bb14c880fc">
<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="c806a369efd14fa9aabb18bb14c880fc-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="c806a369efd14fa9aabb18bb14c880fc-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="c806a369efd14fa9aabb18bb14c880fc-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="c806a369efd14fa9aabb18bb14c880fc-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@fd79e48b1f904884972778ae0b6f8e3a" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<h2 class="hd hd-2 unit-title">Exercise | Graph Algorithm</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@html+block@485f7eb7867f40d5a674a9b23a009c58">
<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@485f7eb7867f40d5a674a9b23a009c58" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>The algorithm STAR MARK starts with a simple undirected graph, <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>G</mi> </math> , with a finite set of vertices, <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>V</mi> </math>, and a set of one or more edges, <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>E</mi> </math>. Initially, all edges are unmarked. Then, <em>STAR MARK</em> proceeds to mark some of the edges, by repeatedly performing the following steps until no further step is possible:</p>
<ol>
<li>Choose any unmarked edge <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>e</mi> <mo>∈<!-- ∈ --></mo> <mi>E</mi> </math> such that there is currently no path of marked edges between the endpoints of <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>e.</mi></math></li>
<li>Mark edge <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>e</mi> </math>.</li>
</ol>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@adcbd6eba0a14a79ac5653a1758a7c9e">
<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@adcbd6eba0a14a79ac5653a1758a7c9e" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_adcbd6eba0a14a79ac5653a1758a7c9e" class="problems-wrapper" role="group"
aria-labelledby="adcbd6eba0a14a79ac5653a1758a7c9e-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@adcbd6eba0a14a79ac5653a1758a7c9e" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@adcbd6eba0a14a79ac5653a1758a7c9e/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="adcbd6eba0a14a79ac5653a1758a7c9e-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@adcbd6eba0a14a79ac5653a1758a7c9e-problem-progress" tabindex="-1">
Preserved Invariants
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@adcbd6eba0a14a79ac5653a1758a7c9e-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_adcbd6eba0a14a79ac5653a1758a7c9e_2_1">
<fieldset aria-describedby="status_adcbd6eba0a14a79ac5653a1758a7c9e_2_1">
<legend id="adcbd6eba0a14a79ac5653a1758a7c9e_2_1-legend" class="response-fieldset-legend field-group-hd">Which of the following predicates are preserved invariants as well as hold for the start state?</legend>
<div class="field">
<input type="checkbox" name="input_adcbd6eba0a14a79ac5653a1758a7c9e_2_1[]" id="input_adcbd6eba0a14a79ac5653a1758a7c9e_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="adcbd6eba0a14a79ac5653a1758a7c9e_2_1-choice_0-label" for="input_adcbd6eba0a14a79ac5653a1758a7c9e_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_adcbd6eba0a14a79ac5653a1758a7c9e_2_1"> There is always an edge that has not been marked.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_adcbd6eba0a14a79ac5653a1758a7c9e_2_1[]" id="input_adcbd6eba0a14a79ac5653a1758a7c9e_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="adcbd6eba0a14a79ac5653a1758a7c9e_2_1-choice_1-label" for="input_adcbd6eba0a14a79ac5653a1758a7c9e_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_adcbd6eba0a14a79ac5653a1758a7c9e_2_1"> The marked edges form an acyclic graph.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_adcbd6eba0a14a79ac5653a1758a7c9e_2_1[]" id="input_adcbd6eba0a14a79ac5653a1758a7c9e_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="adcbd6eba0a14a79ac5653a1758a7c9e_2_1-choice_2-label" for="input_adcbd6eba0a14a79ac5653a1758a7c9e_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_adcbd6eba0a14a79ac5653a1758a7c9e_2_1"> The marked edges form a tree.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_adcbd6eba0a14a79ac5653a1758a7c9e_2_1[]" id="input_adcbd6eba0a14a79ac5653a1758a7c9e_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="adcbd6eba0a14a79ac5653a1758a7c9e_2_1-choice_3-label" for="input_adcbd6eba0a14a79ac5653a1758a7c9e_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_adcbd6eba0a14a79ac5653a1758a7c9e_2_1"> There is always a vertex not touching a marked edge.
</label>
</div>
<span id="answer_adcbd6eba0a14a79ac5653a1758a7c9e_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_adcbd6eba0a14a79ac5653a1758a7c9e_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_adcbd6eba0a14a79ac5653a1758a7c9e_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Preserved 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_adcbd6eba0a14a79ac5653a1758a7c9e" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_adcbd6eba0a14a79ac5653a1758a7c9e">
<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="adcbd6eba0a14a79ac5653a1758a7c9e-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="adcbd6eba0a14a79ac5653a1758a7c9e-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="adcbd6eba0a14a79ac5653a1758a7c9e-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="adcbd6eba0a14a79ac5653a1758a7c9e-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-2" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@61c613793e7a41d984da686d03317f61">
<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@61c613793e7a41d984da686d03317f61" data-request-token="05ea3ec2e12311ef99840affe527bd1b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_61c613793e7a41d984da686d03317f61" class="problems-wrapper" role="group"
aria-labelledby="61c613793e7a41d984da686d03317f61-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@61c613793e7a41d984da686d03317f61" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@61c613793e7a41d984da686d03317f61/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="61c613793e7a41d984da686d03317f61-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@61c613793e7a41d984da686d03317f61-problem-progress" tabindex="-1">
Derived Variables
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@61c613793e7a41d984da686d03317f61-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p>Choose the property that best describes each of the following derived variables.</p>
<p>Answer with the strongest applicable property. For example, for a variable that is constant, the answer should be "constant", even though it is also both weakly increasing and weakly decreasing. </p>
<div class="choicegroup capa_inputtype" id="inputtype_61c613793e7a41d984da686d03317f61_2_1">
<fieldset aria-describedby="status_61c613793e7a41d984da686d03317f61_2_1">
<legend id="61c613793e7a41d984da686d03317f61_2_1-legend" class="response-fieldset-legend field-group-hd">1. # of unmarked edges</legend>
<div class="field">
<input type="radio" name="input_61c613793e7a41d984da686d03317f61_2_1" id="input_61c613793e7a41d984da686d03317f61_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="61c613793e7a41d984da686d03317f61_2_1-choice_0-label" for="input_61c613793e7a41d984da686d03317f61_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_61c613793e7a41d984da686d03317f61_2_1"> strictly increasing
</label>
</div>
<div class="field">
<input type="radio" name="input_61c613793e7a41d984da686d03317f61_2_1" id="input_61c613793e7a41d984da686d03317f61_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="61c613793e7a41d984da686d03317f61_2_1-choice_1-label" for="input_61c613793e7a41d984da686d03317f61_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_61c613793e7a41d984da686d03317f61_2_1"> weakly increasing
</label>
</div>
<div class="field">
<input type="radio" name="input_61c613793e7a41d984da686d03317f61_2_1" id="input_61c613793e7a41d984da686d03317f61_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="61c613793e7a41d984da686d03317f61_2_1-choice_2-label" for="input_61c613793e7a41d984da686d03317f61_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_61c613793e7a41d984da686d03317f61_2_1"> strictly decreasing
</label>
</div>
<div class="field">
<input type="radio" name="input_61c613793e7a41d984da686d03317f61_2_1" id="input_61c613793e7a41d984da686d03317f61_2_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="61c613793e7a41d984da686d03317f61_2_1-choice_3-label" for="input_61c613793e7a41d984da686d03317f61_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_61c613793e7a41d984da686d03317f61_2_1"> weakly decreasing
</label>
</div>
<div class="field">
<input type="radio" name="input_61c613793e7a41d984da686d03317f61_2_1" id="input_61c613793e7a41d984da686d03317f61_2_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="61c613793e7a41d984da686d03317f61_2_1-choice_4-label" for="input_61c613793e7a41d984da686d03317f61_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_61c613793e7a41d984da686d03317f61_2_1"> constant
</label>
</div>
<span id="answer_61c613793e7a41d984da686d03317f61_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_61c613793e7a41d984da686d03317f61_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div><div class="solution-span">
<span id="solution_61c613793e7a41d984da686d03317f61_solution_1"/>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_61c613793e7a41d984da686d03317f61_3_1">
<fieldset aria-describedby="status_61c613793e7a41d984da686d03317f61_3_1">
<legend id="61c613793e7a41d984da686d03317f61_3_1-legend" class="response-fieldset-legend field-group-hd">2. # of marked edges</legend>
<div class="field">
<input type="radio" name="input_61c613793e7a41d984da686d03317f61_3_1" id="input_61c613793e7a41d984da686d03317f61_3_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="61c613793e7a41d984da686d03317f61_3_1-choice_0-label" for="input_61c613793e7a41d984da686d03317f61_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_61c613793e7a41d984da686d03317f61_3_1"> strictly increasing
</label>
</div>
<div class="field">
<input type="radio" name="input_61c613793e7a41d984da686d03317f61_3_1" id="input_61c613793e7a41d984da686d03317f61_3_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="61c613793e7a41d984da686d03317f61_3_1-choice_1-label" for="input_61c613793e7a41d984da686d03317f61_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_61c613793e7a41d984da686d03317f61_3_1"> weakly increasing
</label>
</div>
<div class="field">
<input type="radio" name="input_61c613793e7a41d984da686d03317f61_3_1" id="input_61c613793e7a41d984da686d03317f61_3_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="61c613793e7a41d984da686d03317f61_3_1-choice_2-label" for="input_61c613793e7a41d984da686d03317f61_3_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_61c613793e7a41d984da686d03317f61_3_1"> strictly decreasing
</label>
</div>
<div class="field">
<input type="radio" name="input_61c613793e7a41d984da686d03317f61_3_1" id="input_61c613793e7a41d984da686d03317f61_3_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="61c613793e7a41d984da686d03317f61_3_1-choice_3-label" for="input_61c613793e7a41d984da686d03317f61_3_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_61c613793e7a41d984da686d03317f61_3_1"> weakly decreasing
</label>
</div>
<div class="field">
<input type="radio" name="input_61c613793e7a41d984da686d03317f61_3_1" id="input_61c613793e7a41d984da686d03317f61_3_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="61c613793e7a41d984da686d03317f61_3_1-choice_4-label" for="input_61c613793e7a41d984da686d03317f61_3_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_61c613793e7a41d984da686d03317f61_3_1"> constant
</label>
</div>
<span id="answer_61c613793e7a41d984da686d03317f61_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_61c613793e7a41d984da686d03317f61_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div><div class="solution-span">
<span id="solution_61c613793e7a41d984da686d03317f61_solution_2"/>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><div class="choicegroup capa_inputtype" id="inputtype_61c613793e7a41d984da686d03317f61_4_1">
<fieldset aria-describedby="status_61c613793e7a41d984da686d03317f61_4_1">
<legend id="61c613793e7a41d984da686d03317f61_4_1-legend" class="response-fieldset-legend field-group-hd">3. (# of unmarked edges) + (# of marked edges)</legend>
<div class="field">
<input type="radio" name="input_61c613793e7a41d984da686d03317f61_4_1" id="input_61c613793e7a41d984da686d03317f61_4_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="61c613793e7a41d984da686d03317f61_4_1-choice_0-label" for="input_61c613793e7a41d984da686d03317f61_4_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_61c613793e7a41d984da686d03317f61_4_1"> strictly increasing
</label>
</div>
<div class="field">
<input type="radio" name="input_61c613793e7a41d984da686d03317f61_4_1" id="input_61c613793e7a41d984da686d03317f61_4_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="61c613793e7a41d984da686d03317f61_4_1-choice_1-label" for="input_61c613793e7a41d984da686d03317f61_4_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_61c613793e7a41d984da686d03317f61_4_1"> weakly increasing
</label>
</div>
<div class="field">
<input type="radio" name="input_61c613793e7a41d984da686d03317f61_4_1" id="input_61c613793e7a41d984da686d03317f61_4_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="61c613793e7a41d984da686d03317f61_4_1-choice_2-label" for="input_61c613793e7a41d984da686d03317f61_4_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_61c613793e7a41d984da686d03317f61_4_1"> strictly decreasing
</label>
</div>
<div class="field">
<input type="radio" name="input_61c613793e7a41d984da686d03317f61_4_1" id="input_61c613793e7a41d984da686d03317f61_4_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="61c613793e7a41d984da686d03317f61_4_1-choice_3-label" for="input_61c613793e7a41d984da686d03317f61_4_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_61c613793e7a41d984da686d03317f61_4_1"> weakly decreasing
</label>
</div>
<div class="field">
<input type="radio" name="input_61c613793e7a41d984da686d03317f61_4_1" id="input_61c613793e7a41d984da686d03317f61_4_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="61c613793e7a41d984da686d03317f61_4_1-choice_4-label" for="input_61c613793e7a41d984da686d03317f61_4_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_61c613793e7a41d984da686d03317f61_4_1"> constant
</label>
</div>
<span id="answer_61c613793e7a41d984da686d03317f61_4_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_61c613793e7a41d984da686d03317f61_4_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div><div class="solution-span">
<span id="solution_61c613793e7a41d984da686d03317f61_solution_3"/>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 4" role="group"><div class="choicegroup capa_inputtype" id="inputtype_61c613793e7a41d984da686d03317f61_5_1">
<fieldset aria-describedby="status_61c613793e7a41d984da686d03317f61_5_1">
<legend id="61c613793e7a41d984da686d03317f61_5_1-legend" class="response-fieldset-legend field-group-hd">4. (# of marked edges) - (# of unmarked edges)</legend>
<div class="field">
<input type="radio" name="input_61c613793e7a41d984da686d03317f61_5_1" id="input_61c613793e7a41d984da686d03317f61_5_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="61c613793e7a41d984da686d03317f61_5_1-choice_0-label" for="input_61c613793e7a41d984da686d03317f61_5_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_61c613793e7a41d984da686d03317f61_5_1"> strictly increasing
</label>
</div>
<div class="field">
<input type="radio" name="input_61c613793e7a41d984da686d03317f61_5_1" id="input_61c613793e7a41d984da686d03317f61_5_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="61c613793e7a41d984da686d03317f61_5_1-choice_1-label" for="input_61c613793e7a41d984da686d03317f61_5_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_61c613793e7a41d984da686d03317f61_5_1"> weakly increasing
</label>
</div>
<div class="field">
<input type="radio" name="input_61c613793e7a41d984da686d03317f61_5_1" id="input_61c613793e7a41d984da686d03317f61_5_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="61c613793e7a41d984da686d03317f61_5_1-choice_2-label" for="input_61c613793e7a41d984da686d03317f61_5_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_61c613793e7a41d984da686d03317f61_5_1"> strictly decreasing
</label>
</div>
<div class="field">
<input type="radio" name="input_61c613793e7a41d984da686d03317f61_5_1" id="input_61c613793e7a41d984da686d03317f61_5_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="61c613793e7a41d984da686d03317f61_5_1-choice_3-label" for="input_61c613793e7a41d984da686d03317f61_5_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_61c613793e7a41d984da686d03317f61_5_1"> weakly decreasing
</label>
</div>
<div class="field">
<input type="radio" name="input_61c613793e7a41d984da686d03317f61_5_1" id="input_61c613793e7a41d984da686d03317f61_5_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="61c613793e7a41d984da686d03317f61_5_1-choice_4-label" for="input_61c613793e7a41d984da686d03317f61_5_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_61c613793e7a41d984da686d03317f61_5_1"> constant
</label>
</div>
<span id="answer_61c613793e7a41d984da686d03317f61_5_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_61c613793e7a41d984da686d03317f61_5_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div><div class="solution-span">
<span id="solution_61c613793e7a41d984da686d03317f61_solution_4"/>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 5" role="group"><div class="choicegroup capa_inputtype" id="inputtype_61c613793e7a41d984da686d03317f61_6_1">
<fieldset aria-describedby="status_61c613793e7a41d984da686d03317f61_6_1">
<legend id="61c613793e7a41d984da686d03317f61_6_1-legend" class="response-fieldset-legend field-group-hd">5. (# of connected components) in <math xmlns="http://www.w3.org/1998/Math/MathML">
<msup>
<mi>G</mi>
<mo>&#8242;</mo>
</msup>
</math> with vertices in <math xmlns="http://www.w3.org/1998/Math/MathML">
<msup>
<mi>V</mi>
</msup>
</math> and edges in <math xmlns="http://www.w3.org/1998/Math/MathML">
<msup>
<mi>M</mi>
</msup>
</math>, where <math xmlns="http://www.w3.org/1998/Math/MathML">
<msup>
<mi>M</mi>
</msup>
</math> is the set of marked edges</legend>
<div class="field">
<input type="radio" name="input_61c613793e7a41d984da686d03317f61_6_1" id="input_61c613793e7a41d984da686d03317f61_6_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="61c613793e7a41d984da686d03317f61_6_1-choice_0-label" for="input_61c613793e7a41d984da686d03317f61_6_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_61c613793e7a41d984da686d03317f61_6_1"> strictly increasing
</label>
</div>
<div class="field">
<input type="radio" name="input_61c613793e7a41d984da686d03317f61_6_1" id="input_61c613793e7a41d984da686d03317f61_6_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="61c613793e7a41d984da686d03317f61_6_1-choice_1-label" for="input_61c613793e7a41d984da686d03317f61_6_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_61c613793e7a41d984da686d03317f61_6_1"> weakly increasing
</label>
</div>
<div class="field">
<input type="radio" name="input_61c613793e7a41d984da686d03317f61_6_1" id="input_61c613793e7a41d984da686d03317f61_6_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="61c613793e7a41d984da686d03317f61_6_1-choice_2-label" for="input_61c613793e7a41d984da686d03317f61_6_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_61c613793e7a41d984da686d03317f61_6_1"> strictly decreasing
</label>
</div>
<div class="field">
<input type="radio" name="input_61c613793e7a41d984da686d03317f61_6_1" id="input_61c613793e7a41d984da686d03317f61_6_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="61c613793e7a41d984da686d03317f61_6_1-choice_3-label" for="input_61c613793e7a41d984da686d03317f61_6_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_61c613793e7a41d984da686d03317f61_6_1"> weakly decreasing
</label>
</div>
<div class="field">
<input type="radio" name="input_61c613793e7a41d984da686d03317f61_6_1" id="input_61c613793e7a41d984da686d03317f61_6_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="61c613793e7a41d984da686d03317f61_6_1-choice_4-label" for="input_61c613793e7a41d984da686d03317f61_6_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_61c613793e7a41d984da686d03317f61_6_1"> constant
</label>
</div>
<span id="answer_61c613793e7a41d984da686d03317f61_6_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_61c613793e7a41d984da686d03317f61_6_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div><div class="solution-span">
<span id="solution_61c613793e7a41d984da686d03317f61_solution_5"/>
</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_61c613793e7a41d984da686d03317f61" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_61c613793e7a41d984da686d03317f61">
<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="61c613793e7a41d984da686d03317f61-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="61c613793e7a41d984da686d03317f61-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="61c613793e7a41d984da686d03317f61-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="61c613793e7a41d984da686d03317f61-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>