What University Challenge considers Computer Science

Happy New Year – 2012 is the year of code! The ICT curriculum in the UK is to be overhauled to make it less about word processors and spreadsheets and more about programming. The smartphone application market has kick-started a new generation of programmers who don’t need to be in a team of hundreds to make some interesting, cool and worthwhile.

But are we i.e. technology enthusiasts, too gung-ho about coding? Shouldn’t we try just as hard to promote computer science? Case in point, over the festive break I managed to catch a special edition of University Challenge and was yet again dismayed by what this beacon of competition in higher education considers to be computer science.

I don’t watch University Challenge religiously but always enjoy it when it’s on. My knowledge of science, politics, history and geography which I used to think were quite rounded is shown time and time again to be lacking. Less said about the classics and poetry the better. Indeed, my final points total depends largely on whether the music question starts with Paxman announcing, “For your music starter you’re going to hear a piece of popular music…”

The area of expertise I should have a fighting chance of getting some points in are the subjects of mathematics and computer science. For the most part I find the mathematics questions at a level beyond which I studied at university, stopping as I did just before the honours courses. But the computer science questions I find frustrating for completely different reasons. Here are three that I recall from memory (answers hidden in white text). I should state that not having seen every episode from the last few years I can’t state they’re all as bad as this but that these are even asked at all says a lot about what the show’s producers consider to be computer science.

Q: What does the acronym USB stand for?
A: Universal Serial Bus

Q: What is the name of the operating system created at Bell Labs in 1969 by Dennis Ritchie and Ken Thompson?
A: Unix

Q: What does the acronym BIOS stand for?
A: Basic Input Output System

That last question on the BIOS acronym was from the recent special edition I watched. I sighed as I recited the correct answer. The question regarding Unix is certainly a valid one about the history of technology and fundamentally important to IT in general. The other two questions, however, could be answered by a student training to be a PC technician. They all have absolutely nothing to do with computer science. In the same way you don’t get questions declared to be about English literature followed by a question actually on book binding, we too should be having questions taken from undergraduate computer science honours courses.

I whole-heartedly support the move to get the wider public interested in understanding technology more deeply and even learning to program, however, if we ever want our discipline to be taken seriously we need to show that it is more than just programming; more than just the nuts and bolts of software and hardware systems; more than just a list of TLAs and ETLAs to quote back parrot fashion!

Most of my lecturers told me they started out as mathematicians and moved over to computer science as it was a relatively new and small research area. That has not been the case for at least two decades now. It’s time to get some proper computer science questions in University Challenge. Here are a couple of example sets of bonus questions in the University Challenge format: gentle opener followed by two tougher follow-on questions.

If you want to join in, post a set in the comments and I’ll add them to the list.

Q: In problem complexity classification, the immediate superset of the polynomial time problems, P, is known as NP. What does NP stand for?
A: Nondeterministic Polynomial

Q: Which problem complexity classification can be defined as the set of all problems that are NP Hard and can be converted to any other problem within its classification in polynomial time?
A: NP Complete

Q: What is the name of the problem complexity classification that is a superset of NP problems, requires polynomial memory to solve, and is a subset of all EXPTIME problems?
A: PSPACE
Q: Describing a function that measures the time taken for an algorithm to process a set of data proportional to the size of the input, all but the largest growing parts of the function are discarded. What is the name of this notation?
A: Big O Notation

Q: What is the big o notation of finding an element in a linked list of n elements?
A: n

Q: What is the optimal big o notation for sorting a list of n numbers into numerical order?
A: n log₂ n