(Relaxed) concurrent priority queues on multicore machines
Experimental comparison of efficient priority queues
Alias analysis in subquadratic time and space
Experimental evaluation of hashing schemes
Kinetic shortest path trees
Dynamic-finger and unified bounds for greedy binary search trees
Efficient integer sorting on GPUs
Fully persistent word-RAM predecessor search
Succinct data structures for one- and two-dimensional minimum range queries
Experimental analysis of competitive dynamic binary search trees for data compression
One month before the end of the semester, each student will submit a project proposal. Project proposals are due Friday, April 8. This is a hard deadline. Proposals should be 2-3 pages in length, and should include a crisp self-contained statement of the proposed topic, a brief survey of known results, a potential plan of attack, and one or two half-baked ideas that probably won't work but what the heck you might get lucky. After everything is submitted, I will post all submitted proposals to this web page as inspiration for final projects; however, the final projects themselves need not focus on any of the proposed topics.
The ideal result of the project is something that can be polished into a publishable paper. This ideal is meant to be an attractive goal, not an absolute requirement—not all research is successful! If you do not find a complete solution, your writeup and presentation should describe partial results (for example, incremental improvements for some interesting special cases), promising approaches for ongoing work, remaining questions where you're still stumped, and most importantly, ideas that initially looked promising but weren't (and why). I prefer creative failure to straightforward success. No, really.
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 Buffy the Vampire Slayer. 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 proposal deadline looming over their head. 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; more likely, 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 advanced data structures 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 commont 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.
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.