Submission Information

Your project submission comprises two parts:
  1. Your code.
  2. Your writeup.
Once you have both parts completed, you should follow the instructions on submitting your project.

Your code

Your code should meet the following requirements:

Your writeup

Your writeup should cover the following topics, at least; you may cover more topics if you wish, but submit no more than (the equivalent of) five 8.5x11 pages total:
The identities of everyone in your project group.

A complete description of your data structure.
If you have simply used a data structure documented in the literature, just provide a reference to the appropriate book, paper, or WWW page. If you augmented a standard data structure, describe how your modified data structure differs from the standard one. If you improvised, then you have to tell us everything about it, as if you were teaching CS161, and we are your students, eager to learn even at 9:30am.

Note: if your data structure relies on some parameter (e.g. the cryptic p of skip lists, or a hash function), document how your code picks its value at run-time, or describe your rationale behind choosing a fixed value.

A complete description of your priority queue operations.
We know the interface already; what you should discuss is how the operations are implemented on your data structure. For example, if you augmented a standard data structure, you must explain how the standard algorithms need to be modified to maintain/use the extra information you added.

Tight asymptotic upper bounds on the running time of each priority queue operation.
You need not present detailed theoretical proofs - simple, reasonable arguments suffice. Make sure you distinguish between bounds on a per-operation basis, amortized bounds, and bounds on the expected running time of a randomized algorithm.

Best/worst case inputs.
What input (i.e. which sequence of priority queue operations and with what arguments) would cause each of your priority queue operations to exhibit their worst-case and best-case performance? Again, algorithms which bound the cost on a per-operation basis, whether deterministic or not, and algorithms which bound the cost over a long sequence of operations will need different analyses.

Comparison to other data structures.
In other words, why you picked the data structure you picked. Maybe the asymptotic running time of the priority queue operations? Maybe the low constants hidden under the O() notation? Maybe ease of implementation and debugging?

Pretend you own your brand new "CS161 Student Project Co." Silicon Valley startup and you want to convince us to buy your product. And we are a tad smarter than Dilbert's boss ...

References/credits.
If you used any papers, books, WWW pages, public domain code, etc. that we did not provide to you, please give credit where credit is due. Acknowledgments to people who helped you (aside from project partners and the teaching staff) are also welcome. In a nutshell, your writeup should be a short, not very theoretical paper, along the lines of (but simpler than) handouts 18-20, or chapters 7, 12-15 of CLR.

You may turn in your writeup in any one of the following formats:


Submitting your project

You should submit your project electronically; we do not want any hardcopies of code or writeups. Follow these steps to submit your project for grading:
  1. Log on an elaine.

  2. cd into your project directory and make sure that all the required project files/subdirectories are there.

  3. Execute
    /usr/class/cs161/project/bin/161submit
    

  4. Contact us if you encounter any problems using the submit script.


Here is a short FAQ regarding the submission process:

  1. Does each group member have to submit their common project separately?

    There should be only one submission per group. Individual group members need not (and must not) each submit the same project individually.

  2. My group made a few last-minute changes. Can we submit again?

    You can re-submit at any time before the official deadline. If you do, all the contents of your previous submission will be wiped out. This means you will be judged solely on your last submission, so be careful about making changes at the last minute.

    If your group comprises more than just one person, then all submissions must be made by the same person.

  3. How do I know whether 161submit completed successfully?

    Unlike some other submission programs you may have used, 161submit does not send out an email message notifying you of successful completion of the submission process. 161submit has done its job if it has executed without any errors, and if it lists all the required project files before it exits.

  4. What does 161submit do to my account?

    161submit just copies the scheduler.c, pqops.c, *.h, and documentation from your current directory into the class directory. It doesn't change any file or directory permissions in your account.

  5. Do I need to keep around my personal copy of the project directory after submitting?

    You may clean up your account, and eliminate all project-related files, anytime after submitting your work. However, we strongly suggest that you do not do so before the end of the quarter.