3 ms·

This is very interesting and very true. I think the main points of this article are: 1. Constants do matter, specially most programs end up with an asymptotic

by alextp 16y ago

This is very interesting and very true. I think the main points of this article are: 1. Constants do matter, specially most programs end up with an asymptotic that looks like a N^b, and a and b are often not what you'd expect. This matches my experience a lot, and it's interesting that this is one level below O notation but one level above "counting how many operations should happen, roughly", which is what you have to do in practice to make algorithmic code go fast. 2. The examples around which an intro to CS course is structured are really uninteresting. I couldn't agree more, and never cared for computing factorial, fibonacci, etc, or for writing silly games or dumb data-processing programs; Simulations and numeric algorithms are far more interesting, and can get students interested more easily when they realize that other classes' work can be made far easier with computers. 3. Everyone should know CS. Even my philosophy-major wife often has the need to run short scripts to automate some tasks, and I think that if a philosophy major can benefit from CS concepts anyone else should as well. All these things one should find out eventually, and I agree that exposing people to these concepts as soon as possible is a very good idea, far better than what is usually taught as CS-for-non-CS-majors.

mturmon 16y ago
And regarding your point (1), the slides also lay out the interesting case in which the typical-case asymptotic time complexity a1 N^b is far more favorable than the worst-case form of a2 N^b The first form is generally deduced through extensive experiments with typical data, while the second is (often) easily proved with just paper and pencil. The first is the more important in practice, but the second is what's quoted in textbooks. There are so many algorithms in which a1 << a2, which enables all sorts of problems to be addressed that would be otherwise intractable. The linear programming/max-flow type problems the slides mention are a major case.

by alextp 16y ago

mturmon 16y ago

And regarding your point (1), the slides also lay out the interesting case in which the typical-case asymptotic time complexity a1 N^b is far more favorable than the worst-case form of a2 N^b The first form is generally deduced through extensive experiments with typical data, while the second is (often) easily proved with just paper and pencil. The first is the more important in practice, but the second is what's quoted in textbooks. There are so many algorithms in which a1 << a2, which enables all sorts of problems to be addressed that would be otherwise intractable. The linear programming/max-flow type problems the slides mention are a major case.