S-Q 1997 - Graduate Paper

Proposal - Due 07/24/97 at 6:00pm

Paper - Due 08/07/97 at 6:00pm

Late Papers Will Not Be Accepted!

Overview

The goal of the final paper is to have you investigate a topic that you find interesting.

The amount time you spend on the final paper should something in the neighborhood of one-half the time required by one of the homework assignments- it should take some time and thought, but it is not meant to be a tremendous undertaking. The paper should be no longer than 5-10 pages, single-spaced, with supporting figures and illustrations (depending on the nature of your subject, more or less may be appropriate). Depending on the nature of the topic you choose, it may also be appropriate for you to write a small amount of code to implement the ideas in your paper.

Deadlines

Before beginning your paper, you must hand in a short proposal so that I will know what you are working on and so I can make sure that your topic is appropriate. The proposal deadline is 6:00pm on 7/24. If you are not sure what topic you want to write about, I strongly urge you to talk to me before that date! Late proposals will be docked 10% per day, up to a maximum of 50% of your grade on the final paper.

The final paper itself is due at 6:00pm on 8/7. Please note that late papers will not be accepted without prior permission.

Topics

I would prefer that you choose a topic that interests you, but if you cannot think of any, I can suggest several. For example, any of the following would make good paper topics:

1. Write a complete and detailed algorithm for non-lazy deletion from an AVL tree. Show that it never requires more than steps to delete any node.
2. Write a complete and detailed algorithm for deletion from a 2-3 tree. Explore strategies for keeping the tree relatively ``full'', to avoid wasting space in relatively empty nodes.
3. Consider using the Lempel-Ziv compression algorithm to compress bit streams instead of byte streams, using a binary trie. Does this offer any advantages over an ordinary trie? Is the compression as good, or better? Is it faster or slower?

About this document ...

This document was generated using the LaTeX2HTML translator Version 96.1-h (September 30, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 finpap.tex.

The translation was initiated by Dan Ellard on Tue Jul 15 08:48:03 EDT 1997