(a)
Describe thenumber of disk accesses and CPU time for n stack operations in worse-case by using the simple implementation.
(a)
Explanation of Solution
In worse case for every stack operation it requires disk access for implementation sothe number of disk accesses for n stack operations using this simple implementation is asymptotically equals to
The CPU time in worse case for n -stack operations is
(b)
Describethe number of diskaccesses and the CPU time required for n -PUSH operations in worse-case.
(b)
Explanation of Solution
The new page starts only when everymthpushes therefore the number of disk operations is n/m. The diskaccess requires time of asymptotically
Hence,the number of disk accesses and CPU time for n - PUSH operations in worse-case is
(c)
Describe the disk accesses and the CPU time required for n -stack operations in worse-case.
(c)
Explanation of Solution
Stack operations include PUSH and POP. The PUSH and POP operations requires alternate disk accesses that means mdisk accesses for performing stack operation so the number of disk accesses asymptotically is
The CPU time for performing stack operations is equal to
(d)
Describe that the amortized number of disk accesses is O (1 /m ) and the amortized CPU time is O (1) for any stack operation .
(d)
Explanation of Solution
At the initial function called as Potential Function of stack defined by difference of size of stack and recent pass which is multiple of m. The value of potential function is 0 at initial state.
When any stack operation is performed the value is decreased and increased according to the operation by one.Loading new pages requires the position which is at leastm position away from recent position to cross the page boundary therefore loading and storing of new stack page requires CPU time of O ( m ).
By dropping appropriate Potential function of order O ( m ) and selecting the suitable value for potential value results to managed the stack pages so that the amortized number of disk accesses for any stack operation is O (1 /m ) and the amortized CPU time for any stack operation is O (1).
Want to see more full solutions like this?
- Java : Write the Java code segment that uses a stack to determine if a string is a palindrome (assume all that blanks have been removed). A palindrome contains the same characters forwards as backwards, for example level is a palindrome. Your solution must use only a stack, you MUST process the string from left to right, and are allowed to go through the string only once. You must use an efficient algorithm. Use : ArrayStack class given below: /** * Creates an empty stack using the default capacity. */ public ArrayStack() { this(DEFAULT_CAPACITY); } /** * Creates an empty stack using the specified capacity. * @param initialCapacity the initial size of the array */ public ArrayStack(int initialCapacity) { top = 0; stack = (T[])(new Object[initialCapacity]); }arrow_forwardA drop-out stack is a data structure that acts just like a stack except that if the stack size is n, and the n + 1 element is pushed, the first element is lost. Using an array, create a drop-out stack. (Hint: A circular array implementation would be appropriate.)arrow_forward4. Sort elements in an array-based stack in ascending order, i.e. make the smallest element to be the top element of the stack. E.g. given the stack elements (from bottom to top): 90, 70, 80, 10, sort the elements to make the stack elements become (from bottom to top): 90, 80, 70, 10. The only data structure you can use is array-based stack. In addition to the given stack, you can use only one extra stack to store some temporary data. Given a stack st, use one extra stack, tmpst, to store temporary data. Here are some hints of the idea. Pop out the top element of st to a variable tmp. If the stack tmpst is empty, push tmp onto tmpst; if tmpst is not empty, pop out its top element and push that element onto st until the top element of tmpst is smaller than tmp, then push tmp onto tmpst .. a. Write a program to implement the stack based sorting. b. Take the input (90, 70, 80, 10) as an example. c. Print all the push and pop operations in proper format. d. At the end, print the sorted…arrow_forward
- Question3. Using the Stack class implemented in JAVA, write a JAVA code to do the following: a. Create an array of integers containing the following elements: 5, -1, 7,8,9,4,15 b. Create an empty stack (call it nums) and push all the array elements onto the stack. c. Using a temporary stack to reverse the content of the stack nums then print it. d. Display all odd elements from the stack nums.arrow_forwardJAVA You are given a stack with n integers. You need to sort the elements of the stack in ascending order such that the minimum value is at the bottom-most position of the stack. Input Format: The first line of input is the number of elements in the stack. The next line of input consists n space separated integers in the order bottom to top. Output Format: The output is sorted stack with minimum value at bottom of the stack and maximum value at the top of the stack. Example: Stack(bottom -> top) = [6, 12, 3, 4] Output: [3, 4, 6,12] Sample Input: 12 6 12 3 4 5 1 7 8 10 9 11 2 Sample Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] Note: You can use extra stack if needed. import java.util.*; public class Source { public static void main(String args[]) { Stack stack = new Stack<>(); Scanner s = new Scanner(System.in); int n = s.nextInt(); while (n-- > 0) stack.push(s.nextInt()); sort(stack); } // Method to sort the elements of the stack in ascending order static…arrow_forwardJava Programming Hello! Can you make an algorithm / code for this part for my java calculator application. (see attached photo) All basic operations are already working, only the M's are needed to be implemented. Contains 'M+', 'M-', 'MC', 'MR' buttons(used to temporarily store data) with the corresponding stack functionalities as follows: 'M+' is push 'M-' is pop 'MC' is clear stack 'MR' is peakarrow_forward
- The stack is a helpful data structure for various computer problems, as demonstrated by the c#bprogramme. We begin with the rightmost digits and move leftward when changing a decimal number into another format. The converted digits are in the right sequence after we're done, so pushing each digit up the stack as we go works properly.arrow_forwardStack: push(x) adds x to top of stack pop() removes top element of stack and returns it size() returns number of elements in stack Select all options that allow for an efficient implementation based on the discussions from class. For any array implementation, you can assume the array is large enough so that making a larger one is not needed when pushing an item to the stack. Using an array with the top at the front of the array. Using an array with the top at the back of the array. Using a singly linked list with the top at the head of the list. Using a singly linked list with the top at the tail of the list. None of these choices allows for an efficient implementation of all methods.arrow_forwardmultiply choice recursion questionarrow_forward
C++ Programming: From Problem Analysis to Program...Computer ScienceISBN:9781337102087Author:D. S. MalikPublisher:Cengage Learning
Systems ArchitectureComputer ScienceISBN:9781305080195Author:Stephen D. BurdPublisher:Cengage Learning