In most classes, the instructor teaches you the techniques to work a specific problem, and then expects you to use those techniques on the exams and the homework. But what do you do when you go out into the real world? Where problems have vague specifications? Where there is more than one way to solve a problem? Where you run into problems you have never seen before.
That's where this course comes in. This is a course about problem solving. There is no set content to cover and specific techniques to learn. We will cover what we will cover. Instead this course will focus on one thing: developing the skills and confidence to tackle unfamiliar and difficult problems.
Many of the problems that we will see in this course will be on the style used in job interviews or programming competitions. In other words, they will not necessarily be applied, but they will tricky and fun. The exact nature of the problems that we will encounter will depend upon the diversity and background of students in the class; the content of the course will adapt to match the abilities of the students. However, the following is a list of some of the areas we might take problems from:
Some of this may seem vague, while some of it may seem unfamiliar. That's the point. I don't expect you to have seen how to do any of this stuff. The only requirements for this course are CS 211 and CS 280 (though you can get away with taking 280 concurrently with this class). With that said, advanced students are still welcome. There are enough challenging problems for everyone.
There is no text for this course. This is a student discussion course where we solve and discuss problems in class. The course is taught discovery style, meaning that I will not tell you how to solve any problems. If you cannot solve a problem, my duty as an instructor is simply to give you easier "hint problems" until you are capable of solving it on your own. While there will be some lectures in the class, it will always be after a problem has been solved, summarizing the techniques that we just discovered.
A typical class day may contain any mixture of the following activities
As demonstrated by the last bullet point, many times there will be debate over whether a particular solution is correct. All students should abide by the rules of classroom etiquette when critiquing a solution.
In trying to solve problems, you may come up with new problems on your own. You are welcome and encouraged to submit new problems to the class. Solutions to your new problem will receive credit equal to any instructor-assigned problem of the same difficulty. In addition, you will receive credit for posing the problem regardless of whether or not you are able to solve it (We don't call Fermat's Last Theorem, Wiles' Last Theorem, do we?).
Come join us. Tuesday and Thursday 11:40-12:55 in the ACCEL Orange Room of Carpenter Hall.
Because this is a discussion course, we will there will be a Wiki for this course. Everyone in the course will have access to the Wiki and be able to post solutions, submit ideas, and/or observations. Like any other Wiki, think of it as a web site that the entire class has access to. We will be the first class at Cornell to test out official Wiki support from CIT, and so I am still not exactly sure how we are going to utilize it. We will talk about this more in class.
Based on my previous experience in this class, the purpose of the course Wiki is two-fold. First of all, it gives us a place to post all the solutions. Students from the last semester really enjoyed comparing the different programs and learning techniques from one another. Previously, students would send the solutions to me and I would post them. With a Wiki, you can post the solution yourself. You can even take it down if you want to retract your solution (i.e. you no longer believe that your solution is correct). However, a solution must remain posted if you are to retain credit for it.
As with last semester, there is some concern over privacy and the posting of solutions. Not everyone wants code they wrote their sophomore year posted so that Google can whip it out in their interview a few years later. As this is the first class at Cornell to have an official Wiki (and not just one on a departmental server), there has been some discussion about this. Currently, we have two options:
The second purpose of the Wiki is to keep a journal of our daily activities. Once again, this course is about how we come up with solutions, not the solutions themselves. Therefore, it often helps for us to keep a list of all the things that we tried to do to solve a problem, but which did not work out. In the past, each day I assigned a person to write this up, e-mail it to me, and post it online. As a result, by the time the journal was actually posted, we had moved on to the next problem. No one ever read them! By using a Wiki I hope for us to get this information online faster. Again, we will talk about this more in class.
This is a course about problem solving. A lot of times there is a "trick" to a problem, and so when it is solved, the solution is obvious to everyone. Thus we make the distinction between open problems and closed problems. A closed problem is one that is solved and the solution has been presented by a student in class. No one can receive credit for a problem after it closed, as the any solution would be a minor variation of the solution already presented. In a few cases you may be able to get credit for an alternate solution to a closed problem, though you should get permission from the instructor before working on a closed problem.
An open problem is any problem that is not closed. Anyone may work on any open problem at any time. There are no deadlines to working on an open problem other than the fact that it may become closed. Hence it is your best interest to work on a problem early so that you close it before another student does. As a result, this course will be one of friendly competition. I do reserve the right, however, to deny specific open problems to a student or to "hold back" a solution I know is correct in order to give other students a chance.
As the course progresses, what constitutes a closed problem will become more vague. If the class does not adequately examine the solution to a problem, I will allow them to think that it is closed when it actually is not. Thus a closed problem can again become an open problem if a student demonstrates that the supposed solution is incorrect.
To allow this is level of introspection, at all times I will make available the list of open problems, as well as the list of closed problems with their solutions. At any time you can look over the solution of another student and try to demonstrate that it is not correct. Alternatively,
Both the list of open problems and the solutions to closed problems will be made available on the course Wiki.
Cornell University Department of Computer Science
Last Updated: August 18, 2006