CS35: Written Report on a Data Structure or Algorithm

Overview of Requirements

This lab is to be done individually. But you are welcome and encouraged to discuss ideas with anyone in the class, and team up to practice your presentations and provide feedback on your reports. I strongly recommend practicing your presentations with others.

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 13-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 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.

Accompanying your report will be a 10 minute presentation in lab on Monday, December 10, 2012. You will be evaluated on your communication skills in both the report 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 send a short paragraph explaining your plan by Friday, November 30. This should include the topic you plan to cover and what you aim to discuss in your paper. 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: Some example data structures include: You could also do algorithms such as:

Writeup Requirements

Your writeup should be well-structured and follow scientific writing principles. You can structure as you see fit, but at a minimum, your paper should include:

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. If you run update35, there are some example tex files in your cs35/class/12/ directory.

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, should not exceed 5 pages using 1.5 spacing.

Presentation

You will present your findings in a short presentation (maximum 10 minutes) during lab on Monday, December 10. You will be divided into groups of 4-6 students with one discussion leader (either myself, a ninja, or Frances). Each student in your group as well as the discussion leader 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