Thursday, May 14, 2009

A Problem Archive?

Having just gone through the painful process of making up my final exam (again), I'm inspired to think that there must be a better way. We should have a problem (and solution) repository so professors/instructors can easily find a collection of problems to borrow from or to use as a creative inspiration. It would be nice to be able to say, "I need a dynamic programming problem, a linear programming problem, and an approximation algorithm problem..." and go to one place to start getting ideas. (Right now, all of you that keep your exams online, I'm probably cribbing from you, thanks to Google... I notice more of you are keeping such info password-protected than a few years ago...)

I (obviously) haven't thought much about how this would work in practice, so consider this an open discussion. Of course, there's the problem of keeping such a repository protected from student eyes. Ideally, actually, perhaps we'd have a student site (unprotected) and a faculty site (password-protected). Would you use such a site? Would you contribute problems to it? What sort of incentives would make such a site work? What other uses (besides making up exams and problem sets) could such a site be good for?


RME said...

One idea about keeping the repository protected from students: if the repository is big enough (let's say a few hundreds problem) and the exam is closed books then there is no point in protecting it. If the students spend time and do all problems beforehand then they will be well prepared anyway. :-)

Anonymous said...

Following the above comment: at where I went for undergrad, a student group keeps a database of most EE and CS exams from past quarters online, which is publicly accessible. (
I found this to be a win-win strategy for both students and the faculty. For students, they had more resources to prepare for exams (thus enhancing their learning experience) and it prevented the faculty from simply reusing old exams. Often new exam questions were good variants of old questions, different enough that you had to understand the concepts well to answer them, so I bet the faculty used the repository as a "creative inspiration." So I'd say a public repository is a nice thing to have.

Suresh Venkatasubramanian said...

If I'm not mistaken, Bill Gasarch had an archive of this kind, categorized by problem type. I even think I used some problems from there.

David Andersen said...

I maintain one for use within a smallish group of faculty at CMU and a few external folks. It's been very handy, though it turns out to be difficult to organize problem variants, etc., in a coherent way. I think you have to keep it smallish and commit to adding new problems to it frequently, though.

If you ever need any networking problems, let me know. :)

Anonymous said...

I agree with RME. Why protect the repository from students (especially the solutions)? The students can use the solutions to check their work. One of my pet gripes with theory classes while I was a student (grad and undergrad) was that there was no large collection of solved problems that could be used to prepare for exams.

FYI, some of the classes in OCW ( have exams, some also with solutions.

such.ire said...

This obviously isn't from the same field, but David Evans, an organic chemistry professor at Harvard, has been keeping a database of problems from his courses and a few other professors' on his website. The database was open to all students, though getting solutions required an extra bit of effort (an email link), so while it was a valuable study resource for the student, there wasn't an easy way for the student to just vacuum the knowledge into their head for direct regurgitation on tests. Not only that, but the system encouraged the student to spend some effort to try to solve the problem instead of simply reading "question-answer" scripts.

Obviously, a really determined student could compile all of the solutions, but as the other commenters stated, most of the time it wouldn't have helped more than just studying anyway.

Anonymous said...

I think it is really important to have access to a large database of problems with solutions to learn material and also see what clear, correct solutions are.

In undergrad, I took an algorithms class in which the TA handwrote the solutions and then distributed photocopies, which were just hard to understand/read. I recall going to the MIT algorithms class site, which at the time was world accessible, where I could access several years worth of homework problems and solutions that were much better written than what I obtained from my course. It really helped me writing/learning proofs or correctness for algorithms, which was a very new topic for me. I attribute my success in the class purely to these extremely high quality materials that were available from the MIT website.

Michael Mitzenmacher said...

One concern I have about giving students access to a repository (with solutions) is that many theory problems are about thinking about the problem the right way, and then the problem is easy. "Oh, I have to turn this into a maximum flow problem, then I'm done." It can take a lot of work to frame a problem, but not so much to solve it, and many of the interesting problems are NOT examples of a rote procedure. In this way, I think CS theory is different than many other ares, and giving out solutions can make a problem worthless, in that it's hard to design variations.

That is, I'm happy to have an archive with examples of max-flow problems or how Euclid's algorithm works -- I can always change the numbers, and the point there is for the student to understand the algorithm. I'm less happy about, say, a repository with solutions to all the standard dynamic programming problems -- there really are a limited number of really good dynamic programming problems. And I'd never put up solution sets for my programming exercises -- good programming exercises are hard to come up with!

Somewhere, there's a balance between making information available to the student (helpful) but keeping a good supply of (challenging) problems available for examination; I'm not sure where that balance is.

Anonymous said...

Perhaps there is another way to approach your question.

Do you consider your class a place where people can learn how to frame algorithmic problems, or should they already know how to do that? If the latter, what class (at your university) is good for this? In my experience, a data structures class does not provide this background. A discrete math class may provide this background, but not all schools offer such a class (and they can't or don't cover all of the relevant and useful topics).
So for some students, there is a gap between being able to, say, understand what an algorithm does, and to prove or argue a variety of things about it (correctness, time/space complexity, etc.).

Some people call this gap "mathematical maturity", so in a sense, I suppose I'm asking how students can acquire mathematical maturity (at least with respect to the branch of mathematics in question) in such a fashion that they can feel some confidence in earning a good grade in a class that requires it, as opposed to having the class "debug" their mathematical maturity. (For an example of what I'm talking about, see a discussion on my journal about why engineering is difficult. I realize this is a highly debated topic, but am interested in your thoughts, e.g. how did you acquire enough MM to get through your orals, etc.

What I'd like to see accomplished by making solutions available is that students won't just flail helplessly being stuck on certain problems, losing valuable time that they need to cover material for other classes, etc.

Anonymous said...

In order to advance the mathematical art, problems and their should be made available. If a student memorizes the solution to 500 problems, does he then gain an unfair advantage over his peers in solution of the Riemann hypothesis or in understanding the values of the zeta function at odd arguments or in settling P=NP?

The advice to students never to look at solutions before attempt to solve a problem is exactly reversed for researchers: always look at the solutions before attempting to solve a research problem.

Educators have to manage three kinds of cognitive load: intrinsic, which measures the degree of interrelatedness between items; extraneous, which interferes with learning by cluttering short-term memory (think of that biography of Riemann in the sidebar of any calculus text); and germane load, which leads to the formation of schemas (long term memories which aid in perception, thinking and problem solving).

Having a library of solved problems available would help to reduce the cognitive load of students and researchers. Instructors keep problem solutions secret because they do not want to have to change their comfortable routines.