Q. Should I include dependencies in my header? Yes. Note that it's probably easier to list your dependencies in terms of .jar files. See this page for a list of classes inside each jar file.
Q. Do I need to list built-in classes that I import (e.g. import java.util.Iterator) No. The idea is that you only want to list things that need to be in the classpath for the compiler to work.
Q. What's the proper header format to quiet this nagging autograder? Example:
If you really want to go above and beyond, you can try to use fancier fitting techniques, but please explain thoroughly your methodology, as it's very easy to make mistakes when trying to fit functions like N log N.
Q. 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, and the grader will let you know if you're right (and will not deduct points if you're wrong).
Q. 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.
Q. How many data points do I need to analyze the run time of my program? You should have 5 at a minimum.
Q. How do I make the data collection process less tedious? I'd highly recommend writing a program that prints the tables out 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). I'd recommend writing this program as a separate class, e.g. PercolationStatsTimer.
As an example of how to write an automated timing-table generator,
see DoublingRatio.java. Feel free to copy, paste, and modify this code.
Q. When I'm told to find a formula using tilde notation for the running time, is it OK if I try to derive the formulas 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 coefficient (often called a) that is vital to a Tilde notation answer.
However, you are welcome to make comments about the order of growth that you're expecting from 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).
By making automated timing tests, doing experiments to probe things like the log ratio is way easier and more fun.
Q. How do I calculate the memory used by an object? See pages 200-204 of the book. You can also get some practice with the 3rd problem of the Blackboard exercise on Analysis of Algorithms. There are also automated tools available on the web that you are welcome to use, but they are tricky to get working, and you should understand how to calculate memory manually.
Q. Should I include memory that is used by methods? For example, in my PercolationStats constructor, I store a bunch of information that is thrown away as soon as the constructor completes. Would that count? Yes, you should include this memory.
/*************************************************************************
* Name: Ruth Dannenfelser
* Login: rd6
* Precept: P04A
*
* Partner Name: N/A
* Partner Login: N/A
* Partner Precept: N/A
*
* Compilation: javac Percolation.java
* Execution: java Percolation
* Dependencies: WeightedQuickUF.java
*
* Description: Modeling Percolation like a boss. woot. woot.
**************************************************************************/
Timing analysis
Q. When I'm told to find a formula using tilde notation for the running time, is it OK to assume that run time obeys a power law (e.g. aNb)? Yes. In fact you should definitely do this!
Memory Analysis