tsahyt

Writing a toy ray tracer is something that I'd recommend to everyone who's interesting in becoming a better programmer. Once you get deep enough into it you'll encounter so many interesting problems (e.g. data structures, software architecture, some linear algebra, etc.) to hone your skills on. It's almost up there with "write your own compiler" as a learning experience in my opinion and you get the added benefit of creating some pretty pictures in the process.

I do. I've got the server counterpart set up on a Linode and sync my task lists across all devices. That's quite nifty because I usually think of things that I should be doing while I'm on the go. At the moment I need this kind of organization to get anything done, and out of all the solutions I've tried this one is by far the best. The feature I use the most is probably the scheduling feature. After dinner I'll sit down for a moment and contemplate which of the tasks I've still got open I will do the next day and schedule them accordingly. The next morning I do a `scheduled:today` query and I've basically got half the day laid out in front of me already. The best part of it though is that by running my own task server (at no additional cost because the same box doubles as my mail server), all the data belongs to me instead of relying on a third party.

The beauty about Linux (and a lot of well-maintained open source software) is that security flaws are usually patched rather quickly -- with the possible exception of the disaster that is X, but Wayland is coming along nicely.

Same here, although I somehow wanted it to win, so I could finally at least see the mythical 2048 tile that everyone seems to be speaking of.

I'm running dwb, version 2013.08.03 (either the maintainer for Fedora is slightly lazy or there hasn't been a new version in a while) on Fedora 20. It reports Safari 538 and OSX as the operating system. I've also got cookies disabled and it reports that I have them enabled, which is strange.

Many NP-hard or NP-complete problems have (infinitely many) instances that are "easy" to solve. It is quite straight forward to write up a procedure that produces infinitely many instances of 3-SAT that can be solved in polynomial time by the DPLL algorithm. But it is important to note that a problem is actually a set of instances.

Your observation basically boils down to "how rare is the worst case?". There are actually algorithms with exponential worst case complexity that are used all over the place because - on average - they perform really well. The simplex algorithm for linear programming is an example for such. Every version of this algorithm comes with a worst case problem such that the algorithm has exponential runtime. However, on average it is quite a fast algorithm that can handle millions of variables and corresponding constraints on modern hardware. Still, that doesn't change the fact that linear programming is - from a theoretical point of view - still hard enough that we cannot generally solve it faster than in exponential time. As is the case with DPLL, good heuristics can speed up an algorithm a lot without changing worst case complexity. Other examples are all over the place in AI. It's also in AI where the concept of pruning is probably encountered most often. This the practice of discarding whole subtrees of the search tree by some sort of heuristic or deductive reasoning.

Those things aside, I think what we should be looking at from a theoretical point of view is when it makes sense to consider the average case complexity over the worst case complexity. This brings us back to "how rare is the worst case". Quicksort for instance is said to be an O(n log n) algorithm but it has O(n^2 ) worst case complexity (trivially so). However, it can be decided in O(n) whether this case actually occurs and hence a good sorting implementation could switch to a different algorithm once this has been detected (something similar happens in the std::sort function that's been implemented in the STL). This is definitely a case where it makes sense to "forget" worst case complexity.

For SAT, researchers have actually worked up statistics on how hard certain instances are in terms of the number of clauses and the number of symbols. It turns out that there is a range of ratio between the two where problems are the hardest (roughly between clauses/symbols is between 4 and 6). I don't have a source right now but googling "satisfiability threshold conjecture" might turn up some results.

As such, yes, not all instances of NP-hard problems are actually hard to solve, but there are infinitely many that are. Encountering such problems in practice one can usually make use of the special problems of the instance (or class of instances) one actually encounters and devise an algorithm that performs rather well on average.

This might come across as quite harsh but the article could have been much shorter.

NP is the class of decision problems that can be solved by a non-deterministic Turing machine in polynomial time. A problem is called NP-hard when there is a polynomial-time reduction of 3-SAT to said problem. A problem is called NP-complete if it is both NP-hard and in NP. Since TSP is not a decision problem, it is not in NP, therefore it cannot be NP-complete. However, it is NP-hard.

One can call this a minor nitpick. I still point it out every now and then when I hear people talking about such things. However, the really important thing is that we haven't found a way to solve NP-hard (and hence of course NP-complete) problems efficiently on a deterministic Turing machine (and hence computers as we can actually build them). An informal way of saying the same thing is "TSP is really really hard to solve".

Either way, I'm always surprised at how many problems we encounter in our every day lives are actually NP-hard. Every decent puzzle game for instance is usually NP-hard. Goes to show that we don't really enjoy solving easy problems.

EDIT: Of course there's also a decision version of TSP, as others have pointed out. This one is NP-complete of course.

I thought the hash was in fact used for ensuring data integrity. That's pretty much what Linus stated when he said you have a guarantee that the data you put into your repository is exactly the data you get out of it.

I'm no expert but as far as I understand, the signature would be valid as long as the hash stays the same. If the commit has been tampered with in such a way that the hash does not change, the signature would still appear valid.

I'd be interested in learning Rust. I've been learning Haskell last year and I'm absolutely loving it.

But, wasn't the drama exactly the point of the article?

No specific examples, but all of my best optimizations as in biggest-speedup were of algorithmic nature that actually improved asymptotic complexity.

In terms of my favorite ones, it's probably a piece of C code using SSE intrinsics to speed up intersection checking for a voxel raytracer I've been playing with last summer. After about 1.5 days of hacking I've managed to shave about 50% off the rendering time per frame. Nice learning experience but completely pointless in the end. Since it was still way too slow for any practical use, I started rewriting it and eventually stopped halfway through.

There's a lot going on and that's the way it has been for quite a while now but as someone who's working with databases only marginally at the moment, I'm left wondering: What's wrong with RDBMS? Sure it's nice to have a simple Key-Value Store for applications that don't need much more than this but bottom line, the relational model is very powerful, albeit quite abstract, and most data we need to deal with can be made to fit into this model. We have a working, declarative query language that Just Works(TM), for which we have written very good optimizers. The various instances of such DMBS range from small-scale use (for example, SQLite) to really-huge (Postgres, Oracle, etc). So, to sum it up: Exactly why should we abandon this?

I used to strive for clever solutions. The shorter the better. I still like to look at them but I want them as far away as possible from my code base. Sure, if a solution is clever and efficient, while still readable, maintainable and easy to understand when documented properly, I'd use it. However, my general rule of thumb these days is: "Write this code, so an utter idiot can read it". Because that's what's going to happen: One day I'll have to read it again, and I'll feel like an idiot, trying to understand what once went through my brain.

That's something that took me way too long to learn and I feel that novice programmers should embrace that more. We all like to feel like Einstein sometimes, but a big code base is not the place for solutions only we can understand... temporarily.