Looking for a challenge, somethign easier than P ?= NP

April 19, 2009 10:17 PM

I'd like to find a good online resource that poses interesting computer science problems.

I've been digging through some of the modern classics papers of computer science research. Some are easy enough to understand with a little effort, others are pretty difficult to penetrate. I find that most of them are fairly difficult to find practical applications for.

I'd like to find a list of computer science problems, maybe medium to difficult homework problems for CS grad students. I'm not yet looking for grand challenges or problems big enough for a thesis. I don't want to do your homework, and I don't want to do your contract work either. I also don't want interview questions.

posted by b1tr0t to computers & internet (12 comments total)

Most CS courses at most major universities publish homework problems to their websites. Why not just pick a university, look at the course list, pick a course that sounds interesting and check out the problem sets? In some cases (most familiar to me is Stanford Engineering Everywhere) they even might post lectures and/or solutions and/or exams, etc.
posted by crinklebat at 10:24 PM on April 19

Have you seen Project Euler? The problems range from "moderately difficult" to "extremely difficult", at least by typical CS standards here in the US. Might be a good place to start.

The book "The Structure and Interpretation of Computer Programs" (SICP) contains a wealth of interesting exercises. The book itself is available here. There is also a wiki devoted to these exercises and their solutions.
posted by Maximian at 10:28 PM on April 19

SEE is pretty cool, but the CompSci courses they list look like entry level undergraduate stuff. I'm much more interested in upper division graduate problems.
posted by b1tr0t at 10:29 PM on April 19

Project Euler is also cool, and was the inspiration for my question. Most of the PE problems are more along the lines of number theory than computer science.
posted by b1tr0t at 10:31 PM on April 19

The Art of Computer Programming is famous for its exercises, which all have a number indicating their difficulty, ranging from easy to unsolved research problems.
posted by grouse at 10:45 PM on April 19

b1tr0t, not all the SEE courses are undergrad courses. Just the first three. I've only taken 223A, which was a tough class but not really what you're looking for (it was robotics, so lots of physics), but both 224N and 229 are more typical graduate CS courses which would typically have a good mix of MS/PhD students enrolled with a small representation of quite advanced undergraduates.

Seconding the Art of Computer Programming rec as well, especially if you can borrow it from the library for more than a few weeks...or afford it :) Either way.
posted by crinklebat at 11:13 PM on April 19

What kinds of things interest you? What do you like doing? What kinds of things do you want to be able to do?

Computer science isn't really a linear progression from neophite to real ultimate programmer. Once you get to a certain point, there are lot of branches and paths you can go on. There's 3d programming and simulation, there's AI/Machine Learning, there's high performance computing, there's language design and research, there's also mathematical theory of computation (where P != NP? comes from).

As far as my own free-time coding, I've always just come up with one huge-ass project, which is invariably abandoned at some point after spending a ton of time on it. Usually these projects involve learning something technology or skill I've never used before, so I learn a lot that way. When I was first starting out (like in high school) I would write simple demo programs, though.

Once you get to a certain point, though, you'll basically be able to code anything you can imagine. The challenge is expanding your imagination.
posted by delmoi at 1:58 AM on April 20

IBM Research's Ponder This ranges from pure math questions to ones that are far more like CS to my math/physics brain. Certainly some could be solved from that perspective. If nothing else, it's fun to flip through.
posted by Schismatic at 5:31 AM on April 20

The New Turing Omnibus
posted by alb at 7:26 AM on April 20

I'm not entirely clear what your asking, but routing is still an active area of research with both hardware and software solutions. All solutions are forced to make time/space/cost trade-offs.
posted by chairface at 2:50 PM on April 20

Have you tried the Python Challenge?
posted by media_itoku at 5:35 PM on April 20

Once you get to a certain point, though, you'll basically be able to code anything you can imagine. The challenge is expanding your imagination.

I agree - expanding my imagination is what I'm trying to do now.

I'm not entirely clear what your asking, but routing is still an active area of research with both hardware and software solutions. All solutions are forced to make time/space/cost trade-offs.

Routing could be an interesting space to play in, but I don't know enough about the space to set up tractable problems that also won't require setting up a cost-prohibitive lab.
posted by b1tr0t at 8:48 PM on April 20