<div class="xblock xblock-public_view xblock-public_view-vertical" data-block-type="vertical" data-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@878f8548c818465ab0e3c134f0bc21d1" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="False" data-init="VerticalStudentView" data-request-token="bf3edc04dbdb11efb03c029b57e3cc89">
<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@4f247457da91428aaa2a2a6bab54d699">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@4f247457da91428aaa2a2a6bab54d699" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="False" data-init="XBlockToXModuleShim" data-request-token="bf3edc04dbdb11efb03c029b57e3cc89">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>Read <a href="/assets/courseware/v1/de14adc2d3411f76330eeac3324d5e24/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_Session16.pdf" target="[object Object]">Chapter 9.1–9.4 (PDF)</a> of <em>Mathematics for Computer Science</em> for 2.5 Digraphs: Walks & Paths.</p>
<p>View the <a href="/assets/courseware/v1/8d28f7366184ca6678568d50f9a09e85/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_cp16.pdf" target="[object Object]">Section 2.5 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-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@7e625a06f5f942d2a8372f69cf074a7d" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="False" data-init="VerticalStudentView" data-request-token="bf3edc04dbdb11efb03c029b57e3cc89">
<h2 class="hd hd-2 unit-title">Lecture Video | Digraphs: Walks & Paths</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@video+block@1d44f50734d54752a508e6f42288a788">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@video+block@1d44f50734d54752a508e6f42288a788" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="False" data-init="XBlockToXModuleShim" data-request-token="bf3edc04dbdb11efb03c029b57e3cc89">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Digraphs: Walks & Paths</h3>
<div
id="video_1d44f50734d54752a508e6f42288a788"
class="video closed"
data-metadata='{"autoAdvance": false, "transcriptLanguages": {"en": "English"}, "savedVideoPosition": 0.0, "recordedYoutubeIsAvailable": true, "speed": null, "transcriptTranslationUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@1d44f50734d54752a508e6f42288a788/handler/transcript/translation/__lang__", "start": 0.0, "showCaptions": "true", "ytTestTimeout": 1500, "saveStateEnabled": false, "transcriptLanguage": "en", "ytApiUrl": "https://www.youtube.com/iframe_api", "generalSpeed": 1.0, "transcriptAvailableTranslationsUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@1d44f50734d54752a508e6f42288a788/handler/transcript/available_translations", "completionPercentage": 0.95, "end": 0.0, "lmsRootURL": "https://openlearninglibrary.mit.edu", "sources": ["https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_digraphs_ipod.mp4"], "ytMetadataEndpoint": "", "prioritizeHls": false, "autohideHtml5": false, "autoplay": false, "poster": null, "publishCompletionUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@1d44f50734d54752a508e6f42288a788/handler/publish_completion", "saveStateUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@1d44f50734d54752a508e6f42288a788/handler/xmodule_handler/save_user_state", "duration": 0.0, "captionDataDir": null, "completionEnabled": false, "streams": "1.00:MX-mBxt6huU"}'
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="1d44f50734d54752a508e6f42288a788"></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_1d44f50734d54752a508e6f42288a788">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_1d44f50734d54752a508e6f42288a788">
<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_digraphs_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@1d44f50734d54752a508e6f42288a788/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@1d44f50734d54752a508e6f42288a788/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@d13cbca90173450e894d3cf3ea667a50">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@d13cbca90173450e894d3cf3ea667a50" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="False" data-init="XBlockToXModuleShim" data-request-token="bf3edc04dbdb11efb03c029b57e3cc89">
<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/63376f3aabcef1175d92cc0d8fa32474/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_WalksPaths.pdf" target="[object Object]">Digraphs: Walks & Paths (PDF)</a></p>
<p><a href="/assets/courseware/v1/c30c90a8157ef07ddff63083d5a894d7/asset-v1:OCW+6.042J+2T2019+type@asset+block/Digraphs_2.5_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-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@c414b46887024dc2bef9aa3988a861d3" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="False" data-init="VerticalStudentView" data-request-token="bf3edc04dbdb11efb03c029b57e3cc89">
<h2 class="hd hd-2 unit-title">Exercise | Walks and Paths</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@1d8f6e8073db4cbebdaf9e359f14396f">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-block-type="problem" data-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@1d8f6e8073db4cbebdaf9e359f14396f" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="True" data-init="XBlockToXModuleShim" data-request-token="bf3edc04dbdb11efb03c029b57e3cc89">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_1d8f6e8073db4cbebdaf9e359f14396f" class="problems-wrapper" role="group"
aria-labelledby="1d8f6e8073db4cbebdaf9e359f14396f-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@1d8f6e8073db4cbebdaf9e359f14396f" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@1d8f6e8073db4cbebdaf9e359f14396f/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="1d8f6e8073db4cbebdaf9e359f14396f-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@1d8f6e8073db4cbebdaf9e359f14396f-problem-progress" tabindex="-1">
Walks and Paths
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@1d8f6e8073db4cbebdaf9e359f14396f-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_1d8f6e8073db4cbebdaf9e359f14396f_2_1" class=" capa_inputtype textline">
<div class="unanswered ">
<label class="problem-group-label" for="input_1d8f6e8073db4cbebdaf9e359f14396f_2_1" id="label_1d8f6e8073db4cbebdaf9e359f14396f_2_1">1. Let <math xmlns="http://www.w3.org/1998/Math/MathML">
<mo fence="false" stretchy="false">{</mo>
<mi>a</mi>
<mo>,</mo>
<mi>b</mi>
<mo>,</mo>
<mi>c</mi>
<mo>,</mo>
<mi>d</mi>
<mo fence="false" stretchy="false">}</mo>
</math> be four vertices of a directed graph.
<br/>
Let <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>E</mi>
<mo stretchy="false">(</mo>
<mi>G</mi>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mo fence="false" stretchy="false">{</mo>
<mo stretchy="false">(</mo>
<mi>a</mi>
<mo>,</mo>
<mi>b</mi>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mo stretchy="false">(</mo>
<mi>a</mi>
<mo>,</mo>
<mi>c</mi>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mo stretchy="false">(</mo>
<mi>a</mi>
<mo>,</mo>
<mi>d</mi>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mo stretchy="false">(</mo>
<mi>b</mi>
<mo>,</mo>
<mi>c</mi>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mo stretchy="false">(</mo>
<mi>b</mi>
<mo>,</mo>
<mi>d</mi>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mo stretchy="false">(</mo>
<mi>c</mi>
<mo>,</mo>
<mi>b</mi>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mo stretchy="false">(</mo>
<mi>c</mi>
<mo>,</mo>
<mi>d</mi>
<mo stretchy="false">)</mo>
<mo fence="false" stretchy="false">}</mo>
</math>.
<br/>
<br/>
What is the length of the longest path?</label>
<input type="text" name="input_1d8f6e8073db4cbebdaf9e359f14396f_2_1" id="input_1d8f6e8073db4cbebdaf9e359f14396f_2_1" aria-describedby="status_1d8f6e8073db4cbebdaf9e359f14396f_2_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_1d8f6e8073db4cbebdaf9e359f14396f_2_1"/>
<span class="status unanswered" id="status_1d8f6e8073db4cbebdaf9e359f14396f_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_1d8f6e8073db4cbebdaf9e359f14396f_2_1" class="answer"/>
</div>
</div></div>
<br/>
<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_1d8f6e8073db4cbebdaf9e359f14396f_3_1" id="label_1d8f6e8073db4cbebdaf9e359f14396f_3_1">2. If the sum of all the numbers in an adjacency matrix is equal to 6, what does this imply?</label>
<select name="input_1d8f6e8073db4cbebdaf9e359f14396f_3_1" id="input_1d8f6e8073db4cbebdaf9e359f14396f_3_1" aria-describedby="status_1d8f6e8073db4cbebdaf9e359f14396f_3_1">
<option value="option_1d8f6e8073db4cbebdaf9e359f14396f_3_1_dummy_default">Select an option</option>
<option value="There are six edges in total"> There are six edges in total</option>
<option value="There are six vertices in total"> There are six vertices in total</option>
<option value="The sum of the numbers of edges and vertices is equal to 6"> The sum of the numbers of edges and vertices is equal to 6</option>
<option value="None of the above"> None of the above</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_1d8f6e8073db4cbebdaf9e359f14396f_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_1d8f6e8073db4cbebdaf9e359f14396f_3_1"/>
</div></div>
<div class="solution-span">
<span id="solution_1d8f6e8073db4cbebdaf9e359f14396f_solution_1"/>
</div><div class="solution-span">
<span id="solution_1d8f6e8073db4cbebdaf9e359f14396f_solution_2"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Walks and Paths" />
<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_1d8f6e8073db4cbebdaf9e359f14396f" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_1d8f6e8073db4cbebdaf9e359f14396f">
<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="1d8f6e8073db4cbebdaf9e359f14396f-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="1d8f6e8073db4cbebdaf9e359f14396f-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="1d8f6e8073db4cbebdaf9e359f14396f-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="1d8f6e8073db4cbebdaf9e359f14396f-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-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@6effc30a69f74cb0a18829148349587f" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="False" data-init="VerticalStudentView" data-request-token="bf3edc04dbdb11efb03c029b57e3cc89">
<h2 class="hd hd-2 unit-title">Lecture Video | Digraphs: Connected Vertices</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@video+block@57eaebaaf0794cb6b7b25e9a2270005a">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-block-type="video" data-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@video+block@57eaebaaf0794cb6b7b25e9a2270005a" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="False" data-init="XBlockToXModuleShim" data-request-token="bf3edc04dbdb11efb03c029b57e3cc89">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Digraphs: Connected Vertices</h3>
<div
id="video_57eaebaaf0794cb6b7b25e9a2270005a"
class="video closed"
data-metadata='{"autoAdvance": false, "transcriptLanguages": {"en": "English"}, "savedVideoPosition": 0.0, "recordedYoutubeIsAvailable": true, "speed": null, "transcriptTranslationUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@57eaebaaf0794cb6b7b25e9a2270005a/handler/transcript/translation/__lang__", "start": 0.0, "showCaptions": "true", "ytTestTimeout": 1500, "saveStateEnabled": false, "transcriptLanguage": "en", "ytApiUrl": "https://www.youtube.com/iframe_api", "generalSpeed": 1.0, "transcriptAvailableTranslationsUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@57eaebaaf0794cb6b7b25e9a2270005a/handler/transcript/available_translations", "completionPercentage": 0.95, "end": 0.0, "lmsRootURL": "https://openlearninglibrary.mit.edu", "sources": ["https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_connected_ipod.mp4"], "ytMetadataEndpoint": "", "prioritizeHls": false, "autohideHtml5": false, "autoplay": false, "poster": null, "publishCompletionUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@57eaebaaf0794cb6b7b25e9a2270005a/handler/publish_completion", "saveStateUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@57eaebaaf0794cb6b7b25e9a2270005a/handler/xmodule_handler/save_user_state", "duration": 0.0, "captionDataDir": null, "completionEnabled": false, "streams": "1.00:QORX1OUabio"}'
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="57eaebaaf0794cb6b7b25e9a2270005a"></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_57eaebaaf0794cb6b7b25e9a2270005a">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_57eaebaaf0794cb6b7b25e9a2270005a">
<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_connected_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@57eaebaaf0794cb6b7b25e9a2270005a/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@57eaebaaf0794cb6b7b25e9a2270005a/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@2d159b430617402dbb7030d84f581bea">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-block-type="html" data-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@2d159b430617402dbb7030d84f581bea" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="False" data-init="XBlockToXModuleShim" data-request-token="bf3edc04dbdb11efb03c029b57e3cc89">
<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/2f1d3964c93621b01f73d359a2d794dc/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_Concted_Vrtics.pdf" target="[object Object]">Digraphs: Connected Vertices (PDF)</a></p>
<p><a href="/assets/courseware/v1/8ed43d647b74f1d5bab2cb2423b6fb5b/asset-v1:OCW+6.042J+2T2019+type@asset+block/DigraphsCV_2.5_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-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@a1eb9b2264be48e3b8e11b5975fb7977" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="False" data-init="VerticalStudentView" data-request-token="bf3edc04dbdb11efb03c029b57e3cc89">
<h2 class="hd hd-2 unit-title">Exercise | Longest Path</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@9ae14fae12a04ea086981585a7699f01">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-block-type="problem" data-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@9ae14fae12a04ea086981585a7699f01" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="True" data-init="XBlockToXModuleShim" data-request-token="bf3edc04dbdb11efb03c029b57e3cc89">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_9ae14fae12a04ea086981585a7699f01" class="problems-wrapper" role="group"
aria-labelledby="9ae14fae12a04ea086981585a7699f01-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@9ae14fae12a04ea086981585a7699f01" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@9ae14fae12a04ea086981585a7699f01/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="9ae14fae12a04ea086981585a7699f01-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@9ae14fae12a04ea086981585a7699f01-problem-progress" tabindex="-1">
Longest Path
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@9ae14fae12a04ea086981585a7699f01-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p> Consider some graph that has 10 edges and 16 vertices.</p>
<div id="inputtype_9ae14fae12a04ea086981585a7699f01_2_1" class=" capa_inputtype textline">
<div class="unanswered ">
<label class="problem-group-label" for="input_9ae14fae12a04ea086981585a7699f01_2_1" id="label_9ae14fae12a04ea086981585a7699f01_2_1">1. What is the maximum possible length of a <em>longest path</em> in this graph?</label>
<input type="text" name="input_9ae14fae12a04ea086981585a7699f01_2_1" id="input_9ae14fae12a04ea086981585a7699f01_2_1" aria-describedby="status_9ae14fae12a04ea086981585a7699f01_2_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_9ae14fae12a04ea086981585a7699f01_2_1"/>
<span class="status unanswered" id="status_9ae14fae12a04ea086981585a7699f01_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_9ae14fae12a04ea086981585a7699f01_2_1" class="answer"/>
</div>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div id="inputtype_9ae14fae12a04ea086981585a7699f01_3_1" class=" capa_inputtype textline">
<div class="unanswered ">
<label class="problem-group-label" for="input_9ae14fae12a04ea086981585a7699f01_3_1" id="label_9ae14fae12a04ea086981585a7699f01_3_1">2. What is the minimum possible length of a <em>longest path</em> in this graph?</label>
<input type="text" name="input_9ae14fae12a04ea086981585a7699f01_3_1" id="input_9ae14fae12a04ea086981585a7699f01_3_1" aria-describedby="status_9ae14fae12a04ea086981585a7699f01_3_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_9ae14fae12a04ea086981585a7699f01_3_1"/>
<span class="status unanswered" id="status_9ae14fae12a04ea086981585a7699f01_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_9ae14fae12a04ea086981585a7699f01_3_1" class="answer"/>
</div>
</div></div>
<div class="solution-span">
<span id="solution_9ae14fae12a04ea086981585a7699f01_solution_1"/>
</div><div class="solution-span">
<span id="solution_9ae14fae12a04ea086981585a7699f01_solution_2"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Longest Path " />
<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_9ae14fae12a04ea086981585a7699f01" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_9ae14fae12a04ea086981585a7699f01">
<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="9ae14fae12a04ea086981585a7699f01-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="9ae14fae12a04ea086981585a7699f01-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="9ae14fae12a04ea086981585a7699f01-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="9ae14fae12a04ea086981585a7699f01-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-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@09e632715e8c46f1988ecc7da218581d" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="False" data-init="VerticalStudentView" data-request-token="bf3edc04dbdb11efb03c029b57e3cc89">
<h2 class="hd hd-2 unit-title">Exercise | Adjacency Matrix</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@0b266a2319004cc5bc720991c2ca5d99">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-block-type="problem" data-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@0b266a2319004cc5bc720991c2ca5d99" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="True" data-init="XBlockToXModuleShim" data-request-token="bf3edc04dbdb11efb03c029b57e3cc89">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_0b266a2319004cc5bc720991c2ca5d99" class="problems-wrapper" role="group"
aria-labelledby="0b266a2319004cc5bc720991c2ca5d99-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@0b266a2319004cc5bc720991c2ca5d99" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@0b266a2319004cc5bc720991c2ca5d99/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="0b266a2319004cc5bc720991c2ca5d99-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@0b266a2319004cc5bc720991c2ca5d99-problem-progress" tabindex="-1">
Adjacency Matrix
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@0b266a2319004cc5bc720991c2ca5d99-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p>Suppose we have an adjacency matrix A representation of a directed graph G.
</p>
<p>Which of the following must be true for any adjacency matrix, regardless of the underlying graph?</p>
<p> Some matrix definitions: </p>
<div class="choicegroup capa_inputtype" id="inputtype_0b266a2319004cc5bc720991c2ca5d99_2_1">
<fieldset aria-describedby="status_0b266a2319004cc5bc720991c2ca5d99_2_1">
<legend id="0b266a2319004cc5bc720991c2ca5d99_2_1-legend" class="response-fieldset-legend field-group-hd"><math xmlns="http://www.w3.org/1998/Math/MathML">
<msup>
<mi>A</mi>
<mi>T</mi>
</msup>
</math>denotes the transpose of a matrix <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>A</mi>
</math>, such that if <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>A</mi>
</math> has <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>m</mi>
</math> rows and <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
</math> columns, <math xmlns="http://www.w3.org/1998/Math/MathML">
<msup>
<mi>A</mi>
<mi>T</mi>
</msup>
</math> has <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>n</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>m</mi>
</math> columns. Additionally, the value of the cell in <math xmlns="http://www.w3.org/1998/Math/MathML">
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo>,</mo>
<mi>j</mi>
<mo stretchy="false">)</mo>
</math> in <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>A</mi>
</math> becomes the value of the cell <math xmlns="http://www.w3.org/1998/Math/MathML">
<mo stretchy="false">(</mo>
<mi>j</mi>
<mo>,</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
</math> in <math xmlns="http://www.w3.org/1998/Math/MathML">
<msup>
<mi>A</mi>
<mi>T</mi>
</msup>
</math>.</legend>
<div class="field">
<input type="checkbox" name="input_0b266a2319004cc5bc720991c2ca5d99_2_1[]" id="input_0b266a2319004cc5bc720991c2ca5d99_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="0b266a2319004cc5bc720991c2ca5d99_2_1-choice_0-label" for="input_0b266a2319004cc5bc720991c2ca5d99_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_0b266a2319004cc5bc720991c2ca5d99_2_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>A</mi>
<mo>=</mo>
<msup>
<mi>A</mi>
<mi>T</mi>
</msup>
</math>
</label>
</div>
<div class="field">
<input type="checkbox" name="input_0b266a2319004cc5bc720991c2ca5d99_2_1[]" id="input_0b266a2319004cc5bc720991c2ca5d99_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="0b266a2319004cc5bc720991c2ca5d99_2_1-choice_1-label" for="input_0b266a2319004cc5bc720991c2ca5d99_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_0b266a2319004cc5bc720991c2ca5d99_2_1"> A cell <math xmlns="http://www.w3.org/1998/Math/MathML">
<mo stretchy="false">(</mo>
<mi>i</mi>
<mo>,</mo>
<mi>j</mi>
<mo stretchy="false">)</mo>
</math> in the matrix <math xmlns="http://www.w3.org/1998/Math/MathML">
<msup>
<mi>A</mi>
<mn>2</mn>
</msup>
</math> has non-zero value iff there is a length 2 path between the <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>i</mi>
</math>-th and <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>j</mi>
</math>-th vertices.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_0b266a2319004cc5bc720991c2ca5d99_2_1[]" id="input_0b266a2319004cc5bc720991c2ca5d99_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="0b266a2319004cc5bc720991c2ca5d99_2_1-choice_2-label" for="input_0b266a2319004cc5bc720991c2ca5d99_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_0b266a2319004cc5bc720991c2ca5d99_2_1"> Every row in <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>A</mi>
</math> must be different.
</label>
</div>
<span id="answer_0b266a2319004cc5bc720991c2ca5d99_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_0b266a2319004cc5bc720991c2ca5d99_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_0b266a2319004cc5bc720991c2ca5d99_solution_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Adjacency Matrix" />
<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_0b266a2319004cc5bc720991c2ca5d99" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_0b266a2319004cc5bc720991c2ca5d99">
<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="0b266a2319004cc5bc720991c2ca5d99-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="0b266a2319004cc5bc720991c2ca5d99-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="0b266a2319004cc5bc720991c2ca5d99-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="0b266a2319004cc5bc720991c2ca5d99-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-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@2b912b00b4504b6193d7a4a749545fcf" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="False" data-init="VerticalStudentView" data-request-token="bf3edc04dbdb11efb03c029b57e3cc89">
<h2 class="hd hd-2 unit-title">Exercise | Counting Paths</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@9a8edc0f0c31465aaf0788061035d340">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-block-type="problem" data-runtime-version="1" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@9a8edc0f0c31465aaf0788061035d340" data-graded="False" data-runtime-class="LmsRuntime" data-course-id="course-v1:OCW+6.042J+2T2019" data-has-score="True" data-init="XBlockToXModuleShim" data-request-token="bf3edc04dbdb11efb03c029b57e3cc89">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_9a8edc0f0c31465aaf0788061035d340" class="problems-wrapper" role="group"
aria-labelledby="9a8edc0f0c31465aaf0788061035d340-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@9a8edc0f0c31465aaf0788061035d340" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@9a8edc0f0c31465aaf0788061035d340/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="3"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="9a8edc0f0c31465aaf0788061035d340-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@9a8edc0f0c31465aaf0788061035d340-problem-progress" tabindex="-1">
Counting Paths
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@9a8edc0f0c31465aaf0788061035d340-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_9a8edc0f0c31465aaf0788061035d340_2_1" class=" capa_inputtype textline">
<div class="unanswered ">
<label class="problem-group-label" for="input_9a8edc0f0c31465aaf0788061035d340_2_1" id="label_9a8edc0f0c31465aaf0788061035d340_2_1">Suppose we have a complete directed graph of 5 vertices with no self-edge.
<br/>
<br/>
That is, for any <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>i</mi>
<mo>,</mo>
<mi>j</mi>
<mo>=</mo>
<mn>1</mn>
<mo>,</mo>
<mn>2</mn>
<mo>,</mo>
<mn>3</mn>
<mo>,</mo>
<mn>4</mn>
<mo>,</mo>
<mn>5</mn>
</math>, edge <math xmlns="http://www.w3.org/1998/Math/MathML">
<mo stretchy="false">(</mo>
<msub>
<mi>v</mi>
<mi>i</mi>
</msub>
<mo>,</mo>
<msub>
<mi>v</mi>
<mi>j</mi>
</msub>
<mo stretchy="false">)</mo>
</math> exists iff <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>i</mi>
<mo>&#8800;<!-- &#8800; --></mo>
<mi>j</mi>
</math>.
<br/>
<br/>
1. How many edges are in the graph?</label>
<input type="text" name="input_9a8edc0f0c31465aaf0788061035d340_2_1" id="input_9a8edc0f0c31465aaf0788061035d340_2_1" aria-describedby="status_9a8edc0f0c31465aaf0788061035d340_2_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_9a8edc0f0c31465aaf0788061035d340_2_1"/>
<span class="status unanswered" id="status_9a8edc0f0c31465aaf0788061035d340_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_9a8edc0f0c31465aaf0788061035d340_2_1" class="answer"/>
</div>
</div></div>
<br/>
<br/>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><p> 2. What is the length of the longest path not containing a cycle?</p>
<div id="inputtype_9a8edc0f0c31465aaf0788061035d340_3_1" class=" capa_inputtype textline">
<div class="unanswered ">
<input type="text" name="input_9a8edc0f0c31465aaf0788061035d340_3_1" id="input_9a8edc0f0c31465aaf0788061035d340_3_1" aria-describedby="status_9a8edc0f0c31465aaf0788061035d340_3_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_9a8edc0f0c31465aaf0788061035d340_3_1"/>
<span class="status unanswered" id="status_9a8edc0f0c31465aaf0788061035d340_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_9a8edc0f0c31465aaf0788061035d340_3_1" class="answer"/>
</div>
</div></div>
<br/>
<br/>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><p> 3. How many paths are there that satisfy the previous condition?</p>
<div id="inputtype_9a8edc0f0c31465aaf0788061035d340_4_1" class=" capa_inputtype textline">
<div class="unanswered ">
<input type="text" name="input_9a8edc0f0c31465aaf0788061035d340_4_1" id="input_9a8edc0f0c31465aaf0788061035d340_4_1" aria-describedby="status_9a8edc0f0c31465aaf0788061035d340_4_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_9a8edc0f0c31465aaf0788061035d340_4_1"/>
<span class="status unanswered" id="status_9a8edc0f0c31465aaf0788061035d340_4_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_9a8edc0f0c31465aaf0788061035d340_4_1" class="answer"/>
</div>
</div></div>
<br/>
<br/>
<div class="solution-span">
<span id="solution_9a8edc0f0c31465aaf0788061035d340_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Counting Paths" />
<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_9a8edc0f0c31465aaf0788061035d340" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_9a8edc0f0c31465aaf0788061035d340">
<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="9a8edc0f0c31465aaf0788061035d340-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="9a8edc0f0c31465aaf0788061035d340-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="9a8edc0f0c31465aaf0788061035d340-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="9a8edc0f0c31465aaf0788061035d340-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>