Question

The following questions relate to implementations of unbounded arrays. Read both parts before answering either of them.
i. Describe an implementation of an unbounded array that has amortised cost of O(1) on both pushBack and popBack operations. In your description make sure you say how and when the necessary allocations and deallocation operations are performed.

ii. Use amortised analysis to demonstrate that pushBack and popBack can be performed on the structure you described in part (i) above at an amortised cost of O(1).

Answer 1

i.  Assume you have an array-based binary heap: a. with the contents: 1,4,7,8,9, 10,14, 12,15, 13, 17,12 Show the contents of a after each of the following two operations Show your working for each operation including the content of the list at its intermediate stages. You can assume a is large enough to contairn all the values inserted. insert 5 into a . deleteMin of a (b) The following questions relate to implementations of unbounded ar- rays. Read both parts before answering either of them. i. Describe an implementation of an unbounded array that has amor tised cost of O(1) on both pushBack and popBack operations. In your description make sure you say how and when the necessary allocations and deallocation operations are performed. ii. Use amortised analysis to demonstrate that pushBack and popBack can be performed on the structure you described in part (i) above at an amortised cost of O(1).

ii. Amortised Analysis is used for algorithms where an occasional operation is very slow, but most of the other operations are faster. In Amortized Analysis, we analyze a sequence of operations and guarantee a worst case average time which is lower than the worst case time of a particular expensive operation.
The example data structures whose operations are analyzed using Amortized Analysis are Hash Tables, Disjoint Sets and Splay Trees.

Let us consider an example of a simple hash table insertions. How do we decide table size? There is a trade-off between space and time, if we make hash-table size big, search time becomes fast, but space required becomes high.

The solution to this trade-off problem is to use Dynamic Table (or Arrays). The idea is to increase size of table whenever it becomes full. Following are the steps to follow when table becomes full.
1) Allocate memory for a larger table of size, typically twice the old table.
2) Copy the contents of old table to new table.
3) Free the old table.

If the table has space available, we simply insert new item in available space.