Implementing IntList
Implementing IntList with addLast() and addBefore() functions in constant time.
Problem Statement:
https://s3.amazonaws.com/iedu-attachments-question/123a48466fba8185a34ed0161c8a92b9_5e027b67d2eb9ef5ab1473885070b82c.pdf
In class, we implemented an IntArrayList class which internally had an array of integers but ENHANCEd it by making it easy to add new elements to the end. We saw that adding π elements to an IntArrayList would only take O(π) time. It accomplished this by doubling the underlying size of the array and copying the old array every time it ran out of space. If π total elements are added to the array, in the worst case, the array might have run out of space and had to copy itself when the very last (πth) element was added, when the π 2 nd element was added, π 4 th, π 8 th, and so on down to the starting size of the array. Every time the array runs out of space, it needs to copy all the elements from the old array to the new array. However, even as π becomes very large and this series becomes arbitrarily long, π < π + π 2 + π 4 + π 8 + π 16 + ⋯ ≤ 2π. In other words, the total number of elements we need to copy over the lifetime of an IntArrayList is bounded above by a linear function of the total number of elements added to it. (Allocating the array each time we copy is additional work which depends on the memory allocation algorithm used, but it will be efficient enough that it won’t change the linear bound.)
ENHANCE the implementation of IntArrayList so that it has an addBefore method. Instead of adding an element to the end, addBefore adds it to the beginning, at index 0, causing all existing elements to move forward (their indexes increased by 1). However, like add, your addBefore method must also guarantee that only O(π) time is needed to perform n addBefores and adds. To accomplish this, as with add, most calls to addBefore must execute very quickly, in O(1) time. The changes you make to IntArrayList should preserve the property that the get and set methods take a constant amount of time (not proportional to the array size) and the above property of add that only a linear number of elements is copied.
There are several ways to accomplish this task. Perhaps the easiest: double the array when you hit the beginning, but instead of copying the old array to the beginning of the new array, copy it to the end (leaving all the unused spaces that are still at the end). You will also need to change the implementation of some other methods (because elements will be indexed differently with this ENHANCEment) and add an additional instance field (to track extra information). The existing methods should continue to have their existing O runtimes as seen in the comment. Start with the IntArrayList implementation found on Canvas, which will resemble what we did in class. It will have an empty addBefore method which you will need to fill in. A tester program will be released which will attempt to empirically test that your program takes only O(π) time to perform n addBefores and adds (after testing that it seems to work, along with verifying that the other methods seem to work).
For reference, on the next page is a program listing for IntArrayList. EXTRA CREDIT 3 POINTS: Notice that the above technique will “run out of space” when there is extra room left on the opposite end of the array. Instead, utilize the whole array before triggering any copying (preserving performance as above).
IntArrayList.java
https://s3.amazonaws.com/iedu-attachments-question/1a7c261e6fe4e9ac4c53a7dafdc66912_9e363e473651ccb932a3a91ef3744f50.java
Test.java
https://s3.amazonaws.com/iedu-attachments-question/b2b38dd694253f968512eee7f3fae389_942b0d9299616669347271a4d1283d97.java
Solution:
https://gist.github.com/Devenc234/bb327ea658693879b052be2a58a69488
Problem Statement:
https://s3.amazonaws.com/iedu-attachments-question/123a48466fba8185a34ed0161c8a92b9_5e027b67d2eb9ef5ab1473885070b82c.pdf
In class, we implemented an IntArrayList class which internally had an array of integers but ENHANCEd it by making it easy to add new elements to the end. We saw that adding π elements to an IntArrayList would only take O(π) time. It accomplished this by doubling the underlying size of the array and copying the old array every time it ran out of space. If π total elements are added to the array, in the worst case, the array might have run out of space and had to copy itself when the very last (πth) element was added, when the π 2 nd element was added, π 4 th, π 8 th, and so on down to the starting size of the array. Every time the array runs out of space, it needs to copy all the elements from the old array to the new array. However, even as π becomes very large and this series becomes arbitrarily long, π < π + π 2 + π 4 + π 8 + π 16 + ⋯ ≤ 2π. In other words, the total number of elements we need to copy over the lifetime of an IntArrayList is bounded above by a linear function of the total number of elements added to it. (Allocating the array each time we copy is additional work which depends on the memory allocation algorithm used, but it will be efficient enough that it won’t change the linear bound.)
ENHANCE the implementation of IntArrayList so that it has an addBefore method. Instead of adding an element to the end, addBefore adds it to the beginning, at index 0, causing all existing elements to move forward (their indexes increased by 1). However, like add, your addBefore method must also guarantee that only O(π) time is needed to perform n addBefores and adds. To accomplish this, as with add, most calls to addBefore must execute very quickly, in O(1) time. The changes you make to IntArrayList should preserve the property that the get and set methods take a constant amount of time (not proportional to the array size) and the above property of add that only a linear number of elements is copied.
There are several ways to accomplish this task. Perhaps the easiest: double the array when you hit the beginning, but instead of copying the old array to the beginning of the new array, copy it to the end (leaving all the unused spaces that are still at the end). You will also need to change the implementation of some other methods (because elements will be indexed differently with this ENHANCEment) and add an additional instance field (to track extra information). The existing methods should continue to have their existing O runtimes as seen in the comment. Start with the IntArrayList implementation found on Canvas, which will resemble what we did in class. It will have an empty addBefore method which you will need to fill in. A tester program will be released which will attempt to empirically test that your program takes only O(π) time to perform n addBefores and adds (after testing that it seems to work, along with verifying that the other methods seem to work).
For reference, on the next page is a program listing for IntArrayList. EXTRA CREDIT 3 POINTS: Notice that the above technique will “run out of space” when there is extra room left on the opposite end of the array. Instead, utilize the whole array before triggering any copying (preserving performance as above).
IntArrayList.java
https://s3.amazonaws.com/iedu-attachments-question/1a7c261e6fe4e9ac4c53a7dafdc66912_9e363e473651ccb932a3a91ef3744f50.java
Test.java
https://s3.amazonaws.com/iedu-attachments-question/b2b38dd694253f968512eee7f3fae389_942b0d9299616669347271a4d1283d97.java
Solution:
https://gist.github.com/Devenc234/bb327ea658693879b052be2a58a69488
Comments
Post a Comment