With that in mind, please answer q1 part a and b only:
Part 5: Amortized Analysis Consider the append() operation for a Dynamic Array. In the best case, the operation is O(1). This corresponds to the case where there was room in the space we have already allocated for the array. However, in the worst case, this operation slows down to O(n). This corresponds to the case where the allocated space was full and we must copy each element of the array into a new (larger) array. This problem is designed to discover runtime bounds on the average case when various array expansion strategies are used, but first, some information on how to perform an amortized analysis is necessary. 1. Each time an item is added to the array without requiring reallocation, count 1 unit of cost. This cost will cover the assignment which actually puts the item in the array. 2. Each time an item is added and requires reallocation, count X + 1 units of cost, where X is the number of items currently in the array. This cost will cover the X assignments which are necessary to copy the contents of the full array into a new (larger) array, and the additional assignment to put the item which did not fit originally. To make this more concrete, if the array has 3 spaces and is holding 2 items, adding the third will cost 1. However, if the array has 3 spaces and is holding 3 items currently, adding the 4th item will actually cost 4 (3 to move the existing items + 1 to assign the 4th item once space is available). Now our goal is to calculate how many "units are spent in the entire sequence of N append operations then use it to find the average "unit" cost for an append. When we can bound an average cost of an operation in this fashion, we call it amortized execution time. Note that this method charges the same amortized execution time to each operation in the sequence of N append operations even though the same operation will experience very different costs across a sequence. It relies on the fact that many of the operations in the sequence contribute little cost and only a few operations contribute a high cost to the overall time. In a file called amortized Analysis.pdf, please provide answers to the following questions: 1. How many cost units are spent in the entire process of performing 40 consecutive append operations on an empty array which starts out at capacity 3, assuming that the array will double in capacity each time a new item is added to an already full dynamic array? As N (i.e., the number of appends) grows large, under this strategy for resizing, what is the amortized big-O complexity for an append? 2. How many cost units are spent in the entire process of performing 40 consecutive append operations on an empty array which starts out at capacity 3, assuming that the array will grow by a constant 2 spaces each time a new item is added to an already full dynamic array? As N (i.e., the number of appends) grows large, under this strategy for resizing, what is the amortized big-O complexity for an append? Questions: a) The calculation can be shown in the following table(when N= 40): 6 Append 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Write Cost 1 1 1 1 Copy Cost 3 You finish the rest of the calculation! Total Cost 1 2 3 7 Append 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 Write Cost Copy Cost Total Cost b) As N (i.e., the number of appends) grows large, under this strategy for resizing, the average big-o complexity for an append can be derived using the following calculation: Mathematically, total cost = total write cost (Sw) + total copy cost (Sn). The total write cost, Sw= N. Recall (from the table you prepared in part (a)) the copy cost is a sequence as follows: 3, 6, 12, ... (a geometric sequence) Now, what is the cost of the last resize (kth term of the sequence)? The kth term is derived from the following equation, and you will assume the sequence contains k terms: ak= a pk-1 (where ay is the first term andr is the ratio). In this instance: ak= (you have to calculate it) Part 5: Amortized Analysis Consider the append() operation for a Dynamic Array. In the best case, the operation is O(1). This corresponds to the case where there was room in the space we have already allocated for the array. However, in the worst case, this operation slows down to O(n). This corresponds to the case where the allocated space was full and we must copy each element of the array into a new (larger) array. This problem is designed to discover runtime bounds on the average case when various array expansion strategies are used, but first, some information on how to perform an amortized analysis is necessary. 1. Each time an item is added to the array without requiring reallocation, count 1 unit of cost. This cost will cover the assignment which actually puts the item in the array. 2. Each time an item is added and requires reallocation, count X + 1 units of cost, where X is the number of items currently in the array. This cost will cover the X assignments which are necessary to copy the contents of the full array into a new (larger) array, and the additional assignment to put the item which did not fit originally. To make this more concrete, if the array has 3 spaces and is holding 2 items, adding the third will cost 1. However, if the array has 3 spaces and is holding 3 items currently, adding the 4th item will actually cost 4 (3 to move the existing items + 1 to assign the 4th item once space is available). Now our goal is to calculate how many "units are spent in the entire sequence of N append operations then use it to find the average "unit" cost for an append. When we can bound an average cost of an operation in this fashion, we call it amortized execution time. Note that this method charges the same amortized execution time to each operation in the sequence of N append operations even though the same operation will experience very different costs across a sequence. It relies on the fact that many of the operations in the sequence contribute little cost and only a few operations contribute a high cost to the overall time. In a file called amortized Analysis.pdf, please provide answers to the following questions: 1. How many cost units are spent in the entire process of performing 40 consecutive append operations on an empty array which starts out at capacity 3, assuming that the array will double in capacity each time a new item is added to an already full dynamic array? As N (i.e., the number of appends) grows large, under this strategy for resizing, what is the amortized big-O complexity for an append? 2. How many cost units are spent in the entire process of performing 40 consecutive append operations on an empty array which starts out at capacity 3, assuming that the array will grow by a constant 2 spaces each time a new item is added to an already full dynamic array? As N (i.e., the number of appends) grows large, under this strategy for resizing, what is the amortized big-O complexity for an append? Questions: a) The calculation can be shown in the following table(when N= 40): 6 Append 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Write Cost 1 1 1 1 Copy Cost 3 You finish the rest of the calculation! Total Cost 1 2 3 7 Append 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 Write Cost Copy Cost Total Cost b) As N (i.e., the number of appends) grows large, under this strategy for resizing, the average big-o complexity for an append can be derived using the following calculation: Mathematically, total cost = total write cost (Sw) + total copy cost (Sn). The total write cost, Sw= N. Recall (from the table you prepared in part (a)) the copy cost is a sequence as follows: 3, 6, 12, ... (a geometric sequence) Now, what is the cost of the last resize (kth term of the sequence)? The kth term is derived from the following equation, and you will assume the sequence contains k terms: ak= a pk-1 (where ay is the first term andr is the ratio). In this instance: ak= (you have to calculate it)
