This page contains an archived post to the Java Answers Forum made prior to February 25, 2002. If you wish to participate in discussions, please visit the new Artima Forums.

Message:

I really need you guys help

Posted by chilled on April 05, 2001 at 2:39 AM

Here is my assignment,could you please help me to solve it.Thanx for your help.My email address : phuong253@yahoo.com

Part 1 (6/10 marks)

Sometimes it is useful to test several data structures on your data before committing to a single structure for your project design. One way to compare different data structures empirically is to count the number of "fundamental operations" the data structure must perform on your data set.

You are to design and implement an application for testing and reporting the efficiency of data structures. You should assume that the class implementing any data structure to be tested implements the DataStructure interface, as described in the file DataStructure.java linked from the unit web page. This interface requires three methods for manipulating the data structure, and one method for printing metrics relating to the class. You should read and understand the example data structure in MyStack.java that conforms to the DataStructure interface.

Your tester application should read data access commands from a text file, the name of which is supplied as a command line argument to your program. The first line of the input file will contain a code for the data structure you are to test. For example, LL might be the code for a linked list, and S might be the code for a stack. The remaining lines of the input file will contain one data access command per line. Valid commands are

Command
Action required

A data
Add data to the data structure.

R data
Remove data from the data structure.

S data
Search for data in the data structure.

After reading each command your program should execute the appropriate action on the data structure. In addition to updating the data structure, you should record the metric passed back from the data structure's method. The metric should reflect a count of the number of fundamental operations the data structure required to perform the task. For example, a stack has pushes and pops as its fundamental operation, while an array might report the number of probes required. Once the entire input file is read, you should print the total metric for all operations in the input command file to stdout.

For example if the input file contains

S
A apple
A eggplant
A banana
A apple
S apple
S eggplant
S banana
R apple
S apple

The output when running your tester, assuming S is the code for the MyStack class, should be:

The total number of pushes and pops for MyStack is 52.

Note that different data structures may use different metrics. For example, the number of pushes and pops in MyStack.java is appropriate for a stack, but not relevant to any other data structure.

Also note that MyStack.java does not implement the stack directly, but rather makes use of the java.util.Stack to simulate the required stack actions.

Part 2 (4/10 marks)

In Part 2 you should implement a new class that supports a Move To Front list (MTF). This is a data structure used in some data compression programs (eg bzip), and features in some OS programs. The MTF list is a normal linked list with the added rule that each time an item in the list is accessed, it is moved to the front of the list. Do not allow duplicate data items in your list.

For example, assume that we are maintaining a MTF list of fruits that looks like this:

banana, apple, orange, pear, grape, lemon

If a search is requested for pear, or pear is inserted into the list, then the list is traversed from the beginning until pear is reached, and then it is moved to the front, resulting in the following list:

pear, banana, apple, orange, grape, lemon

The idea behind the data structure is that frequently accessed items will group together at the front of list, hence requiring few search steps to locate. It is especially useful when the frequency distribution of accesses to items in the list is heavily skewed towards only a few items.

Using the same example input file as above, the list will change as follows:

NULL
apple
eggplant -> apple
banana-> eggplant -> apple
apple -> banana -> eggplant
apple -> banana -> eggplant
eggplant -> apple -> banana
banana -> eggplant -> apple
banana -> eggplant

It is your responsibility to choose the metric that you will use to assess your MTF list.

You should test your program on small data sets to ensure it is working properly.

Extra challenges

There will be no marks awarded for attempting any of these extra challenges. They are for interested students to pursue once they have fully completed Parts 1 and 2 of the assignment.

Advanced Java programmers might like to use the name of the class that implements the data structure as the first line of the input file. You can then use the java.lang.reflect package to invoke an instance of the class, then you will not need to edit the source of your tester every time you want to add test a new data structure.
Try writing the MTF list class from scratch, rather than simulating it with java.util.LinkedList. While pointer manipulations in lists and trees can be frustrating at times, in the real world you may not have the JFC at your disposal, and have to resort to programming them yourself!
Implement a third DataStructure class that supports a normal linked list. How does your metric compare the MTF list and the linked list?