- Homework 1, due March 16.
- Bill Kinnersley: Maintain the arboricity of graph—the minimum number of edge-disjoint forests that cover the graph—as edges are inserted and deleted.
- Chris Osborn: Maintain a heap-ordered forest under the operations CUT, LINK, and MERGE in O(log n) time per operation. The MERGE operation merges two paths (specified by their deepest nodes) into one path, maintaining heap order.
- Dongyun Jin: Dynamically maintain the (approximate) product of two matrices A and B under operations that change an arbitrary(?) sparse subset of the entries of A or B.
- Hemanta Maji: Preprocess a set X of points in convex position in Rd, to support queries of the following form: Given a point p and a halfspace h, which point in X∩h is furthest from p?
- Joe Elble: Maintain a maximum-weight matching in a weighted (bipartite? planar?) graph, under operations that change the weight of an edge.
- Ke Chen: Maintain the largest element in an n×n integer matrix, subject to operations that increment or decrement an arbitrary horizontal or vertical segment (that is, some portion of a row or column), in o(n) time per operation.
- Kyle Kloepper: Distributed, timestamp-approximate, and/or retroactive retroactivity.
- Nick Wondra: Develop tight bounds on the quantum complexity of spatial search, along the lines of Grover's optimal O(√n)-time search algorithm.
- Nitish Korula: Kinetically maintain an approximate minimum spanning tree, or an approximate Steiner forest, in a graph with continuously changing edge weights.
- Phil Mienk: Kinetically maintain the connectivity of a set of moving disks of different (changing?) radii in the plane.
- Reza Zamani Nasab: Support k-edge-connectivity queries in a semi-dynamic graph as vertices and edges are added.
- Tracy Grauman: Kinetically maintain the convex hull of a set of continuously moving points in 3-space.
Each student will submit an interesting, non-trivial, and preferably open problem related to data structures. Submitted problems need not be limited to the topics covered in class, but they must have some data-structure content. Experimental problems and problems related to your own primary research area are especially welcome. Above all, it should be a problem who solution you want to know but don't.Before the end of the semester, teams of up to three students will submit solutions for a small subset of the submitted problems, preferably excluding their own. Students are encouraged to collaborate with anyone in or out of class (with proper credit, of course). Each team will also give a short oral presentation of their results.
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, promising approaches for solving the problem(s), and ideas that looked promising but weren't (and why).
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!
- Talk with people. This is probably the single most important suggestion I can make. Other people have ideas, intuition, and experience that you don't; just as importantly, you have ideas, intuition, and experience that other people don't! Tell other people your half-baked ideas and listen to theirs. See if they know how to solve your random questions, and try to answer theirs. Ask for suggestions for papers to read, or techniques to try, or problems to think about, and offer your own in exchange. If you're really lucky, you'll find that you have enough background in common to work together. Great!
- 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.
- 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 2 be changed to 10000, or vice versa? What if you have to pay for individual bit operations? What if you can perform rotations for free? 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? 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, and the snozzles are greebly? 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.
- 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 structure classes.
- Listen to talks. Same thing. If the speaker doesn't volunteer any open problems, raise your hand and ask for some.
- 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 know, that big brick building with all the books.) Repeat ad nauseam.
- 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 will evolve together as your research progresses.
- 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.