At this point you will test how array bag and Linked bag implementations compare

Question

At this point you will test how array bag and Linked bag implementations compare with respect to the time it takes some methods to execute. We will test getCurrentSize(); contains(T anEntry); add(T anEntry); GetFrequencyOf(T anEntry); and remove(T anEntry.

Proceed as follows:

a) Create an array-based bag that contains 100,000 random integers between 0 and 100,000  

b) Get the bag size (it should match 100,000) (how long did this take in nanoseconds?)

c) Test whether the bag contains the perfect number 8128 (how long did this take in nanoseconds?)

d) Remove the last number from the bag, even if it is 8128 (how long did this take in nanoseconds?)

e) Add the number 8128 (the size of the bag should not have changed at this point. (how long did thid take in nanoseconds?)

f) Determine the frequency with which 8128 occurs (this could be 1). (how long did this take in nanoseconds?)

g) Double the size of the bag to 200,000 and fill the the bag with 100.000 more random integers while maintaining the same 100,000 integers that are already there. Clearly a call to the add method will return false if a fixed size array is used to to implement the ADT bag. Therefore we need to re-size the array, but maintain the name of the old array.

h) Repeat steps b to f and determine how long getCurrentSize(); contains(T anEntry); add(T anEntry); and remove(T anEntry) take now?

i) Do your findings support the table above wherein the methods are compared? Use the times in nanoseconds you obtained for the execution of the methods to support your conclusion.

Submit only code that runs and addresses the problem .

COMPARING IMPLEMENTATIONS LinkedBag Implementation ADT Bag method ArrayBag getCurrentSize () isFull () isEmpty() add (T anEntry) remove () remove (T anEntry) clear ( getFrequencyof (T anEntry) contains (T anEntry) toArray () (1) to Q(n) (0(n) 0(1) to (n) ((1) or C(n 0(1) to (n) O(n) 0(1) to (n) 0 (n)

Explanation / Answer

Code :

Output :

Array Based Implementation Linked List Based Implementation

(a)Length method time: 1307584   9793
(b)Searching 8128, time : 15467636   63420
(c)Deleting last element, time : 12836613   7885608

(d)Adding an element, time : 191194   124510
(e)8128 frequency : 1 1
(f)Searching 8128, time : 7270055   203319
New Array 200000, time : 24522329   29379
(h)(a)Length method time: 8861 8861
(h)(b)Searching 8128, time : 432286 62488
(h)(c)Deleting last element, time : 1273075   74612
200000
(h)(d)Adding an element, time : 1289397 95131
(h)(e)8128 frequency : 2 1
(h)(f)Searching 8128, time : 10027453   96996

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.