Make a copy of the stack for back-up purposes

Assignment Help JAVA Programming

Reference no: EM132093890

Please answer clearly as required.

Problem 1 : In class, we used amortized analysis to study the extensible array problem. An extensible array is a type of data structure that is like an array, but is resized when it becomes full. The extensible array supports only one operation: "insert". It works as follows: Initially, the array has space for just one element.

Suppose that the array is currently of size k and is full. Then if you attempt to insert an element, the OS will allocate new memory of size 2k, and all k elements currently in the array will be copied to the new location and then the new element will be written.

In class, we assumed that writing or copying an element cost $1, and allocating memory was free. Suppose now that writing or copying an element still costs $1, but now we must also pay $1 for each unit of memory that is allocated. (In other words, if we allocate 2k units of memory, we must pay $2k.)

Perform an amortized analysis of the running time of n insert operations on an extensible array, under the new cost model. State your answer in terms of the average cost per operation, in dollars (that is, do not use big-O notation).

Problem 2 : Suppose that we have a stack whose size is not allowed to exceed K (for instance, if K 10, then we are not allowed to have more than 10 elements on the stack at any time).

If you try to Push an element onto a stack that is already full, then nothing happens. Suppose that after every K operations, we automatically make a copy of the stack for back-up purposes.

(Note the stack may or may not be full at this point.) Suppose that Push and Pop each cost $1 (including if you try to Push an element onto an already-full stack).

Suppose that copying the stack costs SC, where C is the number of elements currently on the stack. Perform an amortized analysis of the running time of n operations. State your answer in terms of the average cost per operation, in dollars (that is, do not use big-O notation).

Reference no: EM132093890

Questions Cloud

How do you think stakeholders will rely on the assurances : Assume you are a member of this taskforce; discuss what types of assertions you would expect your client's management to make regarding socially responsible.

Input various sentences as c-strings and perform conversions : Reverse the order of the words, and print all letters in upper case; there will be no punctuation in this version.

Considered before starting computer forensic engagements : What are the legal factors that should be considered before starting computer forensic engagements?

What kind of pension plans do coca-cola and pepsico provide : The financial statements of Coca-Cola and PepsiCo are presented in Appendices C and D, respectively. The companies' complete annual reports, including.

Make a copy of the stack for back-up purposes : Suppose that after every K operations, we automatically make a copy of the stack for back-up purposes.

Describe the elements of sales promotion brief : List and describe the elements of a sales promotion brief. Describe the various way sampling can be utilized.

Different types of environmental variables and its importanc : Consider the environmental variables (i.e., technological, demographic, economic, political, and cultural variables) that you must include in your marketing

What are the four of positions in a hotel : What are the four of positions in a hotel? How does ADA impact the hotel industry?

Write a program in java to read five integers and print : Write a program in Java to read 5 integers and print and print the minimum and maximum values .Use while loop and if statements in your code.

User Account

All Pages