Programming Assignment FAQ


General FAQ

What's the difference between the assignment and the checklist? The assignment provides the programming assignment specification; the checklist provides clarifications, test data, and hints that might be helpful in completing the assignment.

Where can I find the course policies regarding submission, lateness, grading, and collaboration? Please read the Assignments Page.

I would like to receive help from the course staff. Where can I find the schedules? Piazza is ideal for short technical questions; office hours are best for longer or more conceptual questions; the lab is great for help with debugging. Here is the office hour schedule; here is the lab TA schedule.


Submission FAQ

What should I do to submit my solutions? Here is a short list of things to do:

When I submit, it tells me that I have only 2 checks remaining. Why? In COS 226, there is a limit on the number of times that you may click the Check All Submitted Files button before it is disabled. Please read the submission policy on the Assignments Page.

When I submit, my browser displays a dialog like the following. What should I do?

      Dropbox taking longer than usual

Click OK to let the autograder continue—sometimes the autograder needs more time than your browser deems appropriate. Whether or not you click OK or Cancel, it will still count against your limit of 10 checks.

How many checks to I get if I work with a partner? Both partners in total have 10 times to use the Check All Submitted Files button. For example, one partner may submit 7 times and the other may submit 3 before the Correctness checks are disabled.

When I submit, the autograder reports the error "Process took too long and was killed (output may be truncated)." What could cause this? This usually means that the autograder could not complete in the allocated amount of time. The most common cause is a serious performance bug. Another possibility is that your program produces an enormous amount of output, perhaps because you left in a debugging statement. It will count against your number of checks.

When I try to submit files I get a message telling me "No NetID found in header of file." How do I fix this? At the top of each Java file, include a header in the format described in the header section below.


Header FAQ

What is the proper format for the header for Java programs? Here is an example for an assignment with no partner.

/******************************************************************************
 *  Name:    Kevin Wayne
 *  NetID:   wayne
 *  Precept: P01
 *
 *  Partner Name:    N/A
 *  Partner NetID:   N/A
 *  Partner Precept: N/A
 * 
 *  Description:  Modeling Percolation using an N-by-N grid and Union-Find data 
 *                structures to determine the threshold. woot. woot.
 ******************************************************************************/
The header must appear at the very beginning of the .java file and follow the precise formatting above (e.g., exactly 78 asterisks on the first and last line). We recommend cut and pasting the above template. You are free to add additional information after the description section of the header (such as instructions for compiling, executing, and listing any dependencies) but this is not required in COS 226.

What is the format of the header for the readme.txt file? It is the same as for Java programs, except no description is required.

/******************************************************************************
 *  Name:    Robert Sedgewick
 *  NetID:   rs
 *  Precept: P02
 *
 *  Partner Name:    Kevin Wayne
 *  Partner NetID:   wayne
 *  Partner Precept: P01
 ******************************************************************************/

Can I use non-ASCII characters in the header? Yes. However, if you use non-ASCII characters, they must be Unicode and encoded using UTF-8.


Java FAQ

I haven't programmed in Java in a while. What material do I need to remember? For a review of our Java programming model (including our input and output libraries), read Sections 1.1 and 1.2 of Algorithms, 4th Edition.

Which Java programming environment should I use? For simplicity, we recommend the lightweight IDE DrJava along with the command line. If you use our Mac OS X or Windows installer, then everything should be configured and ready to go. If you prefer use another IDE (such as Eclipse), that's perfectly fine—be sure that you can use command-line arguments, read from standard input, redirect standard input and output, and add algs4.jar to your Java classpath.

What are the input and output libraries? We have designed a set of easy-to-use Java libraries in algs4.jar (similar to the one we use in COS 126) for input and output. You are required to use these in this course. Here are the APIs.

Where can I find the Java code for the algorithms and data structures from lecture and the textbook? They are in algs4.jar. Here are the APIs.

Can I use various Java libraries in this assignment, such as Arrays.sort(), java.util.LinkedList, java.util.ArrayList, java.util.TreeMap, and java.util.HashMap? In general, you should not use any Java library until we have implemented equivalent versions in lecture. Once we have introduced them in lecture, you are free to use either the Java library version or our equivalent. You are always welcome to use common functions in java.lang such as Math.sqrt() and Integer.parseInt().

How do I throw a specific exception, such as java.lang.IndexOutOfBoundsException? Use a throw statement like the following:

if (i < 0 || i >= N) throw new IndexOutOfBoundsException("row index " + i + " must be between 0 and " + (N-1));
While you are required to throw exceptions using throw statements as specified, you should not catch exceptions with try-catch statements—this will interfere with our grading scripts.


Unit Testing FAQ

What is unit testing? It is testing of each method within a class. Ideally, it should be comprehensive enough to catch any error in the class.

Do I need to unit test every class I submit? Yes, that is good programming practice.


Style FAQ

How should I compose my code? Here are some recommended style guidelines. Below are some that are particularly important (and for which you risk losing points if you ignore).

How should I format and comment my code? Below are some that are particularly important (and for which you risk losing points if you ignore).


Style and Bug Checker

When I compile my program, I receive a warning message. Is that ok? No, your programs should compile without errors or warnings. There is only one exception to this rule (on Assignment 2), where a "generic array creation" warning is permitted.

Style checker. We recommend using Checkstyle to check the style of your Java programs. The configuration file checkstyle-6.9.xml is compatible with Checkstyle 6.9. Here is a list of available Checkstyle checks.

Bug checker. We recommend using FindBugs 3.0.1 to identify common bug patterns in your code. The configuration file findbugs.xml is compatible with Findbus 2.0.3 and 3.0.1. Here is a summary of FindBugs bug descriptions.

Mac OS X and Windows installer. If you used our Mac OS X or Windows installer, these programs are already installed as command-line utilities. You can check a single file or multiple files via the commands:

% checkstyle-algs4 HelloWorld.java
% checkstyle-algs4 *.java                      
% findbugs-algs4 HelloWorld.class
% findbugs-algs4 *.class
Note that Checkstyle inspects the source code; Findbugs inspects the compiled code.

Eclipse. For Eclipse users, there is a Checkstyle plugin for Eclipse and a Findbugs plugin for Eclipse.

Caveat. The appearance of a warning message does not necessarily lead to a deduction (and, in some cases, it does not even indicate an error).


Memory Analysis FAQ

What's the difference between tilde notation and order of growth notation? Both tilde notation and order of growth notation discard lower order terms. Tilde notation includes the coefficient of the leading term; order of growth notation discards the coefficient of the leading term. You risk losing points for including lower order terms, failing to include the leading coefficient with tilde notation, and including the leading coefficient with order of growth notation.

How do I calculate the memory used by an object? Use the memory model described in the textbook and lecture slides.

If an object references other objects, should I count the memory of the objects referenced? It depends. In general, you should count all memory unless instructed to do otherwise.


Timing Analysis FAQ
When I'm told to find a formula using tilde notation for the running time, can I assume that the running time obeys a power law (e.g. a Nb)? Yes. If you really want to go above and beyond, you can try to use fancier fitting techniques, but please explain your methodology, as it's very easy to make mistakes when trying to fit functions like N log N.

I get an exponent of 2.1, but I'm expecting it to be 2. What should I put down as an answer? You should report the value as 2.1. Feel free to explain why you think it should be 2.

Different data points are giving me different exponents! What do I do? It's mostly correct to say that you should use the largest data point you can. Answers given with large data points will be considered correct.

How many data points do I need to analyze the run time of my program? At a minimum, you should use 5. You risk losing points if you use fewer than 5 or if the data points that you use are for too small a value of N (e.g., take only a fraction of a second).

How do I make the data collection process less tedious? We recommend writing a program that prints the tables for you. You can even have it print out log ratios! The nice thing about this is that you can reuse this code for future assignments (with some tweaking). For example, see DoublingRatio.java. Feel free to copy, paste, and modify this code.

When the readme asks to give the running time in seconds, can I derive the formula through mathematical analysis? No. While one could make a case for trying to theoretically derive the order of growth of an algorithm, you'd have no hope of finding the leading coefficient because it depends on the machine on which it is running.

However, you are welcome to make comments about the order of growth that you're expecting based on your understanding of theory. A mismatch with your empirical results might indicate a bug in your code, a misunderstanding of theory, a warm and fuzzy feeling that there is a missing log factor in the empirical result, or a demonstration that N is not large enough for asymptotic behavior to be observed (this is particularly true if the log ratio has not settled down).


FTP FAQ

What's the easiest way to copy a subdirectory from the COS 226 ftp site to my computer?