<div class="xblock xblock-public_view xblock-public_view-vertical" data-course-id="course-v1:OCW+6.042J+2T2019" data-runtime-class="LmsRuntime" data-request-token="374384f2e12211ef932016ffeba94eb7" data-block-type="vertical" data-graded="False" data-runtime-version="1" data-init="VerticalStudentView" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@816e5d531b7646e6af7d382d5604c19f">
<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@a201ef2eb3dc4aa1a53e13305038dff6">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-course-id="course-v1:OCW+6.042J+2T2019" data-runtime-class="LmsRuntime" data-request-token="374384f2e12211ef932016ffeba94eb7" data-block-type="html" data-graded="False" data-runtime-version="1" data-init="XBlockToXModuleShim" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@a201ef2eb3dc4aa1a53e13305038dff6">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>Read <a href="/assets/courseware/v1/c6cc62b2c9146170a0dcf2923e6f286c/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_Session10.pdf" target="[object Object]">Chapter 6 (PDF) </a>of <em>Mathematics for Computer Science</em> for 1.10 Recursive Definition.</p>
<p>View the <a href="/assets/courseware/v1/4fd0c6fb3dd99ee56ba88930f138428f/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS15_cp10.pdf" target="[object Object]">Section 1.10 In-Class Questions (PDF)</a></p>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-course-id="course-v1:OCW+6.042J+2T2019" data-runtime-class="LmsRuntime" data-request-token="374384f2e12211ef932016ffeba94eb7" data-block-type="vertical" data-graded="False" data-runtime-version="1" data-init="VerticalStudentView" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@de3061678a0c49d899a574691563121d">
<h2 class="hd hd-2 unit-title">Lecture Video | Recursive Data</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@video+block@0692d1745c174333861707366162f060">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-course-id="course-v1:OCW+6.042J+2T2019" data-runtime-class="LmsRuntime" data-request-token="374384f2e12211ef932016ffeba94eb7" data-block-type="video" data-graded="False" data-runtime-version="1" data-init="XBlockToXModuleShim" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@video+block@0692d1745c174333861707366162f060">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Recursive Data</h3>
<div
id="video_0692d1745c174333861707366162f060"
class="video closed"
data-metadata='{"streams": "1.00:TXNXT3oBROw", "autohideHtml5": false, "autoplay": false, "transcriptTranslationUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@0692d1745c174333861707366162f060/handler/transcript/translation/__lang__", "transcriptLanguage": "en", "publishCompletionUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@0692d1745c174333861707366162f060/handler/publish_completion", "transcriptAvailableTranslationsUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@0692d1745c174333861707366162f060/handler/transcript/available_translations", "completionEnabled": false, "generalSpeed": 1.0, "ytTestTimeout": 1500, "ytMetadataEndpoint": "", "ytApiUrl": "https://www.youtube.com/iframe_api", "showCaptions": "true", "recordedYoutubeIsAvailable": true, "sources": ["https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_recursivedata_ipod.mp4"], "end": 0.0, "saveStateEnabled": false, "prioritizeHls": false, "savedVideoPosition": 0.0, "captionDataDir": null, "transcriptLanguages": {"en": "English"}, "start": 0.0, "saveStateUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@0692d1745c174333861707366162f060/handler/xmodule_handler/save_user_state", "speed": null, "autoAdvance": false, "completionPercentage": 0.95, "duration": 0.0, "lmsRootURL": "https://openlearninglibrary.mit.edu", "poster": null}'
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="0692d1745c174333861707366162f060"></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_0692d1745c174333861707366162f060">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_0692d1745c174333861707366162f060">
<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_recursivedata_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@0692d1745c174333861707366162f060/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@0692d1745c174333861707366162f060/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@9202b16aa9c94f229c8061022b76d624">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-course-id="course-v1:OCW+6.042J+2T2019" data-runtime-class="LmsRuntime" data-request-token="374384f2e12211ef932016ffeba94eb7" data-block-type="html" data-graded="False" data-runtime-version="1" data-init="XBlockToXModuleShim" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@9202b16aa9c94f229c8061022b76d624">
<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/8c5426e2494e6e2e86c2f65edf74fb8b/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS16_RecursiveData.pdf" target="[object Object]">Recursive Data (PDF)</a></p>
<p><a href="/assets/courseware/v1/890e27017619b402e91eba7781e41ea6/asset-v1:OCW+6.042J+2T2019+type@asset+block/RecursiveData_1.10_Trans.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-course-id="course-v1:OCW+6.042J+2T2019" data-runtime-class="LmsRuntime" data-request-token="374384f2e12211ef932016ffeba94eb7" data-block-type="vertical" data-graded="False" data-runtime-version="1" data-init="VerticalStudentView" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@8eeca4a009ea427784bfeaf7dfd22e56">
<h2 class="hd hd-2 unit-title">Exercise | Matching Parentheses</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@f98088975301471b9b84a3a8c87c28e0">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-course-id="course-v1:OCW+6.042J+2T2019" data-runtime-class="LmsRuntime" data-request-token="374384f2e12211ef932016ffeba94eb7" data-block-type="problem" data-graded="False" data-runtime-version="1" data-init="XBlockToXModuleShim" data-has-score="True" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@f98088975301471b9b84a3a8c87c28e0">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_f98088975301471b9b84a3a8c87c28e0" class="problems-wrapper" role="group"
aria-labelledby="f98088975301471b9b84a3a8c87c28e0-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@f98088975301471b9b84a3a8c87c28e0" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@f98088975301471b9b84a3a8c87c28e0/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="f98088975301471b9b84a3a8c87c28e0-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@f98088975301471b9b84a3a8c87c28e0-problem-progress" tabindex="-1">
Matching Parentheses
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@f98088975301471b9b84a3a8c87c28e0-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_f98088975301471b9b84a3a8c87c28e0_2_1">
<fieldset aria-describedby="status_f98088975301471b9b84a3a8c87c28e0_2_1">
<legend id="f98088975301471b9b84a3a8c87c28e0_2_1-legend" class="response-fieldset-legend field-group-hd">Which of the following are true about <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>M</mi>
</math>, the set of matched parentheses strings?</legend>
<div class="field">
<input type="checkbox" name="input_f98088975301471b9b84a3a8c87c28e0_2_1[]" id="input_f98088975301471b9b84a3a8c87c28e0_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="f98088975301471b9b84a3a8c87c28e0_2_1-choice_0-label" for="input_f98088975301471b9b84a3a8c87c28e0_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_f98088975301471b9b84a3a8c87c28e0_2_1"> No string in <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>M</mi>
</math> can start with a right parenthesis.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_f98088975301471b9b84a3a8c87c28e0_2_1[]" id="input_f98088975301471b9b84a3a8c87c28e0_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="f98088975301471b9b84a3a8c87c28e0_2_1-choice_1-label" for="input_f98088975301471b9b84a3a8c87c28e0_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_f98088975301471b9b84a3a8c87c28e0_2_1"> Every string in <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>M</mi>
</math> must start with a left parentheses.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_f98088975301471b9b84a3a8c87c28e0_2_1[]" id="input_f98088975301471b9b84a3a8c87c28e0_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="f98088975301471b9b84a3a8c87c28e0_2_1-choice_2-label" for="input_f98088975301471b9b84a3a8c87c28e0_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_f98088975301471b9b84a3a8c87c28e0_2_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>M</mi>
</math> is an infinite set.
</label>
</div>
<div class="field">
<input type="checkbox" name="input_f98088975301471b9b84a3a8c87c28e0_2_1[]" id="input_f98088975301471b9b84a3a8c87c28e0_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="f98088975301471b9b84a3a8c87c28e0_2_1-choice_3-label" for="input_f98088975301471b9b84a3a8c87c28e0_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_f98088975301471b9b84a3a8c87c28e0_2_1"> Every string in <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>M</mi>
</math> must have even length.
</label>
</div>
<span id="answer_f98088975301471b9b84a3a8c87c28e0_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_f98088975301471b9b84a3a8c87c28e0_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_f98088975301471b9b84a3a8c87c28e0_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Matching Parentheses" />
<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_f98088975301471b9b84a3a8c87c28e0" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_f98088975301471b9b84a3a8c87c28e0">
<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="f98088975301471b9b84a3a8c87c28e0-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="f98088975301471b9b84a3a8c87c28e0-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="f98088975301471b9b84a3a8c87c28e0-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="f98088975301471b9b84a3a8c87c28e0-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-course-id="course-v1:OCW+6.042J+2T2019" data-runtime-class="LmsRuntime" data-request-token="374384f2e12211ef932016ffeba94eb7" data-block-type="vertical" data-graded="False" data-runtime-version="1" data-init="VerticalStudentView" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@4cfb244f542b4bc4b077c1be6fedb51e">
<h2 class="hd hd-2 unit-title">Exercise | Building Functions in F18</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@73de76dc56ab460f97f0672cdd54f1e9">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-course-id="course-v1:OCW+6.042J+2T2019" data-runtime-class="LmsRuntime" data-request-token="374384f2e12211ef932016ffeba94eb7" data-block-type="problem" data-graded="False" data-runtime-version="1" data-init="XBlockToXModuleShim" data-has-score="True" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@73de76dc56ab460f97f0672cdd54f1e9">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_73de76dc56ab460f97f0672cdd54f1e9" class="problems-wrapper" role="group"
aria-labelledby="73de76dc56ab460f97f0672cdd54f1e9-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@73de76dc56ab460f97f0672cdd54f1e9" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@73de76dc56ab460f97f0672cdd54f1e9/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="73de76dc56ab460f97f0672cdd54f1e9-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@73de76dc56ab460f97f0672cdd54f1e9-problem-progress" tabindex="-1">
Building Functions in F18
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@73de76dc56ab460f97f0672cdd54f1e9-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_73de76dc56ab460f97f0672cdd54f1e9_2_1">
<fieldset aria-describedby="status_73de76dc56ab460f97f0672cdd54f1e9_2_1">
<legend id="73de76dc56ab460f97f0672cdd54f1e9_2_1-legend" class="response-fieldset-legend field-group-hd">1. Of the starter functions, <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>I</mi>
<msub>
<mi>d</mi>
<mi>R</mi>
</msub>
</math>, constants <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>s</mi>
<mi>i</mi>
<mi>n</mi>
<mo stretchy="false">(</mo>
<mi>x</mi>
<mo stretchy="false">)</mo>
</math>, which are needed to generate <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>c</mi>
<mi>o</mi>
<mi>s</mi>
<mo stretchy="false">(</mo>
<mi>x</mi>
<mo stretchy="false">)</mo>
</math>, taking advantage of the identity <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>c</mi>
<mi>o</mi>
<mi>s</mi>
<mo stretchy="false">(</mo>
<mi>x</mi>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mi>s</mi>
<mi>i</mi>
<mi>n</mi>
<mo stretchy="false">(</mo>
<mi>x</mi>
<mo>+</mo>
<mi>&#960;<!-- &#960; --></mi>
<mo>/</mo>
<mn>2</mn>
<mo stretchy="false">)</mo>
</math>?</legend>
<div class="field">
<input type="radio" name="input_73de76dc56ab460f97f0672cdd54f1e9_2_1" id="input_73de76dc56ab460f97f0672cdd54f1e9_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="73de76dc56ab460f97f0672cdd54f1e9_2_1-choice_0-label" for="input_73de76dc56ab460f97f0672cdd54f1e9_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_73de76dc56ab460f97f0672cdd54f1e9_2_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>I</mi>
<msub>
<mi>d</mi>
<mi>R</mi>
</msub>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>s</mi>
<mi>i</mi>
<mi>n</mi>
<mo stretchy="false">(</mo>
<mi>x</mi>
<mo stretchy="false">)</mo>
</math>
</label>
</div>
<div class="field">
<input type="radio" name="input_73de76dc56ab460f97f0672cdd54f1e9_2_1" id="input_73de76dc56ab460f97f0672cdd54f1e9_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="73de76dc56ab460f97f0672cdd54f1e9_2_1-choice_1-label" for="input_73de76dc56ab460f97f0672cdd54f1e9_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_73de76dc56ab460f97f0672cdd54f1e9_2_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>s</mi>
<mi>i</mi>
<mi>n</mi>
<mo stretchy="false">(</mo>
<mi>x</mi>
<mo stretchy="false">)</mo>
</math> only
</label>
</div>
<div class="field">
<input type="radio" name="input_73de76dc56ab460f97f0672cdd54f1e9_2_1" id="input_73de76dc56ab460f97f0672cdd54f1e9_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="73de76dc56ab460f97f0672cdd54f1e9_2_1-choice_2-label" for="input_73de76dc56ab460f97f0672cdd54f1e9_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_73de76dc56ab460f97f0672cdd54f1e9_2_1"> constants and <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>s</mi>
<mi>i</mi>
<mi>n</mi>
<mo stretchy="false">(</mo>
<mi>x</mi>
<mo stretchy="false">)</mo>
</math>
</label>
</div>
<div class="field">
<input type="radio" name="input_73de76dc56ab460f97f0672cdd54f1e9_2_1" id="input_73de76dc56ab460f97f0672cdd54f1e9_2_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="73de76dc56ab460f97f0672cdd54f1e9_2_1-choice_3-label" for="input_73de76dc56ab460f97f0672cdd54f1e9_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_73de76dc56ab460f97f0672cdd54f1e9_2_1"> <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>I</mi>
<msub>
<mi>d</mi>
<mi>R</mi>
</msub>
</math>, constants, and <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>s</mi>
<mi>i</mi>
<mi>n</mi>
<mo stretchy="false">(</mo>
<mi>x</mi>
<mo stretchy="false">)</mo>
</math>
</label>
</div>
<span id="answer_73de76dc56ab460f97f0672cdd54f1e9_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_73de76dc56ab460f97f0672cdd54f1e9_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_73de76dc56ab460f97f0672cdd54f1e9_3_1">
<fieldset aria-describedby="status_73de76dc56ab460f97f0672cdd54f1e9_3_1">
<legend id="73de76dc56ab460f97f0672cdd54f1e9_3_1-legend" class="response-fieldset-legend field-group-hd">2. In the above process, which of the following rules are used?</legend>
<div class="field">
<input type="checkbox" name="input_73de76dc56ab460f97f0672cdd54f1e9_3_1[]" id="input_73de76dc56ab460f97f0672cdd54f1e9_3_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="73de76dc56ab460f97f0672cdd54f1e9_3_1-choice_0-label" for="input_73de76dc56ab460f97f0672cdd54f1e9_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_73de76dc56ab460f97f0672cdd54f1e9_3_1"> Addition
</label>
</div>
<div class="field">
<input type="checkbox" name="input_73de76dc56ab460f97f0672cdd54f1e9_3_1[]" id="input_73de76dc56ab460f97f0672cdd54f1e9_3_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="73de76dc56ab460f97f0672cdd54f1e9_3_1-choice_1-label" for="input_73de76dc56ab460f97f0672cdd54f1e9_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_73de76dc56ab460f97f0672cdd54f1e9_3_1"> Multiplication
</label>
</div>
<div class="field">
<input type="checkbox" name="input_73de76dc56ab460f97f0672cdd54f1e9_3_1[]" id="input_73de76dc56ab460f97f0672cdd54f1e9_3_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="73de76dc56ab460f97f0672cdd54f1e9_3_1-choice_2-label" for="input_73de76dc56ab460f97f0672cdd54f1e9_3_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_73de76dc56ab460f97f0672cdd54f1e9_3_1"> Exponentiation
</label>
</div>
<div class="field">
<input type="checkbox" name="input_73de76dc56ab460f97f0672cdd54f1e9_3_1[]" id="input_73de76dc56ab460f97f0672cdd54f1e9_3_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="73de76dc56ab460f97f0672cdd54f1e9_3_1-choice_3-label" for="input_73de76dc56ab460f97f0672cdd54f1e9_3_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_73de76dc56ab460f97f0672cdd54f1e9_3_1"> Inverse
</label>
</div>
<div class="field">
<input type="checkbox" name="input_73de76dc56ab460f97f0672cdd54f1e9_3_1[]" id="input_73de76dc56ab460f97f0672cdd54f1e9_3_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="73de76dc56ab460f97f0672cdd54f1e9_3_1-choice_4-label" for="input_73de76dc56ab460f97f0672cdd54f1e9_3_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_73de76dc56ab460f97f0672cdd54f1e9_3_1"> Composition
</label>
</div>
<span id="answer_73de76dc56ab460f97f0672cdd54f1e9_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_73de76dc56ab460f97f0672cdd54f1e9_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_73de76dc56ab460f97f0672cdd54f1e9_solution_1"/>
</div><div class="solution-span">
<span id="solution_73de76dc56ab460f97f0672cdd54f1e9_solution_2"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Building Functions in F18" />
<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_73de76dc56ab460f97f0672cdd54f1e9" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_73de76dc56ab460f97f0672cdd54f1e9">
<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="73de76dc56ab460f97f0672cdd54f1e9-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="73de76dc56ab460f97f0672cdd54f1e9-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="73de76dc56ab460f97f0672cdd54f1e9-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="73de76dc56ab460f97f0672cdd54f1e9-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-course-id="course-v1:OCW+6.042J+2T2019" data-runtime-class="LmsRuntime" data-request-token="374384f2e12211ef932016ffeba94eb7" data-block-type="vertical" data-graded="False" data-runtime-version="1" data-init="VerticalStudentView" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@a18b482e5b954f73a68ead7084998e22">
<h2 class="hd hd-2 unit-title">Lecture Video | Structural Induction</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@video+block@54185b6bd3c74c0f9beb6c2acb415b7d">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-course-id="course-v1:OCW+6.042J+2T2019" data-runtime-class="LmsRuntime" data-request-token="374384f2e12211ef932016ffeba94eb7" data-block-type="video" data-graded="False" data-runtime-version="1" data-init="XBlockToXModuleShim" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@video+block@54185b6bd3c74c0f9beb6c2acb415b7d">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Structural Induction</h3>
<div
id="video_54185b6bd3c74c0f9beb6c2acb415b7d"
class="video closed"
data-metadata='{"streams": "1.00:VWIDwHCGJDQ", "autohideHtml5": false, "autoplay": false, "transcriptTranslationUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@54185b6bd3c74c0f9beb6c2acb415b7d/handler/transcript/translation/__lang__", "transcriptLanguage": "en", "publishCompletionUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@54185b6bd3c74c0f9beb6c2acb415b7d/handler/publish_completion", "transcriptAvailableTranslationsUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@54185b6bd3c74c0f9beb6c2acb415b7d/handler/transcript/available_translations", "completionEnabled": false, "generalSpeed": 1.0, "ytTestTimeout": 1500, "ytMetadataEndpoint": "", "ytApiUrl": "https://www.youtube.com/iframe_api", "showCaptions": "true", "recordedYoutubeIsAvailable": true, "sources": ["https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_structuralinduction_ipod.mp4"], "end": 0.0, "saveStateEnabled": false, "prioritizeHls": false, "savedVideoPosition": 0.0, "captionDataDir": null, "transcriptLanguages": {"en": "English"}, "start": 0.0, "saveStateUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@54185b6bd3c74c0f9beb6c2acb415b7d/handler/xmodule_handler/save_user_state", "speed": null, "autoAdvance": false, "completionPercentage": 0.95, "duration": 0.0, "lmsRootURL": "https://openlearninglibrary.mit.edu", "poster": null}'
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="54185b6bd3c74c0f9beb6c2acb415b7d"></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_54185b6bd3c74c0f9beb6c2acb415b7d">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_54185b6bd3c74c0f9beb6c2acb415b7d">
<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_structuralinduction_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@54185b6bd3c74c0f9beb6c2acb415b7d/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@54185b6bd3c74c0f9beb6c2acb415b7d/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@7b4c599aa7974246a7192d4fa9b36b5e">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-course-id="course-v1:OCW+6.042J+2T2019" data-runtime-class="LmsRuntime" data-request-token="374384f2e12211ef932016ffeba94eb7" data-block-type="html" data-graded="False" data-runtime-version="1" data-init="XBlockToXModuleShim" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@7b4c599aa7974246a7192d4fa9b36b5e">
<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/3c271753d6ea7662230e0d411797723e/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS16_StructuralInd.pdf" target="[object Object]">Structural Induction (PDF)</a></p>
<p><a href="/assets/courseware/v1/52ecbe32b01fe77f874e4d9e88ce36cb/asset-v1:OCW+6.042J+2T2019+type@asset+block/StructuralInduction_1.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-course-id="course-v1:OCW+6.042J+2T2019" data-runtime-class="LmsRuntime" data-request-token="374384f2e12211ef932016ffeba94eb7" data-block-type="vertical" data-graded="False" data-runtime-version="1" data-init="VerticalStudentView" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@bd33fa7626634d279e2a49f71358dac1">
<h2 class="hd hd-2 unit-title">Exercise | Structural Induction: Definition</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@html+block@6fb88833f0e34bd8a231fa45288a5b2f">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-course-id="course-v1:OCW+6.042J+2T2019" data-runtime-class="LmsRuntime" data-request-token="374384f2e12211ef932016ffeba94eb7" data-block-type="html" data-graded="False" data-runtime-version="1" data-init="XBlockToXModuleShim" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@6fb88833f0e34bd8a231fa45288a5b2f">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<p>To prove <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>P</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </math> holds for all Q#1 in recursively defined set <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>R</mi> </math>, prove:</p>
<ul>
<li><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>P</mi> <mo stretchy="false">(</mo> </math>Q#2<math xmlns="http://www.w3.org/1998/Math/MathML"> <mo stretchy="false">) </mo> </math>for each base case, <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b,</mi></math> in Q#3<math xmlns="http://www.w3.org/1998/Math/MathML"> </math><math xmlns="http://www.w3.org/1998/Math/MathML"> </math></li>
<li style="text-align: left;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>P</mi> <mo stretchy="false">(</mo> </math>Q#4<math xmlns="http://www.w3.org/1998/Math/MathML"> <mo stretchy="false">) </mo> </math>for each constructor, <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> c,</mi></math> assuming induction hypothesis <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>P</mi> <mo stretchy="false">(</mo> </math> Q#5<math xmlns="http://www.w3.org/1998/Math/MathML"> <mo stretchy="false">)</mo> </math><math xmlns="http://www.w3.org/1998/Math/MathML"> </math></li>
</ul>
<p></p>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@f8621c15e8d14a539135cde5cfb85143">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-course-id="course-v1:OCW+6.042J+2T2019" data-runtime-class="LmsRuntime" data-request-token="374384f2e12211ef932016ffeba94eb7" data-block-type="problem" data-graded="False" data-runtime-version="1" data-init="XBlockToXModuleShim" data-has-score="True" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@f8621c15e8d14a539135cde5cfb85143">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_f8621c15e8d14a539135cde5cfb85143" class="problems-wrapper" role="group"
aria-labelledby="f8621c15e8d14a539135cde5cfb85143-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@f8621c15e8d14a539135cde5cfb85143" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@f8621c15e8d14a539135cde5cfb85143/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="f8621c15e8d14a539135cde5cfb85143-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@f8621c15e8d14a539135cde5cfb85143-problem-progress" tabindex="-1">
Questions
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@f8621c15e8d14a539135cde5cfb85143-problem-progress"></div>
<div class="problem">
<div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><p>1. Which variable should replace the placeholder Q#1?</p>
<div class="inputtype option-input ">
<select name="input_f8621c15e8d14a539135cde5cfb85143_2_1" id="input_f8621c15e8d14a539135cde5cfb85143_2_1" aria-describedby="status_f8621c15e8d14a539135cde5cfb85143_2_1">
<option value="option_f8621c15e8d14a539135cde5cfb85143_2_1_dummy_default">Select an option</option>
<option value="b"> b</option>
<option value="b(x)"> b(x)</option>
<option value="c"> c</option>
<option value="c(x)"> c(x)</option>
<option value="R"> R</option>
<option value="x"> x</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_f8621c15e8d14a539135cde5cfb85143_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_f8621c15e8d14a539135cde5cfb85143_2_1"/>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><p>2. Which variable should replace the placeholder Q#2?</p>
<div class="inputtype option-input ">
<select name="input_f8621c15e8d14a539135cde5cfb85143_3_1" id="input_f8621c15e8d14a539135cde5cfb85143_3_1" aria-describedby="status_f8621c15e8d14a539135cde5cfb85143_3_1">
<option value="option_f8621c15e8d14a539135cde5cfb85143_3_1_dummy_default">Select an option</option>
<option value="b"> b</option>
<option value="b(x)"> b(x)</option>
<option value="c"> c</option>
<option value="c(x)"> c(x)</option>
<option value="R"> R</option>
<option value="x"> x</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_f8621c15e8d14a539135cde5cfb85143_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_f8621c15e8d14a539135cde5cfb85143_3_1"/>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><p>3. Which variable should replace the placeholder Q#3?</p>
<div class="inputtype option-input ">
<select name="input_f8621c15e8d14a539135cde5cfb85143_4_1" id="input_f8621c15e8d14a539135cde5cfb85143_4_1" aria-describedby="status_f8621c15e8d14a539135cde5cfb85143_4_1">
<option value="option_f8621c15e8d14a539135cde5cfb85143_4_1_dummy_default">Select an option</option>
<option value="b"> b</option>
<option value="b(x)"> b(x)</option>
<option value="c"> c</option>
<option value="c(x)"> c(x)</option>
<option value="R"> R</option>
<option value="x"> x</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_f8621c15e8d14a539135cde5cfb85143_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_f8621c15e8d14a539135cde5cfb85143_4_1"/>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 4" role="group"><p>4. Which variable should replace the placeholder Q#4?</p>
<div class="inputtype option-input ">
<select name="input_f8621c15e8d14a539135cde5cfb85143_5_1" id="input_f8621c15e8d14a539135cde5cfb85143_5_1" aria-describedby="status_f8621c15e8d14a539135cde5cfb85143_5_1">
<option value="option_f8621c15e8d14a539135cde5cfb85143_5_1_dummy_default">Select an option</option>
<option value="b"> b</option>
<option value="b(x)"> b(x)</option>
<option value="c"> c</option>
<option value="c(x)"> c(x)</option>
<option value="R"> R</option>
<option value="x"> x</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_f8621c15e8d14a539135cde5cfb85143_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_f8621c15e8d14a539135cde5cfb85143_5_1"/>
</div></div>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 5" role="group"><p>5. Which variable should replace the placeholder Q#5?</p>
<div class="inputtype option-input ">
<select name="input_f8621c15e8d14a539135cde5cfb85143_6_1" id="input_f8621c15e8d14a539135cde5cfb85143_6_1" aria-describedby="status_f8621c15e8d14a539135cde5cfb85143_6_1">
<option value="option_f8621c15e8d14a539135cde5cfb85143_6_1_dummy_default">Select an option</option>
<option value="b"> b</option>
<option value="b(x)"> b(x)</option>
<option value="c"> c</option>
<option value="c(x)"> c(x)</option>
<option value="R"> R</option>
<option value="x"> x</option>
</select>
<div class="indicator-container">
<span class="status unanswered" id="status_f8621c15e8d14a539135cde5cfb85143_6_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_f8621c15e8d14a539135cde5cfb85143_6_1"/>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Questions " />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_f8621c15e8d14a539135cde5cfb85143" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_f8621c15e8d14a539135cde5cfb85143">
<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="f8621c15e8d14a539135cde5cfb85143-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="f8621c15e8d14a539135cde5cfb85143-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="f8621c15e8d14a539135cde5cfb85143-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="f8621c15e8d14a539135cde5cfb85143-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-course-id="course-v1:OCW+6.042J+2T2019" data-runtime-class="LmsRuntime" data-request-token="374384f2e12211ef932016ffeba94eb7" data-block-type="vertical" data-graded="False" data-runtime-version="1" data-init="VerticalStudentView" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@a9d5db62bd7345f5b932707ff8aa2ba2">
<h2 class="hd hd-2 unit-title">Exercise | Counting Cases</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@problem+block@46576481f9de4deaa2c3f1304c9b7866">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-course-id="course-v1:OCW+6.042J+2T2019" data-runtime-class="LmsRuntime" data-request-token="374384f2e12211ef932016ffeba94eb7" data-block-type="problem" data-graded="False" data-runtime-version="1" data-init="XBlockToXModuleShim" data-has-score="True" data-usage-id="block-v1:OCW+6.042J+2T2019+type@problem+block@46576481f9de4deaa2c3f1304c9b7866">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_46576481f9de4deaa2c3f1304c9b7866" class="problems-wrapper" role="group"
aria-labelledby="46576481f9de4deaa2c3f1304c9b7866-problem-title"
data-problem-id="block-v1:OCW+6.042J+2T2019+type@problem+block@46576481f9de4deaa2c3f1304c9b7866" data-url="/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@problem+block@46576481f9de4deaa2c3f1304c9b7866/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="46576481f9de4deaa2c3f1304c9b7866-problem-title" aria-describedby="block-v1:OCW+6.042J+2T2019+type@problem+block@46576481f9de4deaa2c3f1304c9b7866-problem-progress" tabindex="-1">
Counting Cases
</h3>
<div class="problem-progress" id="block-v1:OCW+6.042J+2T2019+type@problem+block@46576481f9de4deaa2c3f1304c9b7866-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_46576481f9de4deaa2c3f1304c9b7866_2_1">
<fieldset aria-describedby="status_46576481f9de4deaa2c3f1304c9b7866_2_1">
<legend id="46576481f9de4deaa2c3f1304c9b7866_2_1-legend" class="response-fieldset-legend field-group-hd">If for a structural induction proof, there are 3 base cases and 4 different constructors, how many cases (i.e. specific <math xmlns="http://www.w3.org/1998/Math/MathML">
<mi>P</mi>
<mo stretchy="false">(</mo>
<mi>x</mi>
<mo stretchy="false">)</mo>
</math>'s) must be considered?</legend>
<div class="field">
<input type="radio" name="input_46576481f9de4deaa2c3f1304c9b7866_2_1" id="input_46576481f9de4deaa2c3f1304c9b7866_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="46576481f9de4deaa2c3f1304c9b7866_2_1-choice_0-label" for="input_46576481f9de4deaa2c3f1304c9b7866_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_46576481f9de4deaa2c3f1304c9b7866_2_1"> 3
</label>
</div>
<div class="field">
<input type="radio" name="input_46576481f9de4deaa2c3f1304c9b7866_2_1" id="input_46576481f9de4deaa2c3f1304c9b7866_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="46576481f9de4deaa2c3f1304c9b7866_2_1-choice_1-label" for="input_46576481f9de4deaa2c3f1304c9b7866_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_46576481f9de4deaa2c3f1304c9b7866_2_1"> 4
</label>
</div>
<div class="field">
<input type="radio" name="input_46576481f9de4deaa2c3f1304c9b7866_2_1" id="input_46576481f9de4deaa2c3f1304c9b7866_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="46576481f9de4deaa2c3f1304c9b7866_2_1-choice_2-label" for="input_46576481f9de4deaa2c3f1304c9b7866_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_46576481f9de4deaa2c3f1304c9b7866_2_1"> 7
</label>
</div>
<div class="field">
<input type="radio" name="input_46576481f9de4deaa2c3f1304c9b7866_2_1" id="input_46576481f9de4deaa2c3f1304c9b7866_2_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="46576481f9de4deaa2c3f1304c9b7866_2_1-choice_3-label" for="input_46576481f9de4deaa2c3f1304c9b7866_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_46576481f9de4deaa2c3f1304c9b7866_2_1"> 12
</label>
</div>
<div class="field">
<input type="radio" name="input_46576481f9de4deaa2c3f1304c9b7866_2_1" id="input_46576481f9de4deaa2c3f1304c9b7866_2_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="46576481f9de4deaa2c3f1304c9b7866_2_1-choice_4-label" for="input_46576481f9de4deaa2c3f1304c9b7866_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_46576481f9de4deaa2c3f1304c9b7866_2_1"> 64
</label>
</div>
<div class="field">
<input type="radio" name="input_46576481f9de4deaa2c3f1304c9b7866_2_1" id="input_46576481f9de4deaa2c3f1304c9b7866_2_1_choice_5" class="field-input input-radio" value="choice_5"/><label id="46576481f9de4deaa2c3f1304c9b7866_2_1-choice_5-label" for="input_46576481f9de4deaa2c3f1304c9b7866_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_46576481f9de4deaa2c3f1304c9b7866_2_1"> 81
</label>
</div>
<span id="answer_46576481f9de4deaa2c3f1304c9b7866_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_46576481f9de4deaa2c3f1304c9b7866_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_46576481f9de4deaa2c3f1304c9b7866_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Counting Cases" />
<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_46576481f9de4deaa2c3f1304c9b7866" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_46576481f9de4deaa2c3f1304c9b7866">
<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="46576481f9de4deaa2c3f1304c9b7866-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="46576481f9de4deaa2c3f1304c9b7866-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="46576481f9de4deaa2c3f1304c9b7866-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="46576481f9de4deaa2c3f1304c9b7866-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-course-id="course-v1:OCW+6.042J+2T2019" data-runtime-class="LmsRuntime" data-request-token="374384f2e12211ef932016ffeba94eb7" data-block-type="vertical" data-graded="False" data-runtime-version="1" data-init="VerticalStudentView" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@vertical+block@5493b236033d4f36b7825f5dfe0ebaa4">
<h2 class="hd hd-2 unit-title">Lecture Video | Recursive Functions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:OCW+6.042J+2T2019+type@video+block@0ee51ab5e5e84ffc9a3b340809643090">
<div class="xblock xblock-public_view xblock-public_view-video xmodule_display xmodule_VideoBlock" data-course-id="course-v1:OCW+6.042J+2T2019" data-runtime-class="LmsRuntime" data-request-token="374384f2e12211ef932016ffeba94eb7" data-block-type="video" data-graded="False" data-runtime-version="1" data-init="XBlockToXModuleShim" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@video+block@0ee51ab5e5e84ffc9a3b340809643090">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Video"}
</script>
<h3 class="hd hd-2">Recursive Functions</h3>
<div
id="video_0ee51ab5e5e84ffc9a3b340809643090"
class="video closed"
data-metadata='{"streams": "1.00:tOsdeaYDCMk", "autohideHtml5": false, "autoplay": false, "transcriptTranslationUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@0ee51ab5e5e84ffc9a3b340809643090/handler/transcript/translation/__lang__", "transcriptLanguage": "en", "publishCompletionUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@0ee51ab5e5e84ffc9a3b340809643090/handler/publish_completion", "transcriptAvailableTranslationsUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@0ee51ab5e5e84ffc9a3b340809643090/handler/transcript/available_translations", "completionEnabled": false, "generalSpeed": 1.0, "ytTestTimeout": 1500, "ytMetadataEndpoint": "", "ytApiUrl": "https://www.youtube.com/iframe_api", "showCaptions": "true", "recordedYoutubeIsAvailable": true, "sources": ["https://ia800207.us.archive.org/32/items/MIT6.042JS15/MIT6_042JS15_recursivefunctions_ipod.mp4"], "end": 0.0, "saveStateEnabled": false, "prioritizeHls": false, "savedVideoPosition": 0.0, "captionDataDir": null, "transcriptLanguages": {"en": "English"}, "start": 0.0, "saveStateUrl": "/courses/course-v1:OCW+6.042J+2T2019/xblock/block-v1:OCW+6.042J+2T2019+type@video+block@0ee51ab5e5e84ffc9a3b340809643090/handler/xmodule_handler/save_user_state", "speed": null, "autoAdvance": false, "completionPercentage": 0.95, "duration": 0.0, "lmsRootURL": "https://openlearninglibrary.mit.edu", "poster": null}'
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="0ee51ab5e5e84ffc9a3b340809643090"></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_0ee51ab5e5e84ffc9a3b340809643090">Downloads and transcripts</h3>
<div class="wrapper-downloads" role="region" aria-labelledby="video-download-transcripts_0ee51ab5e5e84ffc9a3b340809643090">
<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_recursivefunctions_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@0ee51ab5e5e84ffc9a3b340809643090/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@0ee51ab5e5e84ffc9a3b340809643090/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@f85656855e2b4a0c83eed4314b29d182">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-course-id="course-v1:OCW+6.042J+2T2019" data-runtime-class="LmsRuntime" data-request-token="374384f2e12211ef932016ffeba94eb7" data-block-type="html" data-graded="False" data-runtime-version="1" data-init="XBlockToXModuleShim" data-has-score="False" data-usage-id="block-v1:OCW+6.042J+2T2019+type@html+block@f85656855e2b4a0c83eed4314b29d182">
<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/9d51bcd82d5ba301201f99b7d91c3c53/asset-v1:OCW+6.042J+2T2019+type@asset+block/MIT6_042JS16_RecursiveFunc.pdf" target="[object Object]">Recursive Functions (PDF)</a></p>
<p><a href="/assets/courseware/v1/338738faa19c6f219ece286f8a0c24b9/asset-v1:OCW+6.042J+2T2019+type@asset+block/RecursiveFunctions_1.10_Lectrans.pdf" target="[object Object]">Lecture video transcript (PDF)</a></p>
</div>
</div>
</div>
</div>