4. (15 pts) There is an algorithm called array doubling that is used to increase
ID: 3743984 • Letter: 4
Question
4. (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
int[] a = new int[1];// start with array size 1.
int x; //declare variable to store value form user
int n=0; // n is index which indicate elements
while(sc.hasNextInt()) // while loop to enter element in array and it will double array size when array is full
{
x=sc.nextInt() //accept the value
if(n==a.length) //array size is full.....increase the size to double
{
int[] h = new int[2*a.length]; // new array with double size
for (int i =0;i <a.length;i++) //put old values in new array
h[i]=a[i];
a=h // now a will indicate new array h
}
a[n] =x; // when if condition is false put new number in a array
n++; // increment index position
}
if(n<a.length) // after inserting all values in array check whether array size is half full
{
int h[]= new int[a.length/2+1]; // cut size to half of array size
for( int i =0;i<h.length;i++)
h[i]=a[i]; // copy old values in new array h
a==h; // a points to new array
}
// finish now print the values from array a and print the size of array also
for(int i =0;i<a.length;i++)
//print values using a[i]
//print new length using a.length;
Explaination of algorithm:
First while loop will check if space is there in array or not.If space is not available for new element it will use array doubling algorithm.After inserting all the values if block check size and applies underflow strategy whenever array falls below half full.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.