ITI 1121. Introduction to Computer Science II Laboratory 10 Summer 2016 Objectives:  Part A: Solving two questions.  Part B: Further understanding of (doubly) linked lists and interfaces. Part A: In this part the TA will solve the following questions. The students need not hand anything for this part. Question 1 The class DynamicArrayStack below increases or decreases its physical size according to the needs of the application. • DynamicArrayStack uses an array to store the elements of this stack; • The interface Stack and its implementation, DynamicArrayStack, have a formal parameter type (in other words, the implementation uses the concept of generics types, introduced in Java 1.5); • The initial capacity of this array is given by the first parameter of the constructor; • The physical size of the array is increased by a fixed amount (increment) when the method void push( E elem ) is called and the array is full; • The physical size of the array is decreased by a fixed amount (increment) during a call to the method E pop() if the number of free cells becomes increment or more; • The increment is given by the second parameter of the constructor; • The instance variable top designates the top element (i.e. the cell where the last element was inserted, or -1 if the stack is empty). A. Correct at least 5 mistakes (compile-time or runtime errors) in the partial implementation (see next two pages) by marking the error with a circle and writing down the correction.(10 marks) B. Complete the partial implementation of the class DynamicArrayStack given the above information. (10 marks) // Instance variables private static E[] elems; // Stores the elements of this stack private static int top = -1; // Designates the top element private final int capacity; // Memorizes the initial capacity private final int increment; // Used to increase/decrease the size public DynamicArrayStack( int capacity, int increment ) { E[] elems = new Object[ capacity ]; this.capacity = capacity; this.increment = increment; } // Returns true if this stack is empty; public boolean isEmpty() { return top == 0; } public void push( E element ) { if ( ___________________________ ) { increaseSize(); } elems[ top ] = element; top++; } private void increaseSize() { E[] newElems; int newSize; newSize= elems.length + increment; newElems = ___________________________; for ( int i=0; i= obj.length) { Object[ ] tmp= obj; obj= new Object[tmp.length * 3 / 2]; for (int i=0; i > { public abstract int size(); public abstract boolean add( T elem ) throws IllegalArgumentException; public abstract T get( int pos ) throws IndexOutOfBoundsException; public abstract void remove( int pos ) throws IndexOutOfBoundsException; } The added benefit of using generics will be that all the elements of a list will be of the same type. Therefore, the method compareTo( other ) will always be passed an object of the same type as the instance. o OrderedStructure.java o OrderedList.java o OrderedListTest.java 4 Quiz (1 mark) For the ArrayList implementation of the interface List. 1. Insertions at intermediate positions are always fast. 2. Adding an element at the first position is always fast. 3. Removing an element is always fast. 4. Reading the value of an intermediate position is always fast.  Write your answer to the above question directly in the Submission text field of the submission Web page;  https://uottawa.blackboard.com/ Last Modified: July 9, 2016