Algorithms and Data Structures

G52ADS Coursework for Autumn 2008

This is an unofficial page. For all formal details, see Andrew J. Parkes and his Technicolor website.
From 1st year Programming, you should know Core Java 5+, including Collections and Generics.
You may have to learn jUnit 4.5, if you have never used it before. (There could have been a lecture or two on JUnit by Dave Elliman in G51PRG.) It is well worth learning, as it is the industry-wide standard testing tool. Birmingham School of CS has a decent tutorial on-line.
It's heartily recommended that you learn to use and one of great IDEs there are for Java. The big & free IDEs are NetBeans and Eclipse, then there is JBuilder, and last but not least, there is a very nice "learn Java" IDE by the name of Blue J.
The recommended Java textbook is the 4th edition of Eckel's Thinking in Java (available in the library or at Amazon). The first seven chapters are available for free here. The complete, if slightly out-dated, 4th revision of the 3rd edition is available for free here.
When stuck, don't panic. Try to think for a bit. Then try Google, the documentation, and the textbook, and when all fails, go and see Jakub in B78. Beware, though: If he can google up the answer within five seconds, he may be reluctant to answer better questions you could have in the future.

The goal is to develop an array-based implementation of the interface SimpleStack, provided to you complete with some unit tests.

Download the source code for the interface and unit tests in simplestack.zip, unpack them, and open in your favourite IDE.
Start by looking at interface SimpleStack either in the source code or in the corresponding in JavaDoc.
Learn to use jUnit 4.5, if you have never used it before. (There could have been a lecture or two on JUnit by Dave Elliman in G51PRG.) Run jUnit tests SimpleStackImplTest from SimpleTests suite. Note down the run times of the *_Performance tests.
Open SimpleStackImpl and replace the present implementation using java.Util.Stack with your own one. (Look for the "TODO" comments.)
Run jUnit tests SimpleStackImplTest from SimpleTests suite again, now using your own implementation. Make sure they do not fail.
Check the run time of *_Performance tests and compare it with the the times you noted down previously. If your implementation is too slow, rewrite the code to make it faster. (Does this relate in any way to "the big O thing"?)

Feel free not to submit this. Please do work in pairs or groups. It's so much more fun!

See more of Jakub's homepage or the list of exercises, if you please.