Homework 4

CMP 338: Data Structures & Algorithms
Lehman College, City University of New York
Spring 2022

This Homework Is Due By 11:59 PM on Sunday March 20, 2022

Overview

In this assignment you will be implementing the Abstract Data Type (ADT) Queue ADT using two different implementations:

1. Array Based Queue
2. Linked Queue

You will also be writing a driver to test your Queue implementations and you will be measuring the test times and memory usage of each test case.

You will also be adding some functionality to the TestTimes class that you created for Homework 1.

Finally, you will be analysing and comparing the performance of the test cases on both the Array Based Queue and the Linked Queue implementations.

Details

1. TestTimes zyLab

   TestTimes Class

   You will be expanding the functionality of the TestTimes class to implement the expanded TestTimes Interface, The interface may be downloaded from here .

2. ArrayBasedQueue zyLab

   You will write the ArrayBasedQueue.java class which will implement the Queue Interface. The interface may be downloaded from here .

   Please note that Queue Interface extends the Iterable Interface , which requires you to implement one method Iterator iterator() .

3. LinkedQueue zyLab

   You will write the LinkedQueue.java class which will implement the Queue Interface. The interface may be downloaded from here .

   Please note that Queue Interface extends the Iterable Interface , which requires you to implement one method Iterator iterator() .

4. ElementIterator zyLab

   You will write the ElementIterator.java class which will implement the Iterator Interface.

   Please note, you only need to implement two methods from the Iterator interface: boolean hasNext() and E next()

5. Node zyLab

   You will write the Node.java Please see the Node Class Documentation for all the methods you will need.

   Please note that the Node Class is a node for a Doubly Linked Queue.

6. QueueDriver zyLab

   You will write the QueueDriver.java class which will implement the QueueDriver Interface. The interface may be downloaded from here .

   Please note that, in addition to implementing the QueueDriverInterface, you are also required to write your own public static main(String[] args) method in QueueDriver.java that performs all of the required tests as specified below.

Required Tests

Definitions:

You will test two queue implementations with different tests. You will run all tests on both implementations of the QueueInterface. The QueueDriverInterface includes the definitions of two enums:

1. QueueDriverInterface.QueueType

   This enum defines all the possible queue types that you will implement. They are:

   ArrayBasedQueue

   The array based implementation of the QueueInterface.

   LinkedQueue

   The linked implementation of the QueueInterface.

2. QueueDriverInterface.TestType

   All the elements being added and removed from the lists must be instances of the String class.

   This enum defines all the tests that you will be performing. The tests are:

   QueueDriverInterface.TestType.Enqueue:

   1. Initialization: Create an empty queue.
   2. Test: Use the enqueue(E e) method to add 10,000 String objects representing the strings ("String 1" ≤ s ≤ "String 10000") to the Queue.

   QueueDriverInterface.TestType.Dequeue:

   1. Initialization: Create a queue and populate it with String objects representing the Strings: "String 1", "String 2", ... , "String 10000".
   2. Test: Use the dequeue() method to dequeue all the String objects from the queue, one at a time.

   QueueDriverInterface.TestType.DequeueRandom:

   1. Initialization: Create a queue and populate it with String objects representing the Strings: "String 1", "String 2", ... , "String 10000".
   2. Test: Use the dequeue(int index) method to dequeue the String objects from the queue in a random order, by selecting the index randomly each time.

Output From Driver Main Method

Please note that, in addition to implementing the QueueDriverInterface, you are also required to write your own public static main(String[] args) method in QueueDriver.java.

Your main() method will have to call the runTestCase() method for each of test cases listed above a total of ten times for each test case:

For each call to the runTestCase() method your main() method will print out a table with the following output for the Array Based Queue and the Linked Queue implementations:

For each call to the runTestCase() method your main() method will print out a table with the following output for the Array Based List and the Linked List implementations:

Test Type = testType
                   Run 1      Run 2      Run 3      Run 4      Run 5      Run 6      Run 7      Run 8      Run 9      Run 10    Average
                   Micro      Micro      Micro      Micro      Micro      Micro      Micro      Micro      Micro      Micro      Micro 
                  Seconds    Seconds    Seconds    Seconds    Seconds    Seconds    Seconds    Seconds    Seconds    Seconds    Seconds
                ---------- ---------- ---------- ---------- ----------- ---------- ---------- ---------- ---------- --------- ----------
ArrayBasedQueue
LinkedQueue

Test Type = testType
                   Run 1      Run 2      Run 3      Run 4      Run 5      Run 6      Run 7      Run 8      Run 9      Run 10    Average
                   Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo      Kilo 
                   Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes     Bytes 
                ---------- ---------- ---------- ---------- ----------- ---------- ---------- ---------- ---------- --------- ----------
ArrayBasedQueue
LinkedQueue
  

Please note that the test times and the average are in Micro Seconds and the memory usage is in Kilo Bytes. You will need to make the necessary conversions.

Sample Output

Test Type = Enqueue
                   Run 1      Run 2      Run 3      Run 4      Run 5      Run 6      Run 7      Run 8      Run 9      Run 10    Average
                   Micro      Micro      Micro      Micro      Micro      Micro      Micro      Micro      Micro      Micro      Micro 
                  Seconds    Seconds    Seconds    Seconds    Seconds    Seconds    Seconds    Seconds    Seconds    Seconds    Seconds
                ---------- ---------- ---------- ---------- ----------- ---------- ---------- ---------- ---------- --------- ----------
ArrayBasedQueue   5057.113   2638.762   2560.027   2087.972   2193.549   2065.599   1956.549   1277.810   1224.415   1256.912   2231.871
LinkedQueue       2420.563   1959.991   1326.675   1342.187   1458.031   1316.956   1334.211   1378.810   1506.672   1102.988   1514.708

Test Type = Enqueue
                   Run 1      Run 2      Run 3      Run 4      Run 5      Run 6      Run 7      Run 8      Run 9      Run 10     Average
                   Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo 
                   Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes 
                ---------- ---------- ---------- ---------- ----------- ---------- ---------- ---------- ---------- ---------  ----------
ArrayBasedQueue   3932.219   6592.734   7903.492  10524.977   11835.758  13146.539  15807.078  17117.797  19739.313 21050.031   12764.994
LinkedQueue      23671.508  24982.266  27603.781  30225.297   31536.055  34157.570  36779.086  38089.844  40711.359 42022.102   32977.887




Test Type = Dequeue
                   Run 1      Run 2      Run 3      Run 4      Run 5      Run 6      Run 7      Run 8      Run 9      Run 10    Average
                   Micro      Micro      Micro      Micro      Micro      Micro      Micro      Micro      Micro      Micro      Micro 
                  Seconds    Seconds    Seconds    Seconds    Seconds    Seconds    Seconds    Seconds    Seconds    Seconds    Seconds
                ---------- ---------- ---------- ---------- ----------- ---------- ---------- ---------- ---------- --------- ----------
ArrayBasedQueue    469.629    164.669    164.523    221.657     176.068    137.763    119.565    155.056    113.918   112.879    183.573
LinkedQueue        649.179    117.386    238.775    295.618     148.869    147.413     88.588    111.047     86.715    87.826    197.142

Test Type = Dequeue
                   Run 1      Run 2      Run 3      Run 4      Run 5      Run 6      Run 7      Run 8      Run 9      Run 10     Average
                   Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo 
                   Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes 
                ---------- ---------- ---------- ---------- ----------- ---------- ---------- ---------- ---------- ---------  ----------
ArrayBasedQueue  43372.008  46071.727  47382.508  50004.070  51314.852   52625.633  55247.172  55247.172  56557.930 56557.930   51438.100
LinkedQueue      59218.508  61840.070  64461.594  65536.000   5321.531    6619.000   7916.469   9213.938  10511.406 11808.875   30244.739




Test Type = DequeueRandom
                   Run 1      Run 2      Run 3      Run 4      Run 5      Run 6      Run 7      Run 8      Run 9      Run 10     Average
                   Micro      Micro      Micro      Micro      Micro      Micro      Micro      Micro      Micro      Micro       Micro 
                  Seconds    Seconds    Seconds    Seconds    Seconds    Seconds    Seconds    Seconds    Seconds    Seconds     Seconds
                ---------- ---------- ---------- ---------- ----------- ---------- ---------- ---------- ---------- ---------- ----------
ArrayBasedQueue 187856.733 172682.043 171321.313 172888.932  167139.142 182414.073 198274.037 193273.824 192348.282 189320.235 182751.861
LinkedQueue     137598.780 196548.062 192145.832 189552.437  190891.565 190019.211 113049.062 113112.209 111297.543 111000.047 154521.475

Test Type = DequeueRandom 
                   Run 1      Run 2      Run 3      Run 4      Run 5      Run 6      Run 7      Run 8      Run 9      Run 10     Average
                   Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo 
                   Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes 
                ---------- ---------- ---------- ---------- ----------- ---------- ---------- ---------- ---------- ---------  ----------
ArrayBasedQueue  11808.875  13145.383  14442.852  14442.852   15740.320  15740.320  17037.789  17037.789  18374.336  19671.805  15744.232
LinkedQueue      20969.258  22266.750  23564.180  26159.086   28753.969  30051.422  31348.891  32646.344  33943.797  33943.797  28364.749
  

Analysis:

Using the tables you created by running QueueDriver.main(), copy your results and your graphs into a Microsoft Word document and answer the following questions using 1-3 complete sentences for each question:

1. Create graphs from the test times you measured.
2. Discuss the difference in test times between the array based queue and the linked queue for all the test cases. Explain the reason(s) why the test times are different between the implementations. Did the results match your expectations? Why or why not? Be as specific as possible.
3. Discuss the difference in memory usage between the array based queue and the linked queue for all the test cases. Explain the reason(s) why the memory usage are different between the implementations. Did the results match your expectations? Why or why not? Be as specific as possible.
4. Are the test times ever similar for both the array based queue and the linked queue? Explain the reason(s) why the test times in both implementations are similar. Did the results match your expectations? Why or why not? Be as specific as possible.
5. Are the memory usages ever similar for both the array based queue and the linked queue? Explain the reason(s) why the memory usages in both implementations are similar. Did the results match your expectations? Why or why not? Be as specific as possible.

Please submit the completed assignment in your zyBooks , in the Homework 4 Chapter.

Please submit your analysis on Blackboard as a typed Microsoft Word file (.docx). No other forms of submission will be accepted. Please include your graphs in the same file as your analysis.