The purpose of this assignment is to implement a balanced binary tree-based variation of a list...

 

Transcribed Image Text:

The purpose of this assignment is to implement a balanced binary tree-based variation of a list and to investigate its time complexity for some of the list operations. Introduction Like an earlier assignment, this assignment will involve (partially) implementing a List¹ interface. The List interface provides four methods for positional (indexed) access to list elements, two methods to search for a specified object, and two methods to insert and remove multiple elements at an arbitrary point in the list. While some of these operations often execute in constant amount of time, the others may execute in time proportional to the index value, depending on an implementation (the LinkedList class, for example, is not very efficient when accessing elements in the middle of the list using an index, and ArrayList does not allow for efficient insertion or deletion, unless the element is at the end of the list). Red-black trees² is a data structure that allows O(log n) search complexity as well as O(log n) insertion complexity within an ordered sequence of n elements. While normally one uses binary search trees to implement maps, with small modifications, one can also use them to implement lists where indices range from zero to list size (inclusive/exclusive). Implementation In this assignment, you will have to write a red-black tree-based partial implementation of the List interface. Unlike the existing implementations (e.g., java.util.LinkedList or java.util.ArrayList), your implementation will allow for faster operations in in the middle of the list. You may start with the tree implementation from The Algorithms book³ (remember to cite any code you use that is not your own). You will need to modify it to allow access by indices and all the other behaviours expected from lists. Note that you cannot just use indices as keys - i.e., wrapping your calls around a map implementation, as doing so would require the indices to be renumbered every time an item is added to or removed from a list (this would take O(n log n)). Instead, you will use subtree sizes in every node and base the insertions on those when given indices*. In fact, the items in your list will be ordered only by their list indices. Part 1 Implement the following public methods in your implementation of the List interface, called RBTList: 1. boolean 2. void 3. E 4. E 5. int 6. void 7. String add(E e) add(int index, E element) remove (int index) get (int index) size() clear() toString() (see Java API: AbstractCollection³) One public constructor should exist in your implementation: one that takes no parameters and creates an empty list when the class is instantiated. The class should use generics. The behaviour of the methods in your implementation should be equivalent to that of Java Standard Library's classes (e.g., ArrayList; please refer to the class API online), except some operations are going to take logarithmic time now (add, remove, get). For the methods of the interface that you do not need to implement, you may either leave them empty or throw an exception public type some UnneededMethod() { } throw new Unsupported OperationException(); Of course, you are free to implement any private or protected methods and classes as you see fit. However, the methods mentioned above (or the ones present in the List interface, or in the class' superclasses) are the only public methods your class may contain. Furthermore, your code should not have any side effects, such as printing debug information to the console. Part 2 Nothing needs to be submitted for this part; however, completing this part will provide you an opportunity to investigate if your implementation is correct and to solidify your understanding of linked lists. Create some tester class and use it with your list implementation to investigate its running time complexity as the number of items in the list increases and as you vary the indices of the elements you are trying to operate on. Try measuring the running time when inserting (deleting, getting...) 10, 100, 1000 ... 1,000,000 elements at various positions. Confirm that the running time follows the expected behaviour for add, remove, and for other methods. NOTES 1. Do not use package-s in your project (put your classes in the default package). Using packages will cost you a 10% deduction from the assignment mark. 2. Some aspects of your code will be marked automatically (e.g., how it handles boundary cases and error conditions), using a custom tester class. It is also imperative you test your classes. If any of the java files that you submit do not compile, the whole submission will be given a grade of zero, regardless of how trivial the compiler error is. The code you submit should compile using javac *.java command in either Windows, Linux, or MacOS. 3. Your code should include Javadoc comments. 4. Using any java.util implementations of Collection or Map interfaces is not allowed (this includes, but is not limited to, ArrayList, LinkedList, Stack and others; importing the java.util.List interface is of course fine). The purpose of this assignment is to implement a balanced binary tree-based variation of a list and to investigate its time complexity for some of the list operations. Introduction Like an earlier assignment, this assignment will involve (partially) implementing a List¹ interface. The List interface provides four methods for positional (indexed) access to list elements, two methods to search for a specified object, and two methods to insert and remove multiple elements at an arbitrary point in the list. While some of these operations often execute in constant amount of time, the others may execute in time proportional to the index value, depending on an implementation (the LinkedList class, for example, is not very efficient when accessing elements in the middle of the list using an index, and ArrayList does not allow for efficient insertion or deletion, unless the element is at the end of the list). Red-black trees² is a data structure that allows O(log n) search complexity as well as O(log n) insertion complexity within an ordered sequence of n elements. While normally one uses binary search trees to implement maps, with small modifications, one can also use them to implement lists where indices range from zero to list size (inclusive/exclusive). Implementation In this assignment, you will have to write a red-black tree-based partial implementation of the List interface. Unlike the existing implementations (e.g., java.util.LinkedList or java.util.ArrayList), your implementation will allow for faster operations in in the middle of the list. You may start with the tree implementation from The Algorithms book³ (remember to cite any code you use that is not your own). You will need to modify it to allow access by indices and all the other behaviours expected from lists. Note that you cannot just use indices as keys - i.e., wrapping your calls around a map implementation, as doing so would require the indices to be renumbered every time an item is added to or removed from a list (this would take O(n log n)). Instead, you will use subtree sizes in every node and base the insertions on those when given indices*. In fact, the items in your list will be ordered only by their list indices. Part 1 Implement the following public methods in your implementation of the List interface, called RBTList: 1. boolean 2. void 3. E 4. E 5. int 6. void 7. String add(E e) add(int index, E element) remove (int index) get (int index) size() clear() toString() (see Java API: AbstractCollection³) One public constructor should exist in your implementation: one that takes no parameters and creates an empty list when the class is instantiated. The class should use generics. The behaviour of the methods in your implementation should be equivalent to that of Java Standard Library's classes (e.g., ArrayList; please refer to the class API online), except some operations are going to take logarithmic time now (add, remove, get). For the methods of the interface that you do not need to implement, you may either leave them empty or throw an exception public type some UnneededMethod() { } throw new Unsupported OperationException(); Of course, you are free to implement any private or protected methods and classes as you see fit. However, the methods mentioned above (or the ones present in the List interface, or in the class' superclasses) are the only public methods your class may contain. Furthermore, your code should not have any side effects, such as printing debug information to the console. Part 2 Nothing needs to be submitted for this part; however, completing this part will provide you an opportunity to investigate if your implementation is correct and to solidify your understanding of linked lists. Create some tester class and use it with your list implementation to investigate its running time complexity as the number of items in the list increases and as you vary the indices of the elements you are trying to operate on. Try measuring the running time when inserting (deleting, getting...) 10, 100, 1000 ... 1,000,000 elements at various positions. Confirm that the running time follows the expected behaviour for add, remove, and for other methods. NOTES 1. Do not use package-s in your project (put your classes in the default package). Using packages will cost you a 10% deduction from the assignment mark. 2. Some aspects of your code will be marked automatically (e.g., how it handles boundary cases and error conditions), using a custom tester class. It is also imperative you test your classes. If any of the java files that you submit do not compile, the whole submission will be given a grade of zero, regardless of how trivial the compiler error is. The code you submit should compile using javac *.java command in either Windows, Linux, or MacOS. 3. Your code should include Javadoc comments. 4. Using any java.util implementations of Collection or Map interfaces is not allowed (this includes, but is not limited to, ArrayList, LinkedList, Stack and others; importing the java.util.List interface is of course fine).

Answer rating: 100% (QA)

It appears that you have given a thorough explanation of the assignment which calls for using a redb... View the full answer