("Should be true: " + (a instanceof java.io.Serializable)) Ĭompile, jar as lab6a.jar, and run, but do not submit - the program will be further developed in the following exercises.ĮXERCISE 3: Linked List Implementation Of A Sorted List (5 points) ("Should be true: " + (a instanceof compsci61b.MyArrayList)) ("Should be true: " + (a instanceof compsci61b.MyArrayBasedDataStructure)) ("Should be true: " + (a instanceof compsci61b.MySortedList)) ("Should be true: " + (a instanceof compsci61b.MyList)) If you have any questions about the specs, ask in lab or use the online discussion group - don't assume anything.įor 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: So make sure that your own testing is sufficient to assure yourself that the class works according to the specs. Your work will be scored using a separate testing program that is not provided to you. Make sure that the array expansion and shifting code works correctly. In the main test method, create a "MySortedList" reference to a "MySortedArrayList" object, and exercise all of its methods. Note that this method, and the one like it in the ch.13 of our Carrano textbook ( getPosition), both modify the index to denote that the value was not actually found at the index, but if it existed at all, it would be at that index.Ĭarrano's scheme makes the value negative - the scheme from our lecture notes adds size()+1 instead. Include a private method to convert a value into its index, like getIndex from the lecture notes for topic 5. Write MySortedArrayList.java in package compsci61b.Įxtend compsci61b.MyArrayList and implement compsci61b.MySortedList and java.io.Serializable. Jar as lab6a.jar, but do not submit - the program will be further developed in the following exercises.ĮXERCISE 2: An Array Implementation Of A Sorted List (5 points) Throw an UnsupportedOperationExceptionĬompile and test the interface as you did with "MyIntList" in lab 2a's exercise 1. public boolean replace(int index, T value) is no longer supported.public boolean add(int index, T value) is no longer supported.public boolean add(T value) adds the value at an index that maintains sorted order, and not necessarily at then end.Īdd comment lines in the file (anywhere you want - they are just comments) that explain changes in the uses of some methods that appear in the MyList interface. In the interface, include one new method: public boolean remove(T value). Note that this the version of the MyList interface that requires support for iteration and for-each in the classes that implement it. Write the interface MySortedList.java in package compsci61b, extending compsci61b.MyList. Partial points will be awarded for programs that are run but do not conform to all specifications, at the discretion of the grader.īe sure to complete both exercises and post the lab6a.jar before midnight of the due date, because there is a 5-point-per-day lateness penalty for late work.Ĭheck the course outline for due dates for lab assignments.ĮXERCISE 1: An Interface For Sorted Data Structures (5 points) Zero points will be awarded for programs that do not compile or run on the department's UNIX server. Zero points will be awarded for programs with misspelled filenames, or incorrect case. This assignment is worth 40 points, and consists of 8 exercises. You will also so some big oh determinations for the new search methods as applied to the sorted classes. These are to be placed in the package compsci61b and named MySortedList (the interface) and the MySortedArrayList and MySortedLinkedList classes. To support binary algorithms, you will also create a new interface and 2 new classes that are like MyList and its implementations, except that they are sorted in order at all times. Two techniques will be implemented: "sequential" (or "linear") searching, which is O(n), and "binary" searching, which is O(log n). In this assignment you will complete work the a "utility" class, compsci61b.MyUtilities, by adding methods that search MyList objects for matching values. CompSci-61B Lab 6a, Sequential and Binary Searches CompSci-61B Lab 6a
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |