Java programming languagePlease help with question: C 7.33: **Exercise C-7.29**Revise the array list implementation given in Section 7.2.1 so that when the actual number of elements, \( n \), in the array goes below \( N/4 \), where \( N \) is the array capacity, the array shrinks to half its size.**Exercise C-7.30**Prove that when using a dynamic array that grows and shrinks as in the previous exercise, the following series of \( 2n \) operations takes \( O(n) \) time: \( n \) insertions at the end of an initially empty list, followed by \( n \) deletions, each from the end of the list.**Exercise C-7.31**Give a formal proof that any sequence of \( n \) push or pop operations (that is, insertions or deletions at the end) on an initially empty dynamic array takes \( O(n) \) time, if using the strategy described in Exercise C-7.29.**Exercise C-7.32**Consider a variant of Exercise C-7.29, in which an array of capacity \( N \) is resized to capacity precisely that of the number of elements, any time the number of elements in the array goes strictly below \( N/4 \). Give a formal proof that any sequence of \( n \) push or pop operations on an initially empty dynamic array takes \( O(n) \) time.**Exercise C-7.33**Consider a variant of Exercise C-7.29, in which an array of capacity \( N \) is resized to capacity precisely that of the number of elements, any time the number of elements in the array goes strictly below \( N/2 \). Show that there exists a sequence of \( n \) push and pop operations that requires \( \Omega(n^2) \) time to execute. 7.2.1 Dynamic ArraysThe ArrayList implementation in Code Fragments 7.2 and 7.3 (as well as those for a stack, queue, and deque from Chapter 6) has a serious limitation; it requires that a fixed maximum capacity be declared, throwing an exception if attempting to add an element once full. This is a major weakness, because if a user is unsure of the maximum size that will be reached for a collection, there is risk that either too large of an array will be requested, causing an inefficient waste of memory, or that too small of an array will be requested, causing a fatal error when exhausting that capacity.Java’s ArrayList class provides a more robust abstraction, allowing a user to add elements to the list, with no apparent limit on the overall capacity. To provide this abstraction, Java relies on an algorithmic sleight of hand that is known as a dynamic array.In reality, elements of an ArrayList are stored in a traditional array, and the precise size of that traditional array must be internally declared in order for the system to properly allocate a consecutive piece of memory for its storage. For example, Figure 7.2 displays an array with 12 cells that might be stored in memory locations 2146 through 2157 on a computer system.**[Figure 7.2: An array of 12 cells, allocated in memory locations 2146 through 2157.]**Because the system may allocate neighboring memory locations to store other data, the capacity of an array cannot be increased by expanding into subsequent cells.The first key to providing the semantics of an unbounded array is that an array list instance maintains an internal array that often has greater capacity than the current length of the list. For example, while a user may have created a list with five elements, the system may have reserved an underlying array capable of storing eight object references (rather than only five). This extra capacity makes it easy to add a new element to the end of the list by using the next available cell of the array.If a user continues to add elements to a list, all reserved capacity in the underlying array will eventually be exhausted. In that case, the class requests a new, larger array from the system, and copies all references from the smaller array into the beginning of the new array. At that point in time, the old array is no longer needed, so it can be reclaimed by the system. Intuitively,

Here we need to compare stack and queueStack is LIFO organisation i.e.-Last in first out whereas…

C-7.29 Revise the array list implementation given in Section 7.2.1 so that when the ac- tual number of elements, n, in the array goes below N/4, where N is the array capacity, the array shrinks to half its size. C-7.30 Prove that when using a dynamic array that grows and shrinks as in the previous exercise, the following series of 2n operations takes O(n) time: n insertions at the end of an initially empty list, followed by n deletions, each from the end of the list. C-7.31 Give a formal proof that any sequence of n push or pop operations (that is, in- sertions or deletions at the end) on an initially empty dynamic array takes O(n) time, if using the strategy described in Exercise C-7.29. C-7.32 Consider a variant of Exercise C-7.29, in which an array of capacity N is resized to capacity precisely that of the number of elements, any time the number of elements in the array goes strictly below N/4. Give a formal proof that any sequence of n push or pop operations on an initially empty dynamic array takes O(n) time. C-7.33 Consider a variant of Exercise C-7.29, in which an array of capacity N, is resized to capacity precisely that of the number of elements, any time the number of elements in the array goes strictly below N/2. Show that there exists a sequence of n push and pop operations that requires (n²) time to execute.

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE