tag:blogger.com,1999:blog-3722233.post7316388347146195773..comments2023-09-27T08:58:55.256-05:00Comments on Computational Complexity: What is a simple function?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger19125tag:blogger.com,1999:blog-3722233.post-42219368838566831652011-08-19T05:44:01.601-05:002011-08-19T05:44:01.601-05:00Martin Thoma,
last line should probably read 5+x^2...Martin Thoma,<br />last line should probably read 5+x^2 instead of 5+2^xAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22507504823442850592011-08-14T11:17:08.473-05:002011-08-14T11:17:08.473-05:00The word verification for the previous post was &q...The word verification for the previous post was "musses".Jim Blairnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17754504470644102172011-08-14T11:14:47.632-05:002011-08-14T11:14:47.632-05:00Is there a way to define the notion of a "sim...Is there a way to define the notion of a "simple function" without using the notion of a function in the definition either explicitly (indicator functions) or implicitly (sets)?Jim Blairnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88690624643758266632011-08-10T19:05:17.642-05:002011-08-10T19:05:17.642-05:00I don't think this kind of question is bad, or...I don't think this kind of question is bad, or misleading, or anything of the sort. I remember being fascinated by this sort of thing in high school. I wish more students were confronted with this kind of question there. But better in sophomore year than never. Of course it's true that there is never a unique answer. And that in itself is something that students at that level can easily understand, and --- even more -- learn to appreciate. And in any case, there are are two things this kind of question leads to:<br /><br />a) Kolmogorov complexity --- what's the "least complicated" way of describing the sequence? OK, I'm mainly kidding here. This is way too sophisticated for students at this level to get a good grasp on. But the question can be posed, at any rate, and I'm sure many of them might at least understand that there *is* a question there.<br /><br />b) It does, as you have intended, lead directly to the use of mathematical induction. That's good in itself.<br /><br />I have found, by the way, that many students believe that mathematical induction consists in proving the correctness of formulas. That I suppose is a problem, not so much with this kind of question, but with the fact that it may be the *only* way in which mathematical induction is presented. So many elementary graph-theoretical properties are inductive in nature --- and they're important in even reasonably low-level computer science -- that students need to be exposed to them as early as possible. But I think it's undoubtedly true that graphs for some reason seem to be more sophisticated than the natural numbers for most students -- at least, until they find out how unintuitive and terminally complex infinite sets like the natural numbers really are.Carl Offnerhttp://www.cs.umb.edu/~offnernoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21872007302618189232011-08-10T12:32:12.054-05:002011-08-10T12:32:12.054-05:00The meta-question is: what exactly is this questio...The meta-question is: what exactly is this question trying to teach them? (Or, if you prefer, what is it trying to demonstrate that they have learned?) Random guessing? Brute-force search through some canonical list of "simple" functions? Web searching for the answer?<br /><br />You said that your goal was to teach them how to prove (using induction) that some given recurrence has some given closed form. So why not just give them a question like that?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27451494717584759112011-08-08T16:42:13.506-05:002011-08-08T16:42:13.506-05:00Bad type of question, in my opinion. The one rede...Bad type of question, in my opinion. The one redeeming quality of math (as non-mathematicians see it) is its precision and exactness and unambiguity. That's completely missing in these questions. For the purpose of teaching them pattern-finding, it'd be better to teach them how to use the OEIS.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18519255855491543002011-08-08T16:10:03.874-05:002011-08-08T16:10:03.874-05:00I've long said … in mathematics, simple and n...I've long said … in mathematics, simple and normal things aren't.stuhttps://www.blogger.com/profile/05190631846507740664noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82254479861299027032011-08-08T13:35:32.936-05:002011-08-08T13:35:32.936-05:00In this context, I ask students to find a "cl...In this context, I ask students to find a "closed-form expression" which is exactly that, a function without summation or recurrences but at least they have seen that before and have some methods to guide them. I agree that's a question of terminology. That will make a great entry in my glossary puzzle for Discrete Math!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72358091179217022011-08-08T12:49:39.941-05:002011-08-08T12:49:39.941-05:00I hate questions like this.
A(n) = [10, -17, 24, ...I hate questions like this.<br /><br />A(n) = [10, -17, 24, -31, 38, -45, 52][n mod 7]<br /><br />B(n) = [-1, 1, 5, 13, 29, 61, 125][n mod 7]<br /><br />C(n) = [6, 9, 14, 21, 30, 41, 54][n mod 7]<br /><br />Yes, I teach students to solve recurrences, too. But I also teach them that's it's dangerous to generalize from small examples; every "What's next in this sequence?" question has an infinite number of answers.<br /><br />Recurrences give strong hints about their solutions; they certainly contain more information that their first few initial values. (Look at f(n) = 2f(n-1). Do you know of any sequences of integers that double in every iteration BY DEFINITION?)<br /><br />Moreover, most simple recurrences (meaning almost all recurrences that show up in an undergraduate CS curriculum) can be solved directly (at least up to constant factors) using fairly simple techniques. Yeah, it's important to fall back on guessing when you have no alternative, but that circumstance is really quite rare.JeffEhttps://www.blogger.com/profile/17633745186684887140noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56886094706871466702011-08-08T11:40:47.064-05:002011-08-08T11:40:47.064-05:00I would say simple functions are those which can b...I would say simple functions are those which can be understood by a pupil in 10th grade in Bavaria, Germany (sin(x), cos(x), tan(x), a^x, log_n(x), abs(x), all polynomial functions, recursive functions, and any possible chaining of these (in R)). So all n-ary functions with n >= 2 are not simple, ceil(x), floor(x), the ackermann function, ...<br /><br />In this context I thought you might want to prohibit the excessive use of defining the function (sorry for my bad English, I think I'll make an example):<br /><br />a(1) = 10<br />a(2) = -17<br />a(3) = 24<br />a(4) = -31<br />a(5) = 38<br />a(6) = -45<br />a(n) = 52, n >= 7<br /><br />I just want to try this for myself:<br /><br />a(1), a(2), a(3),.. <br />a) 10, -17, 24, -31, 38, -45, 52, ... <br />.....-27 +41 -55 +69 -83 +97<br />...... +65 -96 +124 -152 +180<br /> ... seems not to work<br /><br />lets try it with the absolute value as the sign seems to alternate:<br />a) 10, -17, 24, -31, 38, -45, 52, ... <br />..... +7 +7 +7 +7 +7 +7<br />=> f(x) = (3+7*x)*(-1)^(1+x)<br /><br /><br />b) -1, 1, 5, 13, 29, 61, 125, ... <br />.....+2 +4 +8 +16 +32 +64<br /><br />=> recursive: g(1) = -1; g(x) = g(x-1) + 2^(x-1)<br />=> non-recursive: g(x) = 2^x - 3<br /><br /><br />c) 6, 9, 14, 21, 30, 41, 54, ... <br />....+3 +5 +7 +9 +11 +13<br />..... +2 +2 +2 +2 +2<br /><br />=> recursive: h(1) = 6; h(x) = h(x-1) + (2*x-1)<br />=> non-recursive: h(x) = 6 + (2^x - 1) = 5 + 2^x<br /><br />lets see if I was correct:<br />a) correct<br />b) correct<br />c) correct <br />juhu :D<br /><br />By the way, the method I demonstrated for finding the sequence can be used for finding a reasonable sucessor for every sequence. Sometimes, like my first try for a), you can be quite sure that the sucessor you might get will not be the on that the questioner wants to hear, but it is never the less a reasonable sucessor. Has this method a name? I created it by myself, but I guess I'm not the first one who uses it.Martin Thomahttps://www.blogger.com/profile/13629221699214248094noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25608276315022884842011-08-08T11:06:58.728-05:002011-08-08T11:06:58.728-05:00Anon-OES- My hope was to give sequences simple eno...Anon-OES- My hope was to give sequences simple enough so that they wouldn't need OES.<br /><br />Anon-Kolm- I didn't really expect to be able to define this using Kolm complexity.<br /><br />Anon-Curious-what-point- Depends on the complexity of the sequence. The sequence 1,2,4,8,16 (which I WOULD NOT<br />trick them on by saying its something else) I would<br />expect they would be able to figure out in HS. The problem I gave them I HAD THOUGHT they could do before<br />learning induction, but upon giving it some of my<br />VERY GOOD students could not do it (and not becuase it was ill defined) so I would now say a good student<br />AFTER a course in discrete math should be able to do it.<br /><br />Anon-OES again- You raise an interesting question.<br />Since computers can do certain things do we need to<br />ask the students to do them? Should students not be<br />required to know what 7*8 is since they have calculators? Should students not be able to guess<br />what 1,3,5,7,9,... is because they have OES?<br />Should students no longer be able to derive that<br />sum_{i=1}^n i = n(n+1)/2 because they have<br />Wolfram Alpha? For the examples I picked I think<br />they are too easy to say THE STUDENTS NEED NOT KNOW IT,<br />but (1) you may respectfully disagree, and<br />(2) there IS some cutoff where the students really shouldn't need to know stuff, but not sure where it is.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86889591607609760872011-08-08T11:00:23.087-05:002011-08-08T11:00:23.087-05:00I find it amazing when people complain that such p...I find it amazing when people complain that such problems do not have a unique solution. It seems like everything in life should have a unique solution... <br />Noticing patterns is important because most people work by observing, conjecturing and proving. Of course, we may try proving first more complicated, general patterns. Good luck in such case.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31413796222408599472011-08-08T10:58:01.415-05:002011-08-08T10:58:01.415-05:00Out of curiosity, at what point would you expect t...Out of curiosity, at what point would you expect that a student of math or CS would know what to look for in these sequences?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45417833752055068022011-08-08T10:15:49.541-05:002011-08-08T10:15:49.541-05:00Anon- We were going to be induction and one of the...Anon- We were going to be induction and one of the things<br />that you prove by induction is<br />given a recurrence for sequence (e.g., a(0)=1, a(i)=2a(i-1)) find an expression in closed form. I like<br />to have the students caluclate a few of the values and say<br />thinks like `OH, that looks like 2^n !' and then prove it.<br />This excercise was practice in that, though we gave them<br />the numbers directly.<br /><br />More generally, it comes up in math that you see a sequence<br />(or something more complicated) and need to speculate<br />or guess on what it might be.<br /><br />Janorma- YES these problems need not have unique answers.<br />Thats why I gave the many terms of the sequence<br />and asked for a simple expression. Part of my<br />point of the post is that a class develops its<br />own terminology and understanding that might not be<br />well understood outside of the class. It was my<br />hope that SIMPLE FUNCTION would be one of them.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69557722486321441282011-08-08T10:11:10.919-05:002011-08-08T10:11:10.919-05:00Even if this kind of questions made sense from ML ...Even if this kind of questions made sense from ML point of view, the size of data set is too small. Kolmogorov complexity neither makes sense, it completely depends on the the K function you have in mind. I strongly dislike these kind of question, you are essentially asking students to guess what you have in mind. Do you think it is going to help them in predicting the stock market or something? What is the point of these questions?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88634153476463055812011-08-08T10:10:00.625-05:002011-08-08T10:10:00.625-05:00All of them can be looked up in OEIS. Meaningless ...All of them can be looked up in OEIS. Meaningless exercise.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90561539972229524122011-08-08T09:42:52.387-05:002011-08-08T09:42:52.387-05:00Bill, I have to disagree with you when you point t...Bill, I have to disagree with you when you point to "the" answer, since there are many --in fact infinitely many-- answers to each question, and even if only one of them counts as "simple", we still need that definition to check that it is, indeed, simple!<br /><br />This reminds me of some questions in the PSU (our national equivalent to SAT), question of the kind: "What is the next number in the sequence 2, 4, 6,...?". It is inherently a mistake to consider the sequence as being uniquely identified. One student might think of even numbers and answer 8, while other might think of "odd prime numbers minus 1" and answer 10, but it would probably be "wrong" (officially, at least).Janomahttps://www.blogger.com/profile/08125807104571129259noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39916546634700217182011-08-08T09:25:39.545-05:002011-08-08T09:25:39.545-05:00I wonder what is the point of asking such question...I wonder what is the point of asking such questions to the students? And in particular, what is the point of asking for a simple function (whatever it means) to interpolate the values and not accepting that the students gives an interpolating polynomial. It seems much interesting to me for a student to compute a interpolating polynomial than to guess 2^n-3. <br /><br />I shall say that I never taught a sophomore discrete math course, so I never really thought to what should be taught in such class and how. I was just quite surprised that you asked such questions! But I'd really like to understand the (good, for sure!) reasons you did it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15460747679903352852011-08-08T09:03:27.987-05:002011-08-08T09:03:27.987-05:00When you said simple function, the first thing I t...When you said simple function, the first thing I thought of was a function with finite range, just like the one you described. Seems like sequences you could describe with a simple function would be kind of boring!Anonymoushttps://www.blogger.com/profile/17266922987181535824noreply@blogger.com