An uninflatable polyhedron
|
An uninflatable polyhedron |
· Home · Course Announcement · Schedule · Homeworks · References · Administrivia ·
Homeworks
- Homework 1, due February 23.
- Homework 1, due March 14.
InstructionsPlease typeset your homework solutions using LaTeX, with each numbered problem starting on a new page. You can submit your solutions either by emailing me a pdf file or by handing me a stapled pile of thinly-shaved, bleached, and slightly dirty dead trees.Each student must turn in his or her own solutions. However, I strongly encourage you to work together in groups. You may use any resource at your disposal—human, printed, or electronic—but you must not copy anything verbatim, and you must cite every source you use, including the other students you work with. Please cite your sources in enough detail for the reader to find them. In other words, follow the same standards of scholarship you would use for a research paper.
Stars indicate problems that I don't already know how to solve. The problem might be open, or I might just be missing something obvious. I do not really expect anyone to solve these problems, but I've been wrong before. Please make an honest attempt.
FiguresSince this is a computational geometry class, your homework solutions (and scribe notes, and project reports) will almost certainly contain lots of figures. I strongly recommend using a vector-graphics program that can export Encapsulated PostScript (.eps) or Portable Document Format (.pdf) documents.I use both OmniGraffle and Adobe Illustrator on my Mac; your advisor can buy Illustrator for $100 through the CITES Webstore. LineForm looks interesting, but I haven't tried it. InkScape and Ipe are both reasonable open-source programs that run on any platform. I can't recommend anything specifically for Windows (except installing Linux or buying a Mac).
To include .eps or .pdf figures in your latex document, add the line
\usepackage{graphicx}(yes, with an X) just after\documentclass{...}. Then the command\includegraphics[height=1.5in]{foo}includes the file "foo.eps" (if you compile with latex) or "foo.pdf" (if you compile with pdflatex), scaled proportionately to a height of 1.5 inch.If you prefer describing your pictures directly in your latex file instead of drawing and importing them, check out TikZ and PGF.
Submitted Project ProblemsNothing yet. Stay tuned!
About the Projects
Each student will submit an interesting, non-trivial, and preferably open problem related to computational geometry. Submitted problems need not be limited to the topics covered in class, but they must have some geometric 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).
Hey, wait! How do we find good problems?
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 her 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 computational geometry class web sites.
- 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.