Hacker News Reader

Comment by amix | Hacker News Reader

All things don't have to be practical. There's a lot of insight in knowing the theory, because it's the theory that everything is built upon. Knowing something about complexity theory gives one insight into how problems relate to each other and how complex they are - vital if you are solving problems.

And even if you don't use the theory, it still gives a better understanding fundament. For example, if you understand computability theory, you'll understand why your Java compiler can never determine if your program can halt or not (or any other interesting property of the program), and why you have to use static analysis to give an approximative answer.

And "theory" can be used in practice, an example is Google page rank algorithm which would have been hard to brute force without a good understanding of linear algebra.

View on HN

Let's say you wanted to write a CD burner program using the lowest level APIs provided by your OS. Which CS theories would you say would be applicable to such a task?

The low level API calls that you make, make use of the OS scheduling. But you may claim that you can be agnostic to this fact. On the other hand optimizing your code to run efficiently can be done either using your gut feeling, or by understanding the complexity of your code, to make it run faster, with fewer calls, and optimal buffer usage. Would that suffice as an answer to your question?

Exactly. Check out the Linux O(1) time scheduler.

http://www.ibm.com/developerworks/linux/library/l-scheduler/

The low level APIs do not require any knowledge of the OS scheduling. The code is not complex in the way you think it is - there is little algorithmic behaviour in a CD Burning task.

Let's see: predictive I/O scheduling, buffer management, and cryptographic checksums all seem like they fall within the realm of "algorithms," and all would be fairly necessary to a well-behaved non-trivial CD-burning system. And yes, you would need to have some idea how the operating system schedules tasks if you are to have any luck maintaining write throughput to keep from under-buffering.

That would be over-engineering. You want to keep your buffer full:

if buffer not full:

wait (time for 5 writes);

write to 5 * read_size to buffer;

Sure, you could do it more complex, but then you create fragile code at a spot when a simppler solution would work fine.

But even the fact that you have to decide on the buffer size is a matter of understanding the theory. Choosing to multiply by 5 too. Why is it 5 and 12? Why the buffer size is not the half or double the size that it has? How can you prove that you have chosen the correct values if not by theory?

What if you add the constraint that the user has a library of a N songs and you wanted to fill the CD completely for a road trip?

An approximate solution would work for the above but you can see how easily it pops up: http://en.wikipedia.org/wiki/Subset_sum_problem

Complexity theory is the coolest thing I've learned. I think thats why people study it - they don't particularly care about the practicality of their work. Which is ok. Breakthroughs and connections are often unexpected (It's hard to discuss cryptography without understanding it), so you might as well let the smart people do whatever they feel like in academia than declare x,y,z to be the 'real' issues people are facing that should be solved - we have the market/industry for that.

Incidentally, I wasted a lot of time thinking about http://en.wikipedia.org/wiki/Partition_problem in high school - I was trying to figure out how to make the A-side and B-side of a mix tape of equal length.

That has little to do with burning a CD. The particular problem you bring as an example is a small and completely optional problem that one would be faced compared to the entire task. And I could look up a solution in 15 minutes.

And thus, you've just gone and demolished your entire argument. There is no solution in reasonable time, which is why mwerty brought it up.

This whole downvote storm is because your OP was "CS students love dropping four letters: P, NP, O and N. Whenever I want to judge who was a bit too focused on the surface details of computer science, and too little on the real problems, I wait to see if those 4 letters come up in a sentence." and there is a crowd of people here whose work on real problems involves those four letters all the time & couldn't be done without extensive knowledge about them and discussing them endlessly.

Maybe they don't come up so often when writing cd burning programs or robotics (though I find the latter hard to believe since any planning algorithms should hit up against this quickly), but other people have their own real problems where it does. I'm trying hard not to be dismissive here, even though your original post reeked of dismissiveness.

If only you get to decide what's small, what's completely optional and whats the entire task, you are right and I submit.

You would have to be crazy smart to figure out P,NP, etc. in 15 minutes without pre-existing knowledge of it.

You don't need a CS degree to read the API documentation. But if you do bother getting a CS degree, shouldn't you learn something beyond how to look up the cdrom API documentation?

Some knowledge about OS design would be good, I suppose. You've got a degree; what fundamental knowledge do you find the most helpful? (Meaning, things that will be relevant in 20 years, rather than familiarity with what's hot right now.)

The most fundamental knowledge a university has to offer is to learn how to learn.

Reply on news.ycombinator.com