Algorithms and Data Structures

G52ADS Coursework for Autumn 2008

Informal Coursework 2

General Intro

• 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 Assignment

The goal is to implement parenthesis matching using SimpleStack you have implemented in the first part of the informal coursework.

1. Download the binary parenmatcher.jar and try running it using:

   java -jar parenmatcher.jar

2. Download the sources in parenmatcher.zip, unpack them, and open in your favourite IDE.
3. Start by looking at interfaces SimpleStringMatcher and StringMatcher either in the source code or in the corresponding in JavaDoc. You may want to check out CharOccurrence, if it could be of any use.
4. Plug in your own implementation of SimpleStack from the previous exercise.
5. Implement SimpleStringMatcher in SimpleStringMatcherImpl1 using SimpleStack.
6. Implement StringMatcher in StringMatcherImpl1 using SimpleStack.
7. 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 SimpleStringMatcherImpl1Test and StringMatcherImpl1Test from SimpleTests suite. Make sure they do not fail.
8. Check the run time of SimpleStringMatcherImpl1Test.testAllMatch_Performance. If it is too slow, rewrite the code to make it faster. (It matches parentheses in roughly 30 kB of text. Imagine you would open 2 MB of text. How long would it take? How does it relate to "the big O thing"?)

Submission

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.