Home
Syllabus
Classwork
I will assign you a partner with whom to work on this project,
and I'll assign a topic to each pair.
With this other student, you will research the topic,
and you will write a paper and present a 25-minute informal class
lecture
discussing what the problem is, why the problem is
important, what the algorithm is, why the algorithm works, and
how well the algorithm performs.
| presenter | partner | topic | day |
|---|---|---|---|
| Geren | Haynes | Mapping with a pebble | Wed 25 Mar |
| Johnson | Sneeringer | Three-dimensional hull | Wed 25 Mar |
| Maguffee | Attaway | PageRank | Fri 27 Mar |
| Demmler | Weighted majority | Fri 27 Mar |
Send e-mail to 
with
two items:
List three topics from the below list that look most interesting to you. I'll assume that you are listing the topics in order of your preference. Please note that it will not be possible for me to accommodate all interests, but I'll take your expression of interest into account. Also note that your topic preference will not influence who your assigned partner will be.
If there are students with whom you do not want to work on this project, you may express this. Note that, in this course and others, any expression of such a preference reflects poorly on your own maturity and teamwork ability — worse than it reflects on those you'd rather not work with. Nonetheless, sometimes the animosity is bad enough that it should be expressed. This will be kept confidential. Again, there are no guarantees that I can accommodate all preferences.
As mentioned on the syllabus, I'll take class performance into
account when assigning partners. (I'll also tend to assign more
interesting topics to teams that have more potential to do a good job
with them.) In general, I'll try to avoid assigning a team that seems
highly unbalanced with ability level. However, it will be considerably
more random than simply ranking
students and picking off the
first two for one group, the next two for the next, and so on.
The length of the paper should be roughly four single-spaced pages, and it should be presented at a level that a student who has taken a regular Algorithms course would be able to understand (without having heard your presentation!). Please see the evaluation criteria below for more of an idea of what this is.
Possible topics for both the paper and the presentation include: describing the problem being approached, explaining why the problem is important, presenting the algorithm, arguing why the algorithm solves its problem, and analyzing how well the algorithm performs.
The paper should be submitted electronically, in OpenOffice.org Writer or Microsoft Word format.
One person from your team has been selected to present a lecture of 20 to 25 minutes about the topic. This lecture should be relatively informal, allowing students in the classroom to ask questions.
Yes, even though just one person will speak, both people on your team will receive the presentation score. The other person should still be involved, both in helping to design the presentation and in providing constructive criticism during practice.
If you are not the presenter for Project 1, you will most likely be a presenter for Project 2.
Instructions about what should be modified within the paper will be provided when it is returned.
Possible topics include the following.
How can we identify the relative importance of pages on the World Wide Web? Google uses the PageRank algorithm, which was first developed by an algorithms researcher.
Suppose that we have to bet on whether a stock
will go up or down each day. We have a set of experts
who
each make an independent prediction, but we don't know which
expert is most reliable. How can we combine these expert
predictions into our own prediction each day so that we don't
make many more mistakes that the best expert does overall?
The
weighted-majority algorithm is a simple and effective
algorithm for doing this.
We have two DNA sequences, and we want to find substrings of each that are the most similar. One classical algorithm for this is the Smith-Waterman algorithm. It's based on the edit distance algorithm we saw in class.
Given a string named haystack and a much smaller string needle, we want to find the first appearance of needle within haystack. The Knuth-Morris-Pratt algorithm is an efficient algorithm for this problem.
Given a set of n points in three-dimensional space, we want to find the smallest polyhedron containing all points in O(n log n) time. This polyhedron is called the convex hull. There is a divide-and-conquer algorithm to do it; the best algorithm, though, is Chan's algorithm.
Suppose you are in a maze represented as a graph, and you want to develop a map of the maze by exploring it. Individual vertices are indistinguishible, but you are equipped with pebbles, which you can drop on a vertex so that you know when you've arrived back. This problem was explored in a 1991 article by Dudek, Jenkin, Milios, and Wilkes.
Below is the point breakdown for the project. The questions accompanying each give examples of what the point category represents; the questions are not meant to be exhaustive, though.
| 40 pts | Paper: Research. Is there evidence that the paper is based on studying the subject thoroughly? Are explanations at a sufficient level of detail? Does the paper use mathematical argument where appropriate? Are all such arguments both accurate and as easy as possible to understand? Does the paper cite sources appropriately? |
| 20 pts | Paper: Overall structure. Does the paper present enough information that it would make sense to a reader unfamiliar with the subject? Is the structure of the paper apparent? Does the paper provide good examples when appropriate? |
| 20 pts | Paper: Sentence-level writing. Does the paper use good grammar and spelling? Does it demonstrate a consistent attention to using the most appropriate words? Does the paper address the reader that draws in the audience while simultaneously remaining professional? |
| 10 pts | Presentation: Visual aids. Does the presentation use the chalkboard or computer presentation when appropriate? Is the visual hint genuinely helpful to the audience? Is all text readable throughout the classroom? Is the presenter doing much more than simply reading visual aids? |
| 15 pts | Presentation: Organization. Is the organization apparent to the audience and suitable to the subject? Does the presentation use the designated time without going over? Is the time used consistently in an effective manner? Does the presentation impart detailed information that is appropriate for inclusion on later tests? |
| 15 pts | Presentation: Qualities of address. Does the speaker show evidence of being prepared? Does the speaker maintain eye contact, avoid nervous tics, and speak audibly? Does the speaker avoid rehearsing prepared text from notes or memory? Is the tone of voice conversational but still professional? |
| 30 pts | Paper revisions. |
| 150 pts | TOTAL |