Overview of Requirements

Option A

• An email to me, selecting a data structure and partner, and stating a preference for Option A
• A 4 page paper discussing your data structure due by Friday, May 1st at Midnight

Option B

• An email to me, selecting a data structure and partner, and stating a preference for Option B (note that space is limited for this option, so email me a.s.a.p.)
• A 250 word abstract emailed to me by Friday, April 24, at Noon
• A 15 minute presentation on your data structure in lecture on Tuesday, April 28th or Thursday, April 30th

This lab is to be done with one partner. This does not need to be done with your usual lab partner. In fact, I recommend looking at data structures on your own and then finding a student with similar interests. You are welcome and encouraged to discuss ideas with anyone in the class (not just your lab partner), and team up to practice your presentations and provide feedback on your reports. Both partners are expected to contribute equally to the presentation and lab writeup

Introduction

Throughout the course, we we have seen several algorithms and structures for organizing and manipulating data. With each, you have built the foundations of your computational knowledge base that will aid you as you continue to mature as scientists. The constraints of a 14-week course limited the number of data structures we analyzed, as well as the variations and nuances of some that we did cover. The central goal of this course, however, was not to memorize every data structure ever invented. Rather, it was to develop the skills of analysis and design that are a prerequisite to becoming a skilled computer scientist.

For your last assignment, you will demonstrate these newly acquired skills by exploring data structures and algorithms that we did not cover in class. You have two options for fulfilling this course requirement. However, please note that there are limited spaces for Option B, due to time constraints. If you prefer Option B, please make sure to contact me as quickly as you can.

In Option A, you will write a medium-length paper which will discuss your chosen topic. Your report should introduce the topic, provide a motivating example, compare and contrast to a related course data structure, and analyze a few important operations. You will demonstrate not only your conceptual understanding of the topic(s), but also your ability to analyze algorithmic efficiency.

In Option B, you will provide a short abstract in advance of giving a 15 minute presentation in lecture during the final week of class. You will be evaluated on your communication skills in both the abstract and your presentation, so be sure to understand the motivation of using your data structure. I encourage you to make your presentation interactive; you will be evaluated on substance and your ability to explain the data structure to your classmates. Below, you will find a list of questions I and your classmates will answer to evaluate your presentation.

Choosing a Data Structure/Algorithm

The choice of data structure or algorithm to cover is largely open ended. But you must email me a brief description of your intended topic as soon as you have identified it. This should also include what you aim to discuss in your paper, written briefly and at a high level. You can use the book to find example data structures that we did not cover, or explore resources online. While Wikipedia is not a primary source, it is a reliable repository of data structures that can be easily explored and there are usually good examples.

Other resources include:

• Wikipedia
• A WikiBook
• Data structure books in the CS Main Lab
• The professor, the ninjas, or any CS prof. We all have some favorites.
• Google!

Some example data structures include:

• Skip Lists
• Tries/Prefix trees
• Bloom filters
• Ternary Search Trees
• Red-black tree
• Splay tree
• (2,4) Trees
• Treap (a combined heap/binary search tree)
• B+ Tree
• Fibonacci heap
• Probablistic graphs
• R-tree
• Cords
• BSP trees
• Radix trees

You could also do algorithms such as:

• Sorting algorithms
• Graph algorithms
• Huffman coding
• Hash functions

Paper Requirements

If you choose Option A, you will need to follow these guidelines. Your paper should be well-structured and follow scientific writing principles. You can structure as you see fit, but at a minimum, your paper should include:

• An introduction - this can include a history and a preview of the central features of the data structure/algorithm
• Motivation - what is the problem that needs to be solved? It is recommended that you come up with real-world application and describe it here.
• Background/related work - what does this relate to from class? What are the conceptual differences? Are there other algorithms/data structures that generally compete with your choice?
• Interface - what are the major operations of the data structure? This may not apply for an algorithm, but you discuss assumptions for the structure of the data.
• Illustration - walk through an example (e.g., for BFS, going from Parrish to the Ville). You should have some sort of diagram that illustrates how the data structure/algorithm works.
• Analysis - provide pseudocode for a few key operations and analyze their run time. This does not need to be exhaustive, and how many operations you cover depends on the complexity of the problem. For example, inserting/removing from linked lists was fairly simple so it would be good to cover most of the methods. Removing/inserting into an AVL tree is quite complex, so be sure to limit your discussion to one or two key operations. You should then summarize the other operations.

Your paper should be typed; no hand-written writeups will be accepted. The exception is with illustrations, which can be neatly drawn and attached to your writeup. I would prefer you scan and attach the images to your PDF document, if possible. It may be useful to learn to use LaTeX, a popular typesetting system that is used widely for writing scientific and mathematical papers. If you are interested, feel free to email me any questions about this. You can also find a primer and some sample guides online, including here or here.

In terms of the length of your writeup, it is really up to you to judge how much material adequately describes your data structure/algorithm. Your writeup, excluding figures and references, should not exceed 4 pages using single spacing, 11 point font, and 1 inch margins.

Presentation

If you choose Option B, you will need to follow these guidelines. You will present your findings in a short presentation (maximum 15 minutes) during lecture in the final week of class. I strongly recommend practicing your presentations with others. Selected students and I will evaluate your presentation on the following criteria:

1. Rate the introduction/motivation for the material
2. How effective was the presenters sample illustration in conveying the high-level features of the data structure/algorithm?
3. Overall, how effective was the presentation in explaining the data structure or algorithm?
4. Briefly, describe the strongest part of the discussion
5. Briefly, list one thing the presenter could improve upon to help you understand the topic better

You will also be required to submit a 250-word abstract in advance of your presentation. Like full papers, abstracts should also be structured to include motivation, background, interface and analysis. Length requirements will obviously constrain the depth of coverage in each of these areas.

Logistics and Tips

• You are permitted to use powerpoint/slides if you like. But if you choose to use any visualization requiring a projector, you must let me know ASAP. Also, you should show up a few minutes early to set up your laptop.
• Some students in the past have provided a worksheet to help in their presentation, or to supplement their presentation with more details that had to be omitted due to time.
• Be sure to practice your talk! 15 minutes goes by much faster than you'll expect.
• Do not try to cover every aspect of your topic. A clear, coherent paper or presentation about certain interesting aspects of your topic will be better than one that attempts to be completely comprehensive.
• A good strategy might be to concentrate on one sub-problem and give a high-level intuition of other topics.
• Be sure to think of a good example/illustration - this is the best way to help your peers understand the data structure in a short amount of time.