this kind of test is not valuable. the other tests i've done though - even though incredibly easy i think would be more useful for seeing how i approach problem solving in general...
Regarding CS majors, there's always the possibility of an individual being great at the theory part, but not having much programming experience. This should be rare though; during my own CS degree, we coded so much that I was frequently dreaming about code. If it's provided in the CV, I like to scan through the subjects list of the candidate - the ones who don't actually like programming seem to have an aversion to taking CS courses for elective subjects. As always though, YMMV, and it's a good idea to keep an open mind.
conversely my experience of education is that it trains you to solve education style problems - which are essentially absent from the real world - where being able to invent and implement a slightly broken solution in an hour with 30 seconds notice is much more valuable than being able to solve a problem you know about far in advance and are given loads of information and guidance to help in preparation for it.
on the other hand if i wanted someone to do research then a CS major might be a better choice. :)
* By well-executed, I mean - relatively language agnostic, lacking in trick questions and meaningless trivia, and being open to multiple good answers. The intention is to not only check basic ability to solve simple problems, but the general approach and programming style of the individual interviewed.
Past experience is often vaguely stated in CVs and looks great on paper, but can be disingenous. It takes a thorough two-way discussion which is customised to each individual to reveal this, however. Some people have excellent and highly visible past achievements, but not everyone does. I wouldn't throw out a CV simply because the individual doesn't have any open source code to show me, nor do they have any awards from companies they have worked for (which is often more about self-marketing than actual ability).
I guess your mileage may vary based on the position that's in question and the companies involved, but I've seen some shocking discrepancies between CVs and actual programming ability. Even worse than the usual "fizz-buzz" statistics that get thrown around.