{"id":29,"date":"2022-01-02T20:22:05","date_gmt":"2022-01-02T20:22:05","guid":{"rendered":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2022\/?page_id=29"},"modified":"2022-01-06T19:18:36","modified_gmt":"2022-01-06T19:18:36","slug":"schedule","status":"publish","type":"page","link":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2022\/schedule\/","title":{"rendered":"Schedule"},"content":{"rendered":"

If links do not work in the table below, it likely means that they aren’t set to be released in Gradescope yet. If you believe something should be already released, shoot me an email.<\/p>\n\n\n\n\n\t\n\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t\n\t
Date<\/th>Topics\/Activities<\/th>Readings and Deadlines<\/th>Lab<\/th>\n<\/tr>\n<\/thead>\n
T Jan 25<\/td>Introduction to the Course, Review of Proofs<\/td>To-do before the first day of class<\/a><\/td> 1\/25<\/a><\/td>\n<\/tr>\n
Th Jan 27<\/td>Mathematical Literacy<\/td>Reading: Sipser: Chapter 0<\/a>
\nReleased today: Problem Set 1<\/a><\/td>		1\/27<\/a><\/td>\n<\/tr>\n
Sat Jan 29<\/td><\/td>Due: Labs from 1\/25<\/a> and 1\/27<\/a><\/td><\/td>\n<\/tr>\n
T Feb 1<\/td>Finite Automata<\/td>Reading: Sipser: Section 1.1<\/a><\/td>2\/1<\/a><\/td>\n<\/tr>\n
Th Feb 3<\/td>Nondeterminism<\/td>Sipser: Section 1.2<\/a>
\nYou can just skim the section on Equivalence of NFAs and DFAs. <\/td>		2\/3<\/a><\/td>\n<\/tr>\n
Sat Feb 5<\/td><\/td>Labs from 2\/1<\/a> and 2\/3<\/a><\/td><\/td>\n<\/tr>\n
T Feb 8<\/td>Regular Expressions<\/td>Reading: Sipser Section 1.3<\/a>
\nDue: Problem Set 1<\/a>
\nReleased today: Problem Set 2<\/a><\/td>		2\/8<\/a><\/td>\n<\/tr>\n
Th Feb 10<\/td>Regular Models<\/td>Reading: Decision Procedures<\/a> and questions<\/a><\/td>2\/10<\/a><\/td>\n<\/tr>\n
Sat Feb 12<\/td><\/td>Labs from 2\/8<\/a> and 2\/10<\/a><\/td><\/td>\n<\/tr>\n
T Feb 15<\/td>Irregularity<\/td>Reading: Sipser: Section 1.4<\/a>
\nDue: Problem Set 2<\/a><\/s><\/td>		2\/15<\/a><\/td>\n<\/tr>\n
Th Feb 17<\/td>Context-Free Grammars<\/td>Reading: Sipser: Section 2.1<\/a>
\nReleased today: Problem Set 3<\/a>
\nDue: Problem Set 2<\/a><\/td>		2\/17<\/a><\/td>\n<\/tr>\n
Sat Feb 19<\/td><\/td>Labs from 2\/15<\/a> and 2\/17<\/a><\/td><\/td>\n<\/tr>\n
T Feb 22<\/td>Turing Machines<\/td>Reading: Sipser: 3.1<\/a><\/td>2\/22<\/a><\/td>\n<\/tr>\n
Th Feb 24<\/td>Variants of Turing Machines<\/td>Reading: Sipser 3.2<\/a>
\nQuiz opens today in Gradescope<\/td>		2\/24<\/a><\/td>\n<\/tr>\n
Sat Feb 26<\/td><\/td>Labs from 2\/22<\/a> and 2\/24<\/a><\/td><\/td>\n<\/tr>\n
T Mar 1<\/td>No Class: Working Differently Day<\/td>Reading: Sipser 3.3<\/a>
\nDue: Problem Set 3<\/a><\/td>		<\/td>\n<\/tr>\n
Th Mar 3<\/td>Time Complexity<\/td>Reading: Sipser 7.1-7.2<\/a>
\nReleased today: Problem Set 4<\/a><\/td>		3\/3<\/a><\/td>\n<\/tr>\n
Sat Mar 5<\/td><\/td>Lab from 3\/3<\/a><\/td><\/td>\n<\/tr>\n
T Mar 8<\/td>NP-completeness<\/td>Reading: Sipser 7.3 through page 304<\/a><\/td>3\/8<\/a><\/td>\n<\/tr>\n
Th Mar 10<\/td>The Cook-Levine Theorem<\/td>Reading: Sipser pg 304-311<\/a><\/td>3\/10<\/a><\/td>\n<\/tr>\n
Sat Mar 12<\/td><\/td>Labs from 3\/8<\/a> and 3\/10<\/a><\/td><\/td>\n<\/tr>\n
T Mar 15<\/td>More NP-completeness<\/td>Reading: Sipser 7.5<\/a>
\nDue today: Problem Set 4<\/a><\/td>		3\/15<\/a><\/td>\n<\/tr>\n
Th Mar 17<\/td>Savitch's Theorem<\/td>Reading: Sipser 8.1-8.2<\/a><\/td>3\/17<\/a><\/td>\n<\/tr>\n
Sat Mar 19<\/td><\/td>Labs from 3\/15<\/a> and 3\/17<\/a><\/td><\/td>\n<\/tr>\n
3\/22 - 3\/31<\/td>No Class: Spring Break<\/td>Problem Set 5<\/a> posted<\/td><\/td>\n<\/tr>\n
T April 5<\/td>PSPACE-completeness<\/td>Sipser 8.3<\/a><\/td>4\/5<\/a><\/td>\n<\/tr>\n
Th April 7<\/td>Catch-up day<\/td>No reading today!
\nQuiz opens today<\/td>		4\/7<\/a><\/td>\n<\/tr>\n
Sat April 9<\/td><\/td>Labs from 4\/5<\/a> and 4\/7<\/a><\/td><\/td>\n<\/tr>\n
T April 12<\/td>L and NL<\/td>Sipser 8.4-8.6<\/a>
\nProblem Set 5<\/a> due
\nProblem Set 6 posted<\/s><\/td>		4\/12<\/a><\/td>\n<\/tr>\n
Th April 14<\/td>Intractability<\/td>Sipser 9.1<\/a><\/td>4\/14<\/a><\/td>\n<\/tr>\n
Sat April 16<\/td><\/td>Labs from 4\/12<\/a> and 4\/14<\/a><\/td><\/td>\n<\/tr>\n
T April 19<\/td>Decidability<\/td>Sipser 4.1<\/a>
\nProblem Set 6 due<\/s><\/td>		4\/19<\/a><\/td>\n<\/tr>\n
Th April 21<\/td>Undecidability<\/td>Sipser 4.2<\/a>
\nProblem Set 6 released today<\/td>		4\/21<\/a><\/td>\n<\/tr>\n
Sat April 23<\/td><\/td>Labs from 4\/19<\/a> and 4\/21<\/a><\/td><\/td>\n<\/tr>\n
T April 26<\/td>Reducibility<\/td>Sipser 5.1 and 5.3<\/a>
\nAfter reading Sipser, review this overview<\/a> on the proof strategies from the reading.
\nProblem Set 7 due<\/s><\/td>		4\/26<\/a><\/td>\n<\/tr>\n
Th April 28<\/td>A simple, undecidable problem<\/td>Sipser 5.2<\/a><\/td>4\/28<\/a><\/td>\n<\/tr>\n
Sat April 30<\/td><\/td>Labs from 4\/26<\/a> and 4\/28<\/a><\/td><\/td>\n<\/tr>\n
T May 3<\/td>Rice's Theorem<\/td>Reading<\/a>, and link to questions<\/a>
\nProblem Set 6 due
\nProblem Set 7 released today<\/td>		5\/3<\/a><\/td>\n<\/tr>\n
Th May 5<\/td>The Recursion Theorem<\/td>Sipser 6.1<\/a>
\nQuiz opens today<\/td>		<\/td>\n<\/tr>\n
Sat May 7<\/td><\/td>Labs from 5\/3<\/a> and 5\/5<\/td><\/td>\n<\/tr>\n
T May 10<\/td>Approximation Algorithms<\/td>Sipser 10.1<\/a>
\nProblem Set 8 due<\/s>
\nProblem Set 7<\/a> due<\/td>		<\/td>\n<\/tr>\n
Th May 12<\/td>Wrap-up, course evaluations<\/td>No reading today!
\n<\/td>		<\/td>\n<\/tr>\n
Sat May 13<\/td><\/td>Labs from 5\/10 and 5\/12<\/td><\/td>\n<\/tr>\n
May 16<\/td>Exam Week<\/td>Quiz Make-ups (optional)<\/td><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n\n","protected":false},"excerpt":{"rendered":"

If links do not work in the table below, it likely means that they aren’t set to be released in Gradescope yet. If you believe something should be already released, shoot me an email.<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"elementor_header_footer","meta":{"footnotes":""},"class_list":["post-29","page","type-page","status-publish"],"_links":{"self":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2022\/wp-json\/wp\/v2\/pages\/29","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2022\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2022\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2022\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2022\/wp-json\/wp\/v2\/comments?post=29"}],"version-history":[{"count":4,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2022\/wp-json\/wp\/v2\/pages\/29\/revisions"}],"predecessor-version":[{"id":74,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2022\/wp-json\/wp\/v2\/pages\/29\/revisions\/74"}],"wp:attachment":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2022\/wp-json\/wp\/v2\/media?parent=29"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}