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

This calendar contains the most up-to-date information about deadlines. Check back for changes.<\/p>\n

Submit everything in Gradescope. If you miss class, Labs can be found in Gradescope and should be submitted individually. Problem Sets can be found in Gradescope as well.<\/p>\n

Last updated: 8\/2\/2024<\/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\n\t\n\t
Date<\/th>Topics\/Activities<\/th>Readings and Deadlines<\/th>\n<\/tr>\n<\/thead>\n
Th Aug 29<\/td>Introduction to the Course, Review of Proofs<\/td>To-do: before the first day of class<\/a><\/td>\n<\/tr>\n
Sun Sept 1<\/td><\/td>Due<\/strong>: Lab from 8\/29<\/td>\n<\/tr>\n
Tu Sept 3<\/td>Mathematical Literacy<\/td>Reading: Sipser Chapter 0<\/a><\/td>\n<\/tr>\n
Th Sept 5<\/td>Finite Automata<\/td>Reading: Sipser §1.1<\/a>
\nReleased today: Problem Set 1<\/td>\n<\/tr>\n
Sun Sept 8<\/td><\/td>Due<\/strong>: Labs from 9\/3 and 9\/5<\/td>\n<\/tr>\n
Tu Sept 10<\/td>Nondeterminism<\/td>Reading: Sipser §1.2<\/a><\/td>\n<\/tr>\n
Th Sept 12<\/td>Regular Expressions<\/td>Reading: Sipser §1.3<\/a>
\nDue<\/strong>: Problem Set 1
\nReleased today: Problem Set 2<\/td>\n<\/tr>\n
Sun Sept 15<\/td><\/td>Due<\/strong>: Labs from 9\/10 and 9\/12<\/td>\n<\/tr>\n
Tu Sept 17<\/td>Regular Models<\/td>Reading: Decision Procedures<\/a><\/td>\n<\/tr>\n
Th Sept 19<\/td>Irregularity<\/td>Reading: Sipser §1.4<\/a>
\nDue:<\/strong> Problem Set 2
\nReleased today: Problem Set 3<\/td>\n<\/tr>\n
Sun Sept 22<\/td><\/td>Due<\/strong>: Labs from 9\/17 and 9\/19<\/td>\n<\/tr>\n
Tu Sept 24<\/td>Context-Free Grammars<\/td>Reading: Sipser §2.1<\/a><\/td>\n<\/tr>\n
Th Sept 26<\/td>Turing Machines<\/td>Reading: Sipser §3.1<\/a>
\nDue<\/strong>: Problem Set 3
\nReleased today: Problem Set 4<\/td>\n<\/tr>\n
Sun Sept 29<\/td><\/td>Due<\/strong>: Labs from 9\/24 and 9\/26<\/td>\n<\/tr>\n
Tu Oct 1<\/td>Variants of Turing Machines<\/td>Reading: Sipser §3.2<\/a><\/td>\n<\/tr>\n
Th Oct 3<\/td>Time Complexity<\/td>Reading: Sipser §7.1 and §7.2<\/a>
\nDue<\/strong>: Problem Set 4<\/td>\n<\/tr>\n
Sun October 6<\/td><\/td>Due<\/strong>: Labs from 10\/1 and 10\/3<\/td>\n<\/tr>\n
Tu Oct 8<\/td>Exam 1<\/td><\/td>\n<\/tr>\n
Th Oct 10<\/td>NP-completeness<\/td>Reading: Sipser §7.3 through page 304<\/a>
\nReleased today: Problem Set 5<\/td>\n<\/tr>\n
Sun Oct 13<\/td><\/td>Due<\/strong>: Lab from 10\/10<\/td>\n<\/tr>\n
Tu Oct 15<\/td>The Cook-Levine Theorem<\/td>Reading: Sipser pg 304-311<\/a><\/td>\n<\/tr>\n
Th Oct 17<\/td>More NP-completeness<\/td>Reading: Sipser §7.5<\/a>
\nDue<\/strong>: Problem Set 5<\/td>\n<\/tr>\n
Sun Oct 20<\/td><\/td>Due<\/strong>: Labs from 10\/15 and 10\/17<\/td>\n<\/tr>\n
10\/21 - 10\/25<\/td>No Class: Fall Break<\/td><\/td>\n<\/tr>\n
Tu Oct 29<\/td>Savitch's Theorem<\/td>Reading: Sipser §8.1 and §8.2<\/a><\/td>\n<\/tr>\n
Th Oct 31<\/td>PSPACE-completeness<\/td>Reading: Sipser §8.3<\/a>
\nReleased today: Problem Set 6
\n<\/td>\n<\/tr>\n
Sun Nov 3<\/td><\/td>Due<\/strong>: Labs from 10\/29 and 10\/31<\/td>\n<\/tr>\n
Tu Nov 5<\/td>L and NL<\/td>Reading: Sipser §8.4 - §8.6<\/a><\/td>\n<\/tr>\n
Th Nov 7<\/td>Intractability<\/td>Reading: Sipser §9.1 and §9.2<\/a>
\n
\nDue<\/strong>: Problem Set 6<\/td>\n<\/tr>\n
Sun Nov 10<\/td><\/td>Due<\/strong>: Labs from 11\/5 and 11\/7<\/td>\n<\/tr>\n
Tu Nov 12<\/td>Exam 2<\/td><\/td>\n<\/tr>\n
Th Nov 14<\/td>Decidability<\/td>Reading: Sipser §4.1<\/a>
\nReleased today: Problem Set 7<\/s><\/td>\n<\/tr>\n
Sun Nov 17<\/td><\/td>Due<\/strong>: Lab from 11\/14<\/td>\n<\/tr>\n
Tu Nov 19<\/td>Undecidability<\/td>Reading: Sipser §4.2<\/a><\/td>\n<\/tr>\n
Th Nov 21<\/td>Reducibility<\/td>Reading: Sipser §5.1 and §5.3<\/a>
\n
\nDue<\/strong>: Problem Set 7<\/s>
\nReleased today: Problem Set 7
\n<\/td>\n<\/tr>\n
Sun Nov 24<\/td><\/td>Due<\/strong>: Labs from 11\/19 and 11\/21<\/td>\n<\/tr>\n
Tu Nov 26<\/td>A simple, undecidable problem<\/td>Reading: Sipser §5.2<\/a><\/td>\n<\/tr>\n
Th Nov 28<\/td>No Class, Thanksgiving<\/td><\/td>\n<\/tr>\n
Sun Dec 1<\/td><\/td>Due<\/strong>: Lab from 11\/26<\/td>\n<\/tr>\n
T Dec 3<\/td>Rice's Theorem<\/td>Reading: Rice\u2019s Theorem<\/a><\/td>\n<\/tr>\n
Th Dec 5<\/td>The Recursion Theorem<\/td>Reading: Sipser §6.1 and §6.2<\/a>
\n
\nDue<\/strong>: Problem Set 7
\nReleased today: Problem Set 8<\/td>\n<\/tr>\n
Sun Dec 8<\/td><\/td>Due<\/strong>: Labs from 12\/3 and 12\/5<\/td>\n<\/tr>\n
T Dec 10<\/td>Approximation Algorithms<\/td>Reading: Sipser §10.1 and §10.2<\/a><\/td>\n<\/tr>\n
Th Dec 12<\/td>Wrap-up, course evaluations<\/td>No reading today!
\nDue:<\/strong> Problem Set 8<\/td>\n<\/tr>\n
Sun Dec 15<\/td><\/td>Due<\/strong>: Labs from 12\/10 and 12\/12<\/td>\n<\/tr>\n
12\/17 - 12\/20<\/td>Exam 3<\/td><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n\n","protected":false},"excerpt":{"rendered":"

This calendar contains the most up-to-date information about deadlines. Check back for changes. Submit everything in Gradescope. If you miss class, Labs can be found in Gradescope and should be submitted individually. Problem Sets can be found in Gradescope as well. Last updated: 8\/2\/2024<\/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-fall-2024\/wp-json\/wp\/v2\/pages\/29","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/comments?post=29"}],"version-history":[{"count":7,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/29\/revisions"}],"predecessor-version":[{"id":316,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/pages\/29\/revisions\/316"}],"wp:attachment":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-fall-2024\/wp-json\/wp\/v2\/media?parent=29"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}