Today's tutorial covers list processing in Java using the
GenList class. We will see the use of generics, and will
write methods in both the recursive and iterative style.
The topics for today's tutorial come from lecture modules 9 and 10
(see handouts).
You won't be able to do much for this tutorial without the skeleton code. It's available in a folder, zip file, or a gzipped tar.
Look at the code for the FrequencyPair class and the
FrequencyListTest class first. You should be able to understand
how the FrequencyPair class is used and what its function is,
and you should have a rough idea of what the
FrequencyList class does.
Note that we are looking at the tests before we even see the skeleton code for the class! There is actually a theory which says this is correct - to write tests for a class before we write the code. This is called "test-driven development".
Now look at the skeleton code for the FrequencyList
class. The documentation in this class should be sufficient to completely
describe the behavior of each method. Use recursion to
implement all the methods in the
class except for mostFrequent(int k).
Note that you will have to write helper methods for most of these.
Use the FrequencyListTest class to test your implementation.
Now rewrite all the methods you just implemented using iteration instead
of recursion for the list processing. You shouldn't need any helper methods
now. Again, test with FrequencyListTest.
Now go back and implement the method we skipped,
mostFrequent(int k) First write the method using recursion,
then using iteration. Make use of the provided helper method,
insert. For a final challenge, rewrite insert
to use iteration instead of recursion.
Last modified on Friday, 19 August 2011, at 18:05 hours.