{"id":276,"date":"2024-08-02T18:39:25","date_gmt":"2024-08-02T18:39:25","guid":{"rendered":"http:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/?page_id=276"},"modified":"2024-12-08T01:14:02","modified_gmt":"2024-12-08T01:14:02","slug":"sipser-10-1-10-2","status":"publish","type":"page","link":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/schedule\/sipser-10-1-10-2\/","title":{"rendered":"Sipser 10.1-10.2"},"content":{"rendered":"<p>Read Sipser \u00a710.1 and \u00a710.2<\/p>\n<ol>\n<li>Section 10.1 gives several examples of\u00a0<em>optimization problems<\/em>, along with algorithms to approximate their solutions. Give another example of an optimization problem that is undecidable &#8211; meaning an approximation algorithm might be an appropriate application.<\/li>\n<li>Describe the choice of 1\/3 in the definition of BPP, and why this choice is OK even though it seems like quite a large margin of error.<\/li>\n<li>Describe, in your own words, the difference between the classes BPP and RP.<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>Read Sipser \u00a710.1 and \u00a710.2 Section 10.1 gives several examples of\u00a0optimization problems, along with algorithms to approximate their solutions. Give another example of an optimization problem that is undecidable &#8211; meaning an approximation algorithm might be an appropriate application. Describe the choice of 1\/3 in the definition of BPP, and why this choice is OK &#8230; <a title=\"Sipser 10.1-10.2\" class=\"read-more\" href=\"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/schedule\/sipser-10-1-10-2\/\" aria-label=\"Read more about Sipser 10.1-10.2\">Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":29,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-276","page","type-page","status-publish"],"_links":{"self":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/pages\/276","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/comments?post=276"}],"version-history":[{"count":3,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/pages\/276\/revisions"}],"predecessor-version":[{"id":378,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/pages\/276\/revisions\/378"}],"up":[{"embeddable":true,"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/pages\/29"}],"wp:attachment":[{"href":"https:\/\/eikmeier.sites.grinnell.edu\/csc-341-spring-2025\/wp-json\/wp\/v2\/media?parent=276"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}