Submission Information

Your project submission comprises two parts:

Your code.
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:

It should compile and execute - producing correct results - on an elaine, and using the Makefile we supply. This means the only *.c files should be pqops.c and scheduler.c. You can create any *.h files you find necessary.
Aside from comments, it should only contain code potentially invoked by your priority queue implementation. So if you defined any auxiliary functions for debugging purposes - such as a function that prints your data structure - or if you have interspersed assertion statements in your code, please remove them or comment them out before submitting.
It should be documented well, with in-line comments and well-picked identifiers.
Comments should not point out the obvious, as in
```
  i=j;   /* Set i to have the same value as j. */
```
Nor should they cover high-level material discussed in the writeup. Instead, they should provide the conceptual bridge between algorithm and code.
Picking good names for identifiers is just as important. While i, j, and k are acceptable as loop iterators, you should choose variable names, struct fields, and names of auxiliary functions in a manner such that their relevance to your algorithm is apparent.

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:

ASCII text. If you choose this format, please place your complete writeup in a file named documentation.txt.
PostScript. If you choose this format, please place your complete writeup in a file named documentation.ps.
Pdf. This format is now widely available as an output option in many word-processor or text formatting programs; if you choose this format, please place your complete writeup in a file named documentation.pdf.
HTML. This is the recommended choice.
Why HTML? Not only does HTML allow you better formatting than mere text, easy inclusion of images, facilities for building tables, and other niceties, but it also makes it easy to provide hyperlinks to on-line descriptions of related work. More importantly, you may incorporate your writeup in your personal WWW pages; then, when you get the interview question "So, what were your class projects like at Stanford?", you can smile smugly, walk over to the interviewer's workstation, and point-and-click. (If they don't have a WWW browser, you may want to think again whether you want to work there.)
If you decide to turn in your writeup in HTML, please create a subdirectory named doc_html within your project directory, and place within doc_html all your HTML files and other multimedia aides. Also, if your documentation comprises multiple HTML files, please make sure that the first page we should read is in a file named index.html, residing in your doc_html directory.

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:

Log on an elaine.
cd into your project directory and make sure that all the required project files/subdirectories are there.
Execute
```
/usr/class/cs161/project/bin/161submit
```
Contact us if you encounter any problems using the submit script.

Here is a short FAQ regarding the submission process:

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