A majority of the grade in this course is a two-part final project. The basic requirements of the project are quite open-ended:
The precise form of the project is also open-ended; here are a few possibilities:
Students are strongly encouraged to work on projects motivated by their primary research/development interests and to collaborate outside their teams, with anyone in or out of class (with proper credit, of course). In particular, project topics need not be limited to the specific topics covered in class, as long as they relate to both algorithms and embedded curves and/or graphs. Especially for theoretical projects, you should work on problems whose solution you want to know but don't.
The ideal final outcome of the project is a publishable result. Any student who publishes work from this class in a peer-reviewed conference or journal will automatically get an A+. This rule can be (and has been!) applied retroactively for several years after the course ends.
However, it is not reasonable to expect to obtain publishable results on any problem after only one or two months of effort, especially in a new area. Thus, most final reports will describe the team's incomplete progress toward a solution. This progress can take several forms: a thorough literature survey, a complete solution for some interesting special case or necessary lemma, a plausible plan of attack, counterexamples that killed a seemingly plausible plan of attack, conjectures backed by experimental evidence, interesting approaches that didn't pan out, ideas that seemed smart at first but turned out to be stupid, and so on. You know, research. Creative failure is better than straightforward success. Yes, really.
Excellent question! Here are a few hopefully useful suggestions. This list is nowhere near exhaustive, nor will every suggestion work equally well (or at all) for everybody. If you have other ideas for finding good research problems, I'd love to hear them!
Professors are people. This is a very hard lesson for many graduate students to learn. Yeah, okay, professors are insanely busy people and (hopefully) internationally recognized experts in their research areas. So what?! One of our jobs as faculty is to help graduate students grow into mature, independent researchers. You have every right to expect, even demand, our attention and our help. You are our colleagues—not our employees, not our children, not burdens to be grudgingly endured, but our colleagues. Less experienced, sure, but colleagues nonetheless.
Try treating us as senior colleagues, not as arcane wielders of unspeakable power over your Entire! Academic! Future! We love to express our opinions to interested people, we have lot of bizarre half-baked ideas, we're scared of talking with experts, we make stupid mistakes and bluster to cover them up, we're embarrassed when we forget names, we feel like frauds for our success. We like juggling and/or Russian literature and/or abstract expressionism and/or Belgian beer and/or Adventure Time. Really, we're just like you, only older and better looking.
Talk to faculty in person if at all possible. Knock on office doors; say hi. If you've never talked to that prof before, or if the prof looks confused when he sees you, introduce yourself. (Don't be discouraged if you have to introduce yourself several times. Professors deal with hundreds or even thousands of students a year.) If a prof doesn't have time to talk when you drop by, ask to set up an appointment. If you don't find a prof in their office after several attempts, ask for an appointment by email. If they never have time to talk to you, don't take it personally—they probably have a looming proposal deadline. Ask for suggestions for someone else to talk to. If they're not even willing to give you the time of day, leave a burning paper bag full of dog poop outside their office door, knock, and run away. No, on second thought, skip the dog poop; just talk to the prof next door instead.
Don't worry about whether you have anything to contribute or whether your questions are stupid, especially if you're just starting out in a new area. At some point in your life, you will ask stupid questions, you will fall flat on your face, you will embarrass yourself, just like everyone else does. But probably not today; it's just as likely that the question that you think is stupid is exactly the right question for you to be asking. It's not reasonable for anyone (even you) to expect you to know everything the first time you, well, ever. Trust me, by the time you finish your PhD, you'll be shaking your head in dismay at your professors' ignorance.
Specifically, if you are a UIUC student, especially if you are taking this class, talk with me! I'm in or around my office most afternoons. If my door is open, just knock and say hi. If I'm meeting with another student with the door open, feel free to listen in. If I'm not in my office, send me email. Do not under any circumstances leave flaming bags of poop outside my office door, or I will wield my unspeakable power to destroy your Entire! Academic! Future! Also, I don't actually like Russian literature.
If you're not a UIUC student, please talk to faculty at your own institution. You should only email questions to me at the advice of your own professors, or if I (should) already know you professionally.
Solve lots of problems. Ultimately, the only way to learn how to find good problems, and to learn how to solve them, is by actually doing it. Pick a problem. Try to solve it. If you succeed, what other problems does your solution suggest? What other problems seem likely to fall to your solution technique? If the solution was too easy, tweak the problem to make it harder. If you get stuck, try to formalize why you're stuck; you might be trying to do something impossible! Or tweak the problem to make it easier—consider a useful special case, or ignore the cost of some pesky operation. It's relatively rare for any open problem to be solved in its original stated form; more often, the problem and its solution evolve together as the research progresses.
Read a lot. Many research papers end with a laundry list of open problems. Even if there's no explicit list, very few papers describe results that cannot be improved in some way: efficiency, generality, elegance, or all of the above. Look especially for the questions that nobody is asking! Reading papers is not only a good source of problems, but also the best way to understand what people already know, what people care about, and what people expect in a research publication. For this class, I'd suggest starting with papers discussed in class, or in other computational topology classes.
But don't just read papers. Read books. Listen to talks. (If the speaker doesn't volunteer any open problems, raise your hand and ask for some. And what's the obvious corollary for when you give talks?) Read (and leave comments on) theory blogs. Read (or better yet, post to) TCS Stack Exchange.
Tweak an existing result. If the best algorithm is randomized, can you get the same performance deterministically? If the best algorithm is deterministic, is there a simpler randomized solution? Can you efficiently maintain the solution as the input changes? Can that constant 5 be changed to 10000, or το 1+ε? What if you have to pay for individual bit operations? What if you can perform rotations for free? What if you only care about cache misses? Can you solve the same problem for sets of strings as efficiently as for sets of numbers? What if the points are moving? How good an approximation can you compute in linear time? In sublinear time? What if you're only allowed to scan through the data once? What if you can only use constant space or constant time? What if you use ellipses instead of circles? Does it work in higher dimensions? Can you run the algorithm backward in time? In parallel? What if the computer can lie to you occasionally? Can you turn the problem into a game? What if the nodes have colors, the edges have negative weights, the disks are magnetized, the strawberries taste like strawberries, and the snozzberries taste like snozzberries? Don't worry (at first) about whether your questions make sense, or if they're impossible, or if they're trivial. The goal is just to come up with questions.
Embrace the confusion. Often you'll find yourself faced with that looks like a simple variant of a well-understood problem that inexplicably resists you attempts to solve it. The more you think about the problem, the more confused you get. You're on the right track! That feeling of confusion and stupidity is actually a sign of progress; it's just your brain resisting letting go of its comfortable ignorance.
Wander around at random. Start with an interesting paper. Look up other papers cited in its bibliography. Find the paper on CiteSeer or Google Scholar and look at newer papers that cite those. Go to the authors' web pages and look at their other papers. Google for an interesting phrase or an unfamiliar piece of terminology. Look at other papers in the same journal or conference proceedings, or on the same shelf at the library. (You remember, that big brick building with all the books?) Repeat ad nauseam.
Write everything down. Keep a research notebook with you at all times. (I strongly recommend paper over anything electronic, but use something you feel comfortable with.) Whenever you see, read, hear, or think of something even remotely interesting or relevant to your research, write it down. Especially write down half-baked ideas and "stupid" questions. Periodically read through your own notes; you'll be surprised at how much stuff you see (and think of!) in a single year. As you mature as a researcher, the content of your notebook will slowly will drift away from ideas you get from other people and toward your own thoughts and discoveries.