Java programming questionPlease help me with C 7.31: 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 arraycapacity, the array shrinks to half its size.C-7.30 Prove that when using a dynamic array that grows and shrinks as in the previousexercise, the following series of 2n operations takes O(n) time: n insertions atthe end of an initially empty list, followed by n deletions, each from the end ofthe 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. 7.2.1 Dynamic ArraysThe ArrayList implementation in Code Fragments 7.2 and 7.3 (as well as those fora stack, queue, and deque from Chapter 6) has a serious limitation; it requires thata fixed maximum capacity be declared, throwing an exception if attempting to addan element once full. This is a major weakness, because if a user is unsure of themaximum size that will be reached for a collection, there is risk that either toolarge of an array will be requested, causing an inefficient waste of memory, or thattoo small of an array will be requested, causing a fatal error when exhausting thatcapacity.Java's ArrayList class provides a more robust abstraction, allowing a user toadd elements to the list, with no apparent limit on the overall capacity. To providethis abstraction, Java relies on an algorithmic sleight of hand that is known as adynamic array.In reality, elements of an ArrayList are stored in a traditional array, and theprecise size of that traditional array must be internally declared in order for thesystem to properly allocate a consecutive piece of memory for its storage. Forexample, Figure 7.2 displays an array with 12 cells that might be stored in memory2157 on a computerlocations 2146 throughsystem.21442145214621472148214921502151215221532154215521562157215821592160XXFigure 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 arraylist instance maintains an internal array that often has greater capacity than thecurrent length of the list. For example, while a user may have created a list withfive elements, the system may have reserved an underlying array capable of storingeight object references (rather than only five). This extra capacity makes it easy toadd 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 underly-ing array will eventually be exhausted. In that case, the class requests a new, largerarray from the system, and cop all references from the smaller array into thebeginning 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, this strategy is much like that ofthe hermit crab, which moves into a larger shell when it outgrows its previous one.

As we know ,Push refers to inserting an element in the stack. Also as there's only one position at which the new element can be inserted i.e Top of the stack, the new element is inserted at the top of the stack, Pop operation refers to the removal of an elementIn the below Diagram to use stack efficiently, we need to check the status as well. For the same purpose, the following functionality is added to stacks. Push() - Pushing (storing) an element on the stack. * Pop() - Removing (accessing) an element from the stack.

Engineering

Computer Science

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.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.

Database System Concepts

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

See similar textbooks

Similar questions

What are some of the advantages of using encapsulation in Java?
Why is JAVA so object-oriented focused/heavy?
In c#. Print the line given below: "Basic learning module of C#"
In Java, What is abstraction and what advantage does it provide? Please provide code example.
What are some of the benefits of using encapsulation in Java?
Describe differences between inheritance and polymorphism in java.
In java please
Explain Final keyword in java?
Math 130 Java Programming Does my code pass the requirements? May I have more explanation? Does my code compile correctly? Is my code readable? Is my code well commented? How may I better organize my code? Are there whitespaces to appropriate help separate distinct parts? My code: import java.util.Scanner; public class TicketSale { public static void main(String[] args) { Scanner keyboard = new Scanner(System.in); //Prompt user to input the number of Adult tickets to purchase System.out.print("Please enter number of adults:"); //Prompt user to input the number of Adult tickets to purchase int adults = keyboard.nextInt(); //Prompt user to input the number of Children tickets to purchase System.out.print("Please enter number of children:"); //Prompt user to input the number of Children tickets to purchase int children = keyboard.nextInt(); //Calculate and display the total cost for adults and children System.out.print("Your total cost for " + adults +…
What do you understand by function overloading explain with code in java programming.