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 and algorithm.
| presenter | partner | topic | day |
|---|---|---|---|
| Sneeringer | Maguffee | Delaunay triangulation | Wed 22 Apr |
| Haynes | Johnson | Shortest superstring | Wed 22 Apr |
| Attaway | Demmler | Karger's algorithm | Fri 24 Apr |
| Geren | Edge coloring | Fri 24 Apr |
.
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.
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.
Instructions about what should be modified within the paper will be provided when it is returned.
Possible topics include the following.
Given a set S of two-dimensional points, their Delaunay triangulation is a set of line segments connecting the points and partitioning the space into triangles, where the only points in S within the smallest circumscribed circle around each triangle are those three points defining the triangle. In this project you'll describe and analyze a relatively efficient algorithm for computing a Delaunay triangulation.
Given an unweighted, undirected graph, we want to partition its vertices into two sets so that the number of edges between the two partitions is as small as possible. This is called its minimum cut. One interesting algorithm for this problem is Karger's algorithm; it uses randomness and probability to arrive at a correct answer with reasonable probability. Your project would be to describe and analyze this algorithm.
In the shortest superstring problem, we're given a set of strings and we want to find the shortest string that has each of the given strings as substrings. For example, given abc, cde, and eab, the shortest superstring is cdeabc. One important application of this problem is to DNA sequencing, where we have many segments of a DNA strand and we want to determine the original DNA sequence. The problem is NP-complete. You should describe a constant-factor approximation algorithm for the problem. You might also show that the original problem is NP-hard.
Instead of coloring vertices, we want to color edges with as few colors as possible, so that no vertex has two edges of the same color. This problem is also NP-complete, but there is an algorithm due to Vizing that never uses more than one color than necessary.
We have m identical machines and we receive a sequence of jobs, each with a known duration. We want to assign each job to a machine with a goal that the time taken is close to the best time possible. There is a greedy algorithm that takes at most 2 - 1 / m times the optimal schedule. Your project would prove that this algorithm is correct and outline other results for the problem.
Given a context-free grammar and an input string of n characters, the CYK algorithm determines whether the input string can be produced from the grammar in O(n³) time. You would present the algorithm, including the required preprocessing needed to bring an arbitrary context-free grammar into Chomsky normal form as required by the grammar.
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 |