tag:blogger.com,1999:blog-3722233.post6252254780108417749..comments2023-09-30T21:44:03.907-05:00Comments on Computational Complexity: Types of questions for examsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-77447979106979151342013-09-12T22:38:48.818-05:002013-09-12T22:38:48.818-05:00I completely relate to your 7th type of question. ...I completely relate to your 7th type of question. Last semester, I encountered one on the final of my Theory of Computation class. The first question asked us to count the number of "l"'s (L's) in the string: "hello world". I was quite bummed to have spent an hour on the problem, only to learn afterwards that it was deemed "trivial" by peers. In the end, I got this problem wrong and failed the course, despite applying most of what I had learned:<br /><br />I first wondered if the generalized decision version of the problem (Given a string, a symbol, and a number, determine if #symbol <= n) was tractable or even decidable. I knew that it was not regular due to the Pumping Lemma, even when provided an ordering. Rice's theorem did not seem to obviously apply here. After trying various diagonalization arguments and failed reductions to the Halting problem, I convinced myself that the problem was likely decidable.<br /><br />The big hurdle was the abscence of a specified ordering on the input. Because of brain damage caused by a discrete math course, I cannot parse strings properly without error. I began by selecting arbitrary symbols of the input and checking for the presence of L's, individually. I was able to verify that there was at least one L present, but could not convince myself that L's found in subsequent trials were distinct from the first. I did discover at least 5 characters that were NOT L's.<br /><br />Since I had a lower bound (one L), I figured a good next step is to establish an upper bound. In a somewhat cheaty fashion, I used the knowledge that there are no more than 80, 12 pt, monospaced characters written on single line of a standard page. Since at least 5 of those are not L's, we have an upper bound of 75 L's.<br /><br />Though handicapped, I knew that the physical page layout preserved the ordering of the input. In my excitement, I folded the paper lengthwise, partitioning it into two sections. I wanted to properly sample this time, so I sought a good source of random bits. I asked the proctor to generate a random sequence of 75 ones or zeros for me. After chuckling, they audibly gave me one that consisted of all ones. Surprised, I accepted that low probability events do occur. Using this sequence, I randomly checked symbols from each section independently. Eventually, I found TWO distinct L's. This improved my lower bound to 2 L's.<br /><br />To avoid tearing, I chose not to fold it further. I requested blank paper in the hopes that I could use it to "compute" on the exam (computation is local, after all). After some involved folding and test runs, I believe I succeeded in creating a bizarre paper TM head that could parse the input for me. I used a single strip of paper that slid through the machine as a way of encoding the answer. Every time my machine found an L, I tore an extra piece off from that page. At the end of the computation, the number of torn pieces determined the number of L's.<br /><br />Time elapsed during the middle of my computation on the "hello world" string. I requested and was permitted an extra 5 minutes to finish. I rushed the process, frantically tearing pieces off my strip as I witnessed new L's. The proctor became quite upset at the sight of a student shifting around a complicated origami "sculpture" while tearing up a long strip of paper. Much to my objections and despair, the proctor violently pulled the exam and machine away. Through the shower of small bits of paper (including those from the test computations), I cried as I watched my creation get crumpled up in their hands. This very much has been the most traumatic and saddening moment in my life so far.<br /><br />I somehow managed to get a 2/100 on the exam, probably because of my lower bound. I guess I really don't have what it takes to do well in cs theory. Since the course is required for a degree, I am retaking it next semester with another instructor. I hear they prefer oral exams rather than written ones. Perhaps things will go better for me next time.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60824720048726262012013-09-05T08:23:53.059-05:002013-09-05T08:23:53.059-05:00#5- asking them to write a (possibly long) proof o...#5- asking them to write a (possibly long) proof or algorihtm so<br />that anyone can understand it. When I have done this they are<br />warned ahead of time (you will be asked one of the following<br />three questions on the exam next week...) or I make it not THAT long<br />a problem (you may assume Lemma XXX). Still hard to grade so never<br />in a big class. In short- YES there are some issues, but it can be done right.<br /><br />The only trend I have noticed is that some of the bright-but-lazy <br />students get the questions that don't require having gone to class<br />but miss those that have. They don't do well in the end.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81598104326466612662013-09-05T08:16:14.467-05:002013-09-05T08:16:14.467-05:00Point well taken- the webpage that we both saw has...Point well taken- the webpage that we both saw has something<br />CALLED `Call fo papers' (they left out the r- maybe a bad sign)<br />but all it is is a list of topics. No List of whose on the<br />committee, or where/how to submit. GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51916349068675468512013-09-05T01:18:45.380-05:002013-09-05T01:18:45.380-05:00#5 is just agony to place on an exam and not so he...#5 is just agony to place on an exam and not so helpful to students or teaching staff, much better for homework. All other questions are really helpful and they may help to give you the distributions that you are seeing. Have you ever checked if students who could do questions of type #6 and all other questions were the A's, type #4 and all other questions the B's, and so forth? Would be interesting to see, but that's what my intuition would be.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55762532819765242632013-09-05T00:39:35.678-05:002013-09-05T00:39:35.678-05:00Bill, thanks. But Googling STOC 2014 does not give...Bill, thanks. But Googling STOC 2014 does not give a call for papers for STOC 2014. It does give a one generic paragraph named "called for papers", but with no PC members, for instance. <br />For CCC 2014, the situation is much worse. There's basically nothing. <br />I guess these conferences shoot only for the regular participants from about 20 research centers in the US (and some more from other countries), and so they don't feel obliged to even publish their CFP.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-92187673913083806402013-09-04T09:00:06.062-05:002013-09-04T09:00:06.062-05:00If you google
STOC 2014 the first relelvent hit (...If you google<br /><br />STOC 2014 the first relelvent hit (the second hit when I did it)<br />goes to a webpage that has Topics/Call for papers- in paragraph<br />form rather than list form so that may have confused you<br />when you did the Google Search.<br /><br />The deadline is Nov 30. I do not know how much lead time they<br />usually give.<br /><br />CCC I have not been able to find. Again, I do not recall what<br />the usual lead time is so I do not know if this is unusual.<br /><br />BACK to my TOPIC- if you give a HW assignment where the answer<br />can be found by Google, is it worth giving? YES if the point is to<br />have them LEARN the thing they Google. NO if you are trying to test<br />cleverness. The line is not all that clear.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2489360080777962082013-09-04T05:10:47.690-05:002013-09-04T05:10:47.690-05:00Off topic: Why on earth weren't the call for p...Off topic: Why on earth weren't the call for papers for both STOC 2014 and CCC 2014 published yet? Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37211381237064636332013-09-03T15:46:00.444-05:002013-09-03T15:46:00.444-05:00A true/false math question where they then have to...A true/false math question where they then have to prove their answer. A student who picks the wrong answer can figure that out during the proof stage and then correct their answer. A student who picks the wrong answer and proves it has proven they really don't have a clue.Anonymousnoreply@blogger.com