Delete a random element from an arraylist-JAVA Programming
1. In the archive, you will find the RandomQueue class, which implements the Queue interface in a way that, when we call remove()/poll(), a random element is removed from the queue. Currently, this is done by storing all the elements in an ArrayList and picking one at random to remove. Unfortunately, this slow, since deleting a random element from an ArrayList is slow because of all the shifting. For this question, you should modify the poll()method so that it runs in constant time.
Hint: The order that elements are stored in the ArrayList is not important, so you’re free to reorder elements to make the deletion faster.
2. In the archive, you will find the BulkArrayDeque class, which is a subclass of ArrayDeque that has a slow implementation of the addAll(i,c) method. Look at this implementation, understand why it is so slow, and reimplement this method so that it runs in O(1+c.size() + n – i) time.
3.The ArrayDeque implementation given in the archive is pretty good, but it suffers a little from its use of modular arithmetic. Complete the ArrayDeque2 class that works like an ArrayDeque, but all the data always occupies positions a[j],a[j+1],…,a[j+n-1](notice that there is no modular arithmetic being done).
If ever the data runs off either end of a then the resize() operation is called to resize a to size 2*n and place the data at locations a[n/2],…,a[n/2+n-1].
Like an ArrayDeque, the add(i,x), and remove(i) operations should run in O(1+min{i,n-i}) amortized time.
4. This is another exercise in avoiding modular arithmetic. When a.length is a power of 2, i%a.length = i&(a.length-1). Using this fact, complete the ArrayDeque3 class in the implementation so that it uses & and – instead of %. The trick here is to change how and when a is resized so that a.length always remains a power of two, but the data structure still remains efficient.
Like an ArrayDeque, the add(i,x), and remove(i) operations should run in O(1+min{i,n-i}) amortized time.
5. Make a RootishArrayStack2 class that uses the same ideas as a RootishArrayStack, but is more efficient.
Instead of storing data in a sequence of r arrays b[0],…,b[r-1], it should store the data in a sequence of r bounded ArrayDeques (the BDeque class is provided in the assignment). If you implement this properly, the add(i,x) and remove(i) operations will run in O(1+min{n1/2, n-i}) time.
Hint: Using a BDeque means that most of the shifting that is done within the arrays of a RootishArrayStack can be replaced with remove(0), remove(size()-1), add(0), or add(size()-1).
Part II: Testing
Within the Tester class, write the following functions, all of which return true if all tests are successful or false if any test fails.
1. testPart1(q) that takes as input a Queue, q, and tests if it satisfies the requirements for Question 1.
This function should do all kinds of correctness tests on q.
This function should make a decent effort to test if the output order of the queue is indeed random.
This function should check that add(x) and remove(x) run in constant time.
2. testPart2(ad) function that tests if the addAll(i,c) operation works for the List ad and satisifies the requirements for Question 2:
This function should do all kinds of correctness tests on ad.
This function should test if the running time of the addAll(i,c) operation is indeed O(1+c.size() + n – i).
3. testPart3(ad) function that tests if a the list ad satisfies the requirements for Question 3:
This function should do all kinds of correctness tests.
This function should test that the performance of all operations is what it should be for an ArrayDeque
4. There is no Question 4, since the test for Question 3 also works for Question 4.
5. testPart5(ras) function that tests if the List ras satisifies the requirements for Question 5.
The function should do all kinds of correctness tests on ras.
The function should do its best to check that the running time of the add(i,x) and remove(i) operations is indeed O(1+min{n1/2, n-i}).
Some notes:
When applied to a correct and efficient implementation, your test functions should not take long to execute, no more than 2 seconds.
You can test elapsed times using System.nanoTime(). This is encapsulated by the Stopwatch class that can be found in the zip file; feel free to use that.
Your test functions will be run against buggy/slow implementations as well as correct/fast implementations. In the former case, your functions may return false, crash, or take more than 2 seconds to execute. In the latter case, your functions must return true and take less than 2 seconds to execute.
