(15 pts) There is an algorithm called array doubling that is used to increase th
ID: 3743337 • Letter: #
Question
(15 pts) There is an algorithm called array doubling that is used to increase the size of an array to accommodate new data when an array fills up. In the algorithm, when an array fills up, a new array is created dynamically that is 2x the size of the original, the data is copied to the new array, and the old array is destroyed. (a) Write an algorithm to implement an underflow strategy that cuts the array size in half whenever the array falls below half full (b) Specify the loop invariant in your algorithm. (c) Explain how your algorithm maintains the loop invariant.
Explanation / Answer
Algorithm for underflow strategy:
For the loop invariant, we are checking the value of the loop variable variable and check it with the value of half the element in the array. If half the array element are deleted then we will reduce the size of the array to half and repeat the procedure
We will also check for the index to be 0 or less, so in this condition array has only one element or none. So in both the case we would not be able to half the array. So if this condition is met we will break the loop
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.