
Re: Is this an exceptionally hard set of questions to answer?
Posted:
Oct 7, 2002 3:39 PM


Alberto Moreira <junkmail@moreira.mv.com> writes:
> Kevin Foltinek <foltinek@math.utexas.edu> said: > > >You can understand the algorithm without knowing whether O(n^k) is > >faster than O(2^n); you will not understand which is faster, though. > > The point that an O(n^k) algorithm may be timewise feasible while an > O(k^n) algorithm may not be seems to have escaped this argument.
Only for those who are incapable of reading and comprehending more than one sentanece at a time, for you will note I later said "O(n^k) will be faster for all sufficiently large n".
My point, that just knowing O(...) behaviour may not be enough, appears to have eluded you. For example, implementations of quicksort usually don't do a quicksort unless n is sufficiently large.
> And I > can easily contend that if someone doesn't interiorize this very > simple but very fundamental point, one doesn't really understand > either class of algorithms.
One can certainly understand an algorithm without having derived its asymptotic runtime estimates; one would not understand all the properties of the algorithm. One can certainly derive rather than interiorize the fact that O(n^k) is eventually faster than O(k^n) (with respect to n); having done so, would one understand the properties of the algorithms in question any less?
> >Even if you know n and k, you still will not know which is faster. > > A polynomial algorithm is asymptotically faster than an exponential > one. Like GKP say in their marvellous book, THINK BIG. But if I know n > and k, I can always throw it into Maple.
OK, let's say that algorithm A is O(n^k), algorithm B is O(p^n), and n=100, k=10, p=20. Which is faster, algorithm A or algorithm B?
> Computation, you know, is for machines.
That's along the lines of what I've been saying  remember this started out with my less than fond memories of rote computational drills in the early years?
> >Computation is a consequence of mathematics. It can be learned > >without learning the underlying mathematics, but since it is a > >consequence of the mathematics, it cannot be removed. > > It's the other way around, mathematics is a consequence of > computation. Much mathematics exists basically to formalize the > intuitive concept of computation.
You seem to be mistaking the historical development of the subject with the subject itself.
> That may as well be, but that's not the point of the discussion. The > point was, I believe, what direction do we give a math course when we > take a K12 classroom full of kids who not only won't probably be > mathematicians, but many of them won't even engage in applied math or > in applied mathematical science. You see, I'm not advocating the need > for mathematicians, I'm debating the issue from a teaching point of > view ! I post from misc.education, not from sci.math.
Right, and as a teacher, I would have expected you to consider the datum I provided: that someone (myself) who enjoys mathematics and is good at it has rather less than fond memories of rote arithmetic drills.
> >what > >might make economic sense is to hire a mathematician to help write a > >computer program that can be used on any site. > > Again, there's way more to a computer program than mathematics.
Perhaps you missed the word "help" in what I wrote.
> Not > only knowing math doesn't help writing programs, but it is perfectly > possible to write great programs without knowing anything beyond > elementary arithmetic.
This is no doubt true for some programs, but it would be beyond stupid to believe that it is universally true.
> So, coming back to my teaching, maybe it's a good idea to punt that > kind of math to grad school, and concentrate my more elementary > teaching on things that don't go that far and that aren't as > esoteric as not to be mentioned in the majority of textbooks we > use.
Are your textbooks homogeneous in content because that is what is important in the subject, or because of institutional inertia, or because of some other factors?
> >I'm sorry, did you just say "QUANTITATIVE"? Please show me the > >numerical values to which Simmonds was referring. > > Pray, what's the use of visualizing vectors in an application such as > an airplane turning, if direction and length aren't part of it ?
When I visualize the levelflight airplane force vectors (e.g., thrust, lift, drag, gravity), I see QUALITATIVE directions and lengths: the thrust is pointing forward and slightly up, the gravity is straight down, the drag is backward, the lift is up and slightly back. No numbers, but qualitative descriptions of direction and length.
Perhaps you are using abstract qualitative reasoning without realizing it.
> I'll give one bad example. Have you ever taught elementary trig ?
Yes.
> Some students will have been taught that cosine is the result of > dividing the adjacent side by the hypothenuse. Then you go and draw > them the trigonometric circle and say, "here, guys, just let the > radius be one and the length of this line segment is the cosine".
You're right, this is a bad example (of teaching).
> Then enjoy the blank stares. "BUT TEACHER, THAT RADIUS IS *NOT* 1 !" > You see, this is what I call "number sense": students who have it > find that jump intuitive.
That is not number sense; that is an understanding (perhaps intuitive) of the invariants of Euclidean geometry.
> Lord, how many of them have problems orbiting a > sphere along a meridian ? They get to the north or to the south pole, > and their math goes astray: because more often than not, they blindly > throw the equations in, and forget to use their number sense and > spacial sense to predict problems.
Again, this is not number sense; if they understood analysis, geometry, and the definition of coordinates, they would be well aware of the singularities, and would (hopefully) know to insert the appropriate code into their algorithms to verify that they were in a nonsingular region.
> More, if I want to rotate I call glRotate( ),
if you happen to have the appropriate library available. Perhaps you need to handcode an implementation to optimize performance or memory requirements on your embedded application. (Also, see below for the dangers of the "if I want to X, I call glX()" way of thinking.)
> Five minutes of running that tutorial, > and my students learn more about the transformation than all the math > in the world could teach them. You know what ? Because the tutorial > shores their intuition in the right way. Once they get it, moving down > to the math is trivial pursuit.
I'm having a hard time reconciling the above with your earlier implications about the need for rote arithmetic drills.
> But if I just give them the math, none > of them will learn half a fraction of what they need to learn. > If you really want them to understand it, you should have them derive it on their own.
> And here we seem to agree: I have still to see a number in my real > life without a unit attached to it.
Never rolled dice?
> Because if one of my students needs to stop to think mathematics while > I'm teaching them algorithms or graphics, sorry, that student is > wasting his or her precious time that should be more profitably used > to learn algorithms.
Pity the student who gets into the real world, finds a job, is given an assignment to write code, sees that none of your algorithms drops neatly into the assignment, and realizes that perhaps one of the algorithms needs to be modified, or even a new one created. Too bad the student didn't understand the mathematics behind the algorithm, because if they did, they would have a much better chance of coming up with the appropriate modification.
> >> and music for once is way more difficult to master than math. > > > >Again you are demonstrating your ignorance of what mathematics is. > > And you are demonstrating your ignorance of what music is. But I for > myself went far enough into both careers to know the difference.
I have considerable experience in music (though not professional). I understand what is required to master music. It is not trivial, but to claim that it is "way more difficult to master" than mathematics is incredibly naive.
> If mathematics is not sufficient to do an application, it obviously > follows that mathematicians are illequipped to perform many > application tasks.
Your lack of logic skills are showing. If the only thing that mathematicians know is mathematics, then your above statement is true. Unfortunately for your statement, this is a prejudiced stereotypical view of mathematicians; while there are some mathematicians who know little other than mathematics, there are a great deal who know a lot more, and many who have nearexpert knowledge in other subjects (such as physics, biology, etc.).
Moreover, it has been my experience and observation that mathematicians can often learn other subjects faster than nonmathematicians can (an observation similar to one that Feynman made about physicists).
> If it is not automatic, it's not real skill. I'm sorry, my criterion > here is really strict. As I pointed out before, I'm also a classical > musician: if it doesn't come automatically when I tell it to, my > listeners will know the difference. Coming back to something I said > before, the day mathematicians need to do their stuff in realtime in > front of a very demanding audience and in absolute lockstep with one > hundred other performers all while taking care of a mindboggling > array of detaillevel specifications, plus the need to add one's own > creative line on top, then, maybe one can claim mathematics is harder > to do than music.
You just came pretty close to describing a typical mathematics conference (except that the audience and the performers are the same people). You'll note I never said math was harder than music. In fact, I suspect they are incomparable. (See "partially ordered set".)
> Mathematics cannot tell intuition is right or wrong, because > mathematics does not model intuition.
Your lack of logic skills is showing again. I have a counterexample in which an entire community of experts were assuming as "intuitively true" something which was mathematically false (except for some special cases).
The error in your statement is your assumption that mathematics must model intuition in order for it to say something about the product of intuition.
> What you call "concept" is > either an axiom  which is arbitrary and needs not match anything real >  or a rule of inference  which is usually an oversimplification > because real life inference is too tough to be modeled  or a theorem, > which is just a simpleminded assertion.
Wrong, wrong, wrong. Rules of inference come before axioms; theorems are statements about the properties of concepts.
That you think a theorem is a "simpleminded assertion" merely (once again) demonstrates your ignorance of the subject of mathematics.
> If the intuition is correct, the algorithm will > be applied where the preconditions allow it to  but if the intuition > is not there, it becomes a lottery.
If the mathematics is there, it does not matter if the intuition is correct or not  the mathematics will tell you whether the conditions are satisfied.
> >Pure mathematicians work on the "concept" end of your "concept, > >algorithm, application, problem solving" spectrum, with significant > >work in the algorithm and some in the application. Applied > >mathematicians work less in the concept, more in the algorithm and > >problem solving, but still are intimately familiar with the concept. > > Pure mathematicians work inside formal systems. They do NOT deal with > what I call concept, because my concept of concept is the concept that > exists in problem space:
Well into the application part of the spectrum.
> outside the mathematical model. If the > algorithm operates in problem space  and many do  mathematics is not > necessary.
Sure; if I want to sort a column of numbers, I call the "sort" function.
> but then, my > experience tells me that it is imperative that, there too, we grow up > an intuition in our students, otherwise we'll lose many of them.
Right, so let's get on with those repetitive, mindless, rote arithmetic drills  much better for the intuition than tactile and visual models of numbers, like, say, Cuisenaire rods.
> >That you mentioned O(n^k) as being required to understand the > >algorithm suggests that you are somewhat unfamiliar with the concept > >end of your spectrum. > > If you don't know the difference between an O(n^k) and an O(k^n) > algorithm, you're going to have a problem in my profession. And that > must go a lot further than just knowing it at the theoretical math > level.
One can understand, say, how the quicksort algorithm works, without realizing that it is O(n log(n)) on average. One can also know that it is O(n log(n)) without knowing anything about how it works. Preferably one would know both; however, given the option, I would prefer the former over the latter.
And if you don't know the difference between n^k and k^n asymptotic behaviour, you're likely going to have a problem in my profession as well.
Kevin.

