Deleting a random element from an arraylist

Assignment Help Data Structure & Algorithms
Reference no: EM13494394

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.


Attachment:- 1922_comp.zip

Reference no: EM13494394

Questions Cloud

Explain your analysis and understanding of social accounting : Details: You are meeting with accounting department personnel to make sure they understand the importance of corporate social responsibility and how it affects the company and their specific jobs.
Explain what is the mass of ethylene glycol dissolved : Permanent antifreeze contains ethylene glycol dissolved in water. What is the mass of ethylene glycol dissolved in 5.00 kg of a 40.0% solution
Determine the electric potential at the center of the shell : A charge of q = +10-7 C is uniformly distributed on a spherical shell of radius 12 cm. What is the electric potential at the center of the shell
How much energy was released in the explosion : A 12.0- shell is launched at an angle of 55.0 above the horizontal with an initial speed of 150. how much energy was released in the explosion
Deleting a random element from an arraylist : 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 ..
Explain types of crystalline solids is malleable and ductile : Which of the following types of crystalline solids is malleable, ductile, and a conductor of electricity
What is the capacitance of the vessicle : Assume a spherical membrane vesicle of diameter 50nm( about the size of a synaptic vesicle), What is the capacitance of the vessicle
Define glucose produces ethyl alcohol and carbon dioxide : Fermentation of glucose produces ethyl alcohol and carbon dioxide; C6H12O6(l) ? 2 C2H5OH(l) + 2 CO2(g) What is ?H°rxn (in kilojoules) if 385.3 mL of CO2 was collected over water at 20.00°C and 761.2 mm Hg
Explain salicylic acid with an excess of methanol produced : Methyl salicylate (oil of wintergreen) is prepared by heating salicylic acid (C7H6O3) with methanol (CH3OH) C7H6O3 + CH3OH ® C8H8O3 + H2O What is the percent yield if reaction of 8.244 g of salicylic acid with an excess of methanol produced a meas..

Reviews

Write a Review

 

Data Structure & Algorithms Questions & Answers

  Explaining effective customer relationships and loyalty

Paws'n Tails is an online pet shop that wants to influence what customers buy and builkd effective customer relationships and loyalty.

  Creating java program using two arrays

Create a program in Java which defines 2-unconstrained arrays of user defined length n, that contain n Random numbers each and which outputs addition of pairs of elements.

  Efficient algorithm to achieve goal using few base stations

Certain points along the road, so that every house is within four miles of one of the base stations. Give an efficient algorithm that achieves this goal using as few base stations as possible.

  Creating code for a class called arrayqsn

Create all the code for a class called ArrayQsn. This class will contain 2-techniques. The first technique runningSumMean accepts an array of ints as a parameter, and will return the mean of the values as a double.

  Give algorithm-correctness proof-time complexity for tree

Determine the minimum number of nodes in tree to remove so that the tree is separated into subtrees of sizes at most k. Give the algorithm, the correctness proof and the time complexity.

  Input a list of employee names and salaries and determine

input a list of employee names and salaries and determine the meanaverage salary as well as the number of salaries

  Find maximum possible amount of money by optimal strategy

Removes it from row permanently, and receives value of coin. Find out the maximum possible amount of money we can definitely win if we move first.

  Creating an idef1x diagram

Construct an IDEF1X diagram that demonstrate only entities and relationships. Name each relationship and specify its cardinalities.

  Illustrate insertion into the linear hash file

Illustrate insertion into the linear hash file. Suppose that bucket splitting occurs whenever file load factor exceeds (is greater than) 0.8.

  Write algorithm using pseudocode to recognize substrings

Write the algorithm, using pseudocode, to do the following task, Given the string of numbers, recognize all the substrings which form numbers which are divisible by 3.

  You have been commissioned to prepare a manual covering the

in a 6-8-page paper complete the followingyou have been commissioned to create a manual covering the installation

  Draft a mission statement for willowbrook school

Draft a mission statement for Willowbrook School, based on information provided in the first two chapters and does a strong business case exist in the case of Willowbrook School? Discuss why or why not.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd