That's quite a bold claim.

He mentioned he's a "developer", and from his point of view, (and mine), the field of practical programming knowledge is pretty limited. So he could roll up to a Barnes and Noble, pick up most any book and learn the concepts in it no problem.

But on the other hand, couldn't P=NP be considered "programming concept" itself? But on the third hand, maybe once its figured out, it will be a concept he could learn in a day.

So you're right, "there isn't a single..." is probably pushing it. But I'd definitely stand by the fact that I can read, understand, and re-implement 99% of algorithms or architectures.

My point is simply that the breadth of the field of software engineering apparently pales in comparison to that of mathematics.

Or rather --- it's very strange to me that if you are an expert in a given branch of mathematics, then all of your lifetime of experiences cannot be applied to an entirely different branch. If I understand cperciva correctly, if you want to learn a particular specialized branch of mathematics, then you basically have to start from the ground-up (years).

It would basically be equivalent to wiping your memory of all programming knowledge, then re-learning it all, in terms of effort. It's just strange / interesting that mathematics works that way.

You are right that mathematics is unique in being an infinitely broad subject. Programming as a subject is like medicine in that it is constrained by the real world. However, I don't know about you but I'm not going to trust a radiologist to perform surgery because he's 'understood' the concepts in one day.

Conversely she was shocked to realize that people in mathematics couldn't. And that you could easily complete a masters in mathematics without once being asked to try to read a real research paper.

That shocks me, too. I'd expect anyone completing a master's degree in mathematics to have published at least one paper, never mind reading others' papers.

Publishing is another story. Reading current research is one thing... actually successfully advancing the state of the art in an area of pure math is quite another. (Applied math is another story altogether).

The University of Chicago awards ‘incidental’ master's degrees at the end of the first year of graduate study (http://catalogs.uchicago.edu/divisions/math.html). Although it's certainly possible to be reading current research at that point, I wasn't; and yet I think it's fair to say that U of C degrees are worth something.

Personally I published my first paper in undergrad. But that was considered unusual among the people I knew.

Can you implement this algorithm in less than a day then?

http://www.cs.princeton.edu/~chazelle/pubs/polygon-triang.pd...

Disregarding the "linear time" part, there is a standard way to accomplish this goal:

- the polygon can be thought of as the "outline".

- transform the outline into a set of XYZ positions (verts). This is accomplished simply by starting at any point on the outline, then stepping along the outline by a fixed interval until you wind up back at your start pos.

- then:

  triangles = []

  while len( verts ) >= 3:

   for i from 0 to len( verts ) - 2:

     A = verts[i]
     B = verts[i+1]
     C = verts[i+2]

     # verify the triangle has not been flipped inside-out, and is not degenerate.
     det = Determinant2x2( A - B, C - B )

     # if the triangle is degenerate, then remove the middle vertex.
     if det == 0:
       verts.remove( B )
       break;

     # if the triangle is inside-out, skip it.
     if det < 0:
       continue;

     # if the triangle does not intersect the polygon and is not inside-out, then it is a valid triangle, so add it to the result.
     if not TriangleIntersectsPolygon( poly, A, B, C ):
       triangles.append( [A, B, C] )
       verts.remove( B )
       break;

Now, it is not linear time, but there is no reason to optimize this algorithm unless it turns out to be necessary, which I've never yet seen to be the case in an actual real-world scenario.

That's the thing about scientific papers --- they are very useful, but only if your problem domain precisely matches theirs. For example if you don't care about "linear time", then all of that paper's complexity simply fades away.

This is like someone challenging me to implement merge-sort, and then I give him the solution to bubble-sort saying that there's "no reason to optimize" until necessary.

Granted the cases where Chazelle's linear time algorithm is necessary is less than merge-sort. But that is true of any field, including mathematics.

I gave a solution that solves the problem. The problem is, convert an arbitrary concave closed polygon into a set of triangles. I maintain that it is completely valid for me to present that solution --- there are plenty of tricks you can do to optimize it in C/C++. And not just runtime optimization either... For example why not triangulate the polygon, then save the results to disk? That way O(N log N) vs O(N) becomes completely irrelevant... you only have to do it once, ever.

I suppose what I am saying is this: I can solve 99% of real-world problems I am likely to encounter in my career as a software engineer. The challenge "implement THIS scientific paper!" is completely invalid because it's a solution to a problem which very likely will never exist. My solution is valid as long as it does not greatly impact the performance of the app. Which is "always", once you throw in a layer of caching.

P.S. The paper has the restriction "for every polygon vertex XY, no two vertices may have the same Y coordinate", which means it's likely to not be applicable to any real-world problem.

Memoization is not panacea. This is like telling someone to sort every possible group of numbers and saving it to disk so you don't have to implement something faster than bubble-sort.

My point is that in any field, "99% of real-world problems" are easy enough for the average college graduate to comprehend. Think about the kind of math that is useful for "real-world" problems. When you start bragging that you can learn any CS topic/algorithm in less than a day, you just didn't look hard enough.

P.S. You missed the sentence right after where it says "we can easily get around this assumption by applying the symbolic perturbation techniques of [10] and [31]"

Memoization is not panacea. This is like telling someone to sort every possible group of numbers and saving it to disk so you don't have to implement something faster than bubble-sort.

I really am not trying to be mean, I'm just stating the facts -- your statement is so full of ignorance that it's kind of disturbing that you believe it. Programming is generally an exercise in caching. There was a good article posted a long time ago called It's caches, all the way down. If you think about it, memoization (a.k.a. 'caching') has been the primary solution to a large percentage of past problems. The examples off the top of my head:

- GPU memory is a cache of system memory

- system memory is a cache of the hard drive

- the operating system presents a file I/O interface which heavily utilizes caching

- John Carmack developed Quake which revolutionized the realtime graphics industry primarily because of his innovative "potential visibility set" algorithm, which is just a cache of computing visibility on-the-fly

So for all intents and purposes, memoization (caching) IS the magical panacea that you deny it to be.

Of course caches are important. But it isn't the only thing. That's why programs aren't all giant databases. Memoization != better caching either. That is simply naive. If your algorithm can fit in L1-L2 cache, it can be better than loading a giant hash table or tree from disk.

I'm not trying to be mean either, but you have all the signs of a junior developer who thinks there is nothing left in CS to challenge him as he churns out enterprise crud where caching is the only thing he can think of that matters.

Because the problem applies primarily to realtime 3D / 2D graphics, of which I have spent the last 7 years learning about. That is of course not a guarantee the problem does not exist, but it is very likely. Otherwise, it would be one of the significant known problems in realtime graphics.

Even if you are pre-computing it, wouldn't you like it to go faster, like encoding a video or rendering a ray-traced scene?

What I want is irrelevant. All that matters is what the application needs to do. It is a senseless waste of time to optimize a sufficiently fast algorithm.

There are an infinite number of polygons.

There are an infinite number of numbers. This has no bearing on the problem, on the effectiveness of caching, or on any other of my points. In other words, this is yet another completely irrelevant statement by you.

You have all the signs of a junior developer who thinks there is nothing left in CS to challenge him as he churns out enterprise crud where caching is the only thing he can think of that matters.

Oh, really? I did you the courtesy of explaining exactly why your earlier statement was so full of ignorance. You merely insult without reason or basis. Congrats, you are a troll and have been trolling this entire time. This means you have not only completely discredited yourself, but are also no longer worth trying to disprove, because your statements are without reason or merit. Which is quite sad, since I personally was interested in an opposing viewpoint; but not if it's completely insane.

Have you even solved any problems related to "polygons" in your programming career? Also, how long exactly have you been programming for? I have been programming for ten years. I'm trying to find one good reason to take any of your statements seriously. Unless you have any graphics experience, or more experience in general, I see no reason to. And since you have neither logic nor tact, I see no reason to continue this conversation.

Instead of rising up to the challenge or admitting failure, you make broad sweeping generalizations like you could learn 99% of any CS concept in less than a day, and that any challenge that you are not willing to do (or likely cannot), is because the challenge has no "real-life" application.

Not only did you read the paper incorrectly, trying desperately to find holes in it, but you try to change the subject by calling me naive in my refusal to allow you to just say "memoize" as the answer to any algorithmic challenge. I think it is clear to anyone else reading this that you are in the wrong here.

The following algorithms have beaten me totally and I wasn't able to implement them:

Bochs multiple shooting (the modern versions are even more complex): http://www.iwr.uni-heidelberg.de/groups/agbock/FILES/Bock198...

Multitaper Spectrum Analysis: http://www.amazon.com/Spectral-Analysis-Physical-Application...

Korenbergs Nonlinear system identification algorithm: http://www.informaworld.com/smpp/content~db=all~content=a769...

While this may be true, you are comparing apples to oranges. "Read, understand and re-implement software algorithms / architectures" is to computer science as "Read, understand and apply some given formulas to solve a problem instance" is to maths/physics.

Formalizing and proving the correctness and boundaries of these formulas is the hard part here, where mathematicians are doing their job. You probably can implement a Support Vector Machine in one day given a detailed pseudo-algorithm, but truly understanding the underliying concept, as well as its weaknesses and strong points is way harder. Let alone improving it. And the very same thing can be said about a lot of other algorithms (MRF-optimization, coding theories, etc.).