{"id":393,"date":"2018-12-23T10:56:12","date_gmt":"2018-12-23T18:56:12","guid":{"rendered":"https:\/\/blogs.ubc.ca\/organizingchaos\/?p=393"},"modified":"2018-12-23T10:56:12","modified_gmt":"2018-12-23T18:56:12","slug":"course-review-cpsc-421","status":"publish","type":"post","link":"https:\/\/blogs.ubc.ca\/organizingchaos\/2018\/12\/23\/course-review-cpsc-421\/","title":{"rendered":"Course Review: CPSC 421"},"content":{"rendered":"

Introduction to Theory of Computing
\n<\/b><\/span><\/p>\n

“Let me start off by telling you a fact without enough background to prove the fact”<\/em><\/p>\n

Text:\u00a0<\/strong>Introduction to the Theory of Computation by Michael Sipser<\/p>\n

Prof:<\/strong>\u00a0 Dr. Nick Harvey<\/p>\n

Dr Nick Harvey is a very clear professor.\u00a0He makes effective use of slides and slowly explains complex topics, making his lectures both interesting and easy to follow. For example, his explanation of the diagonalization argument was much clearer than any of the presentations on the same topic I have received in math classes. He also has a peculiar sense of humour and is a big soccer fan, so the class is interspersed with entertaining distractions.<\/p>\n

\n

Difficulty<\/b><\/p>\n

The material starts with fairly simple with a bit of review\u00a0from CPSC 121. It picks up a bit when you start performing reductions between problems from various complexity classes though there is a bit of recap from CPSC 320. The first midterm was straightforward, however, given its short length it was possible to not to do as well if one tripped on only\u00a0one or two questions. The final was a bit harder, however, the previous exam was good preparation.\u00a0 The homework included some questions that could be genuinely hard to understand. However, he gave generous hints as the deadline approached, and they were the type of questions that once you understood what the question was asking, the proof was often one of the first few obvious approaches that you would think of. Given that he dropped the lowest couple of homework, it’s no surprise that the overall average in the course was 80.<\/p>\n

Key Concepts<\/strong><\/p>\n

Finite Automata and Regular Languages<\/p>\n

Turing Machines<\/p>\n

Non-determinism<\/p>\n

Time complexity classes<\/p>\n

Mapping Reductions<\/p>\n

Probabilistic\u00a0Turing Machines<\/p>\n

Communication Complexity and Fooling sets<\/p>\n

Hard Concepts<\/strong><\/p>\n

Context Free Languages: Can be hard sometimes to come up with CFG or PDA for a given context-free\u00a0language<\/p>\n

Probabilistic\u00a0Turing Machines: Give rise to quite convoluted complexity classes.<\/p>\n

NP-Hard\u00a0reductions: Might require a bit of imagination\u00a0to come up with the reductions, at times.<\/p>\n

Fooling Sets and Covers: One can sometimes get fooled by these, make sure one recalls the definition of rectangles and what exactly needs to hold for a fooling set.<\/p>\n

 <\/p>\n

Conclusion<\/strong><\/p>\n

Fun course. Dr Nick Harvey can make the course appear deceptively simple at times, but you actually learned a lot of quite complex material.<\/p>\n","protected":false},"excerpt":{"rendered":"

Introduction to Theory of Computing “Let me start off by telling you a fact without enough background to prove the fact” Text:\u00a0Introduction to the Theory of Computation by Michael Sipser Prof:\u00a0 Dr. Nick Harvey Dr Nick Harvey is a very clear professor.\u00a0He makes effective use of slides and slowly explains complex topics, making his lectures […]<\/p>\n","protected":false},"author":28516,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[281864],"tags":[950,1171242,1171248,3957445,3957446,1171247,1171243,1171244,1171245,37],"class_list":["post-393","post","type-post","status-publish","format-standard","hentry","category-course-reviews","tag-cpsc","tag-cpsc-421","tag-cpsc-501","tag-cpsc421","tag-cpsc501","tag-cs","tag-nick-harvey","tag-theory-of-computation","tag-theory-of-computing","tag-ubc"],"_links":{"self":[{"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/posts\/393","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/users\/28516"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/comments?post=393"}],"version-history":[{"count":1,"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/posts\/393\/revisions"}],"predecessor-version":[{"id":394,"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/posts\/393\/revisions\/394"}],"wp:attachment":[{"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/media?parent=393"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/categories?post=393"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ubc.ca\/organizingchaos\/wp-json\/wp\/v2\/tags?post=393"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}