CompSci-61B Lab 6b
Dictionary Lookups

In this assignment you will write alternative classes to the MyList series. These will use a key to store and retrieve values, instead of a numeric index. These are to be placed in the package compsci61b and named MyDictionary (the interface) and the MyArrayDictionary and MyLinkedDictionary classes. You will also so some big oh determinations for the new search methods as applied to the sorted classes.

This assignment is worth 40 points, and consists of 4 exercises. Zero points will be awarded for programs with misspelled filenames, or incorrect case. Zero points will be awarded for programs that do not compile or run on the department's UNIX server. Partial points will be awarded for programs that are run but do not conform to all specifications, at the discretion of the grader. Be sure to complete both exercises and post the lab6b.jar before midnight of the due date, because there is a 5-point-per-day lateness penalty for late work. Check the course outline for due dates for lab assignments.

Compile and test the interface as you did with "MyIntList" in lab 2a's exercise 1. Jar as lab6b.jar, but do not submit -- the program will be further developed in the following exercises.

Use compsci61b.testing.MyArrayList as a model, adding iteration support from compsci61b.MyArrayList. Include a private method to convert a value into its index, like locateIndex from the lecture notes.

Include a private Node class to encapsulate key/value pairs, and make the data storage array an array of these objects. You may include constructors, mutators, and/or accessors for the private node class, but it is not required -- you may directly access the inner class' private members from the methods of its container class.

In the main test method, create a "MyDictionary" reference to a "MyArrayDictionary" object, and exercise all of its methods. Make sure that the array expansion and shifting code works correctly. Your work will be scored using a separate testing program that is not provided to you. So make sure that your own testing is sufficient to assure yourself that the class works according to the specs. If you have any questions about the specs, ask in lab or use the online discussion group -- don't assume anything.

For public interface validation, use the same test.java as in lab 2a's exercise 2, but use these statements to create and validate the data structure object:

MyDictionary<Integer, String> a = new MyArrayDictionary<Integer, String>();
...
System.out.println("Should be true: " + (a instanceof compsci61b.MyDictionary));
System.out.println("Should be true: " + (a instanceof compsci61b.MyArrayDictionary));
System.out.println("Should be true: " + (a instanceof java.io.Serializable));

Include a private Node class to encapsulate key/value pairs and the "next" link, but you may use some other linked-list implementation technique if you prefer. You may include constructors, mutators, and/or accessors, but it is not required -- you may directly access the inner class' private members from the methods of its container class.

In the main test method, create a "MyDictionary" reference to a "MyLinkedDictionary" object, and exercise all of its methods.

For public interface validation, use the same test.java as in lab 2a's exercise 2, but use these statements to create and validate the data structure object:

MyDictionary<Integer, String> a = new MyLinkedDictionary<Integer, String>();
...
System.out.println("Should be true: " + (a instanceof compsci61b.MyDictionary));
System.out.println("Should be true: " + (a instanceof compsci61b.MyLinkedDictionary));
System.out.println("Should be true: " + (a instanceof java.io.Serializable));

1. unsuccessful getValue from a compsci61b.MyArrayDictionary
2. unsuccessful getValue from a compsci61b.MyLinkedDictionary

Perform timing tests on each to confirm your determination of the big oh. Use the spec from lab 4's exercises 5-8, with nicely-aligned columns and 2 decimal digits in the last column's values. Report your determination of the big oh in the output heading, where you see O(?) in the example below.

unsuccessful getValue from a compsci61b.MyArrayDictionary, O(?)
    n     big oh   elapsed time in millis   elapsed time / big oh  norm
-----  ---------   ----------------------   ---------------------  ----
10000          ?                        ?                       ?  1.00
20000          ?                        ?                       ?     ?
40000          ?                        ?                       ?     ?
80000          ?                        ?                       ?     ?

[ Home | Contact Prof. Burns ]