{"id":308,"date":"2008-02-13T20:26:27","date_gmt":"2008-02-14T00:26:27","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=308"},"modified":"2008-02-13T20:26:27","modified_gmt":"2008-02-14T00:26:27","slug":"great-ideas-in-theoretical-computer-science-lecture-1","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=308","title":{"rendered":"Great Ideas In Theoretical Computer Science Lecture 1"},"content":{"rendered":"<p>For those who&#8217;ve stopped following the Democritus series, there&#8217;s another train leaving the station today: the <a href=\"https:\/\/stellar.mit.edu\/S\/course\/6\/sp08\/6.080\/courseMaterial\/topics\/topic1\/lectureNotes\/lec1\/lec1.pdf\">first lecture<\/a> of my <a href=\"http:\/\/stellar.mit.edu\/S\/course\/6\/sp08\/6.080\/index.html\">new undergraduate course<\/a> (&#8220;Great Ideas In Theoretical Computer Science&#8221;) is now available.<\/p>\n<p>After whetting the appetite by describing how theoretical computer science has finally let humankind achieve one of its noblest aspirations (playing roulette over the Internet), the lecture then goes back to antiquity, and covers the hottest results in the computing world circa 300BC: Euclid&#8217;s GCD algorithm and the &#8220;straightedge-and-compass&#8221; model of computation.<\/p>\n<p>(One word of warning: the lecture notes were written by my teaching assistant, Yinmeng Zhang, and do not faithfully reflect what I said in class. They&#8217;re much <em>better<\/em> than what I said in class.   She even had the gall to improve my jokes.)<\/p>\n<p>To preempt the inevitable questions, two remarks about the course&#8217;s title:<\/p>\n<ol>\n<li>I considered calling it just &#8220;Great Ideas In Computer Science,&#8221; but then I realized it would have to be a week longer.  (Har har, just kidding!  Cue cymbals.)<\/li>\n<li>Any relation to the <a href=\"http:\/\/www.cs.cmu.edu\/~15251\/\">famous CMU course<\/a> designed by Steven Rudich (&#8220;Great <em>Theoretical Ideas<\/em> In Computer Science&#8221;) is obviously a coincidence.  The philosophies behind the two courses are every bit as different as their names.<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>For those who&#8217;ve stopped following the Democritus series, there&#8217;s another train leaving the station today: the first lecture of my new undergraduate course (&#8220;Great Ideas In Theoretical Computer Science&#8221;) is now available. After whetting the appetite by describing how theoretical computer science has finally let humankind achieve one of its noblest aspirations (playing roulette over [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_seo_schema_type":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"{title}\n\n{excerpt}\n\n{url}","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false,"jetpack_post_was_ever_published":false},"categories":[5,27],"tags":[],"class_list":["post-308","post","type-post","status-publish","format-standard","hentry","category-complexity","category-gitcs"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/308","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=308"}],"version-history":[{"count":0,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/308\/revisions"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=308"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=308"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=308"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}