tag:blogger.com,1999:blog-3722233.post7376087648863245436..comments2023-12-02T04:32:02.323-06:00Comments on Computational Complexity: Why is there no all-encompassing term for a course on Models of Computation?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-3722233.post-29839848505473184732019-12-17T07:47:05.440-06:002019-12-17T07:47:05.440-06:00The algorithm was `me copying a comment from the l...The algorithm was `me copying a comment from the last post' which is, as evidenced from your correction and the last comment, not a prefect algorithm. I have fixed it. GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90893267788240053102019-12-16T20:11:01.569-06:002019-12-16T20:11:01.569-06:00Was a your spell-checker that turned Calculabilité...Was a your spell-checker that turned <i>Calculabilité</i> (perfectly good French) into <i>Calulabitite</i> (huh?)? What algorithm was it using?Peter Shorhttps://www.blogger.com/profile/13823970640202949073noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17681492150962322562019-12-15T19:41:51.521-06:002019-12-15T19:41:51.521-06:00Bill, I doubt that Informatak is a term. please ch...Bill, I doubt that Informatak is a term. please check and get back to me. did you mean informatik ? If so, make correction.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54821138671087431342019-12-13T20:49:51.073-06:002019-12-13T20:49:51.073-06:00My coworker texted me later to mention that the tw...My coworker texted me later to mention that the two Discrete Structures courses are commonly referred to by the student body as "Little Discrete" and "Big Discrete".Aaron Rotenberghttps://www.blogger.com/profile/04025704694247832990noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86587515676356129912019-12-13T14:48:37.924-06:002019-12-13T14:48:37.924-06:00Just posed this question to a coworker who went to...Just posed this question to a coworker who went to UCF. Apparently these topics are spread out among the "Discrete Structures" (discrete math) ugrad courses there, with most of it concentrated in Discrete Structures II. That's about as informative a course title as "Informatik III", if not less so.Aaron Rotenberghttps://www.blogger.com/profile/04025704694247832990noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50961759515898562092019-12-13T14:41:34.154-06:002019-12-13T14:41:34.154-06:00I would have absolutely taken that course as an el...I would have absolutely taken that course as an elective if it existed.Aaron Rotenberghttps://www.blogger.com/profile/04025704694247832990noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52567115578333129682019-12-13T13:06:44.649-06:002019-12-13T13:06:44.649-06:00Good Point.
Actually `Great ideas' sounds like...Good Point.<br />Actually `Great ideas' sounds like a Great course, but is to wide a name to be a good universal name for a DFA and/or CFG and/or... course I am talking about.GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44217102287406875742019-12-13T13:04:08.079-06:002019-12-13T13:04:08.079-06:00On a related note: the ACT of SIGACT *used* to sta...On a related note: the ACT of SIGACT *used* to stand for "Automata and Computability Theory" and now stands for "Algorithms and Computation Theory". <br /><br />The different titles are really a function of the starting point and content for the course (as well as inertia) not some lack of consensus on what to call the same material.<br /><br />Some of the big differences:<br /><br />- Does the course have a large focus on finite state machines/grammars/PDAs, along with computability?<br /> <br /> If so, you will tend to have the "formal languages/automata" or MAYBE "theory of computation", but maybe only if the course extends into complexity.<br /><br />- Does the course have a significant focus on computability?<br /><br />If so, "Theory of Computing/Computation Theory/Theory of Computation" seem appropriate.<br /><br />- Course titles like "Great Ideas in TCS" and "Intro to Theoretical Computer Science" suggest that the material covers substantial algorithmic content as well. The idea is fine, but I think it is another apples and oranges comparison.<br /><br />Anonymoushttps://www.blogger.com/profile/02744495309363882940noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30115651151546963262019-12-12T20:44:25.425-06:002019-12-12T20:44:25.425-06:00Why is “Great Ideas in Theoretical Computer Scienc...Why is “Great Ideas in Theoretical Computer Science?” too narrow?<br /><br />At Harvard I changed the name of the course from “Introduction to the theory of computing” to “introduction to theoretical computer science” because I thought the latter term is broader and hints at topics such as cryptography, randomness in computation, and quantum computing that intersect with computational complexity but are not a subset of it.Boaz Barakhttps://www.blogger.com/profile/01023091208435407661noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18984491894166323602019-12-12T18:47:48.496-06:002019-12-12T18:47:48.496-06:00The problem with cryptography is that there are at...The problem with cryptography is that there are at least two cryptographies.<br /><br />One is about one-way functions and random number generators; the other one is about RSA and CBC cyphers.Anonymoushttps://www.blogger.com/profile/11067659793463483481noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84163139880075205632019-12-12T18:45:20.397-06:002019-12-12T18:45:20.397-06:00To me, Models of Computation sound more like what ...To me, Models of Computation sound more like what "Structure and Interpretation of Computer Programs" is about. I.e. lazy vs eager evaluation, prolog, language design, circuit design, etc...Anonymoushttps://www.blogger.com/profile/11067659793463483481noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14655770024182351572019-12-12T15:27:13.198-06:002019-12-12T15:27:13.198-06:00Models of Computation sounds like you spend a whol...Models of Computation sounds like you spend a whole semester talking about stuff like Wang tiles and membrane computing.Andreihttps://www.blogger.com/profile/02656015432967049103noreply@blogger.com