cheyennecarrillo14
21.04.2020 •
Computers and Technology
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 8 spaces and is holding 5 items, adding the sixth will cost 1. However, if the array has 8 spaces and is holding 8 items, adding the ninth will cost 9 (8 to move the existing items + 1 to assign the ninth item once space is available).
When we can bound an average cost of an operation in this fashion, but not bound the worst case execution time, we call it amortized constant execution time, or average execution time. Amortized constant execution time is often written as O(1+), the plus sign indicating it is not a guaranteed execution time bound.
In a file called amortizedAnalysis.txt, please provide answers to the following questions:
1. How many cost units are spent in the entire process of performing 16 consecutive push operations on an empty array which starts out at capacity 8, assuming that the array will double in capacity each time new item is added to an already full dynamic array? Now try it for 32 consecutive push operations. As N (ie. the number of pushes) grows large, under this strategy for resizing, what is the big-oh complexity for push?
2. How many cost units are spent in the entire process of performing 16 consecutive push operations on an empty array which starts out at capacity 8, assuming that the array will grow by a constant 2 spaces each time new item is added to an already full dynamic array? Now try it for 32 consecutive push operations. As N (ie. the number of pushes) grows large, under this strategy for resizing, what is the big-oh complexity for push?
Solved
Show answers
More tips
- C Computers and Internet Best Applications for Your iPad: Review of the Best Candidates for Installation...
- S Style and Beauty Intimate Haircut: The Reasons, Popularity, and Risks...
- A Art and Culture When Will Eurovision 2011 Take Place?...
- S Style and Beauty How to Choose the Perfect Hair Straightener?...
- F Family and Home Why Having Pets at Home is Good for Your Health...
- H Health and Medicine How to perform artificial respiration?...
- H Health and Medicine 10 Tips for Avoiding Vitamin Deficiency...
- F Food and Cooking How to Properly Cook Buckwheat?...
- F Food and Cooking How Many Grams Are In a Tablespoon?...
- L Leisure and Entertainment Carving: History and Techniques for Creating Vegetable and Fruit Decorations...
Answers on questions: Computers and Technology
- C Computers and Technology Informal group are often called task-orientedgroups. true false...
- C Computers and Technology In laissez-faire styleof group leadership, members of the group are not given inactivity plans by the leader only when it is requested. true false...
- C Computers and Technology In democratic style of group leadership, responsibilities areplaced on all members. true false...
- C Computers and Technology What does less-than-friendly error messages mean?...
- C Computers and Technology Let x be a string that belongsto {0, 1}* of length n. there is an fa that accepts only x. how many states arenecessary for this fa? [5 marks] [hint: put different values...
- C Computers and Technology Add the nodesgiven below to construct the avl tree show all the necessarysteps, 20,21,22,17,18,23,27,25,30,33,34...
- C Computers and Technology Which is likely to be longer (have more instructions): a program written for a zero-address architecture, a program written for a one-address architecture, or a program...
- C Computers and Technology How would you convert this base 10 decimal into a base 2number? : 36 r 210= *note: r means remainder* also just in general how would you convert any base numberwith a...
- C Computers and Technology What are the pros and cons of fixed-lengthand variable-length instructions? which is currently morepopular?...
- C Computers and Technology If i have student table in ms accesswith the following fields sid, name, father, dateof birth , degree, gender i- what is query to find duplicate record in thetable....
Ответ:
1. Average of total Cost = Total Cost/n = O(1)
2. Average of total Cost = Total Cost/n = O(n)
Explanation:
1) Array has Initial size of 8
For adding 16 elements
1. So Cost for first 8 element its 8.
2. On adding 9th element cost is (8+1) = 9 and array is resized to size of 16
3. Then for 10th,11th,12th,,16th element Cost is 7.
So total cost is 8 +9 + 7 = 24 ..So for adding 16 elements Cost is 24 units.
For adding 32 elements
1. So Cost for first 8 element its 8.
2. On adding 9th element cost is (8+1) = 9 and array is resized to size of 16
3. Then for 10th,11th,12th,,16th element total Cost is 7.
4. On adding 17th element cost is (16+1) = 17 and array is resized to size of 32.
5. Then for 18th,19th,20th,,32th element total Cost is 15.
So total cost is 8 +9 + 7 +17+15= 56 ..So for adding 32 elements Cost is 56 units.
We are Intrested in finding the Amortized Cost i.e Averga cost over large number of insertion:-
When the array size is doubled:-
N operation of N pushes will have cost of 1+2+4+8+16+.. + 2k where 2k < N, Summing upo the series we have
2k-1 - 2 . But 2k <=n <= 2k-1 So,
The total cost of the sequence of n insertions will be O(n) .
Since the Amortized Cost is the Average of total Cost = Total Cost/n = O(1)
2) resize by increasing the size by 2 elements
For adding 16 elements
1. So Cost for first 8 element its 8.
2. On adding 9th element cost is (8+1) = 9 and array is resized to size of 10
3. Then for 10th element Cost is 1
4. Then for 11th element Cost is 11
5.Then for 12th element Cost is 1
6.Then for 13th element Cost is 13
6.Then for 14th element Cost is 1
6.Then for 15th element Cost is 15
6.Then for 16th element Cost is 1
So total cost is 60 ..So for adding 16 elements Cost is 60 units.
For adding 32 elements
1. So Cost for first 8 element its 8.
2. On adding 9th element cost is (8+1) = 9 and array is resized to size of 10
3. Then for 10th element Cost is 1
4. Then for 11th element Cost is 11
5.Then for 12th element Cost is 1
7.Then for 13th element Cost is 13
8.Then for 14th element Cost is 1
9.Then for 15th element Cost is 15
10.Then for 16th element Cost is 1
11. Then for 17th element Cost is 17
12. Then for 18th element Cost is 1
13.Then for 19th element Cost is 19
14.Then for 20th element Cost is 1
15.Then for 21th element Cost is 21
16.Then for 22th element Cost is 1
17.Then for 23th element Cost is 23 .. . . .. .. Then for 31th element Cost is 31 .. . . . . . . . . .. Then for 32th element Cost is 1 .
So total cost is 260 ..So for adding 32 elements Cost is 260 units.
N operation of N pushes will have cost of 1+2+3+4+5+.. + N-1 = N(N-1)/2
The total cost of the sequence of n insertions will be O(n2) .
Since the Amortized Cost is the Average of total Cost = Total Cost/n = O(n)
Ответ:
Complete Question:
The first electric, general-purpose computer, ENIAC, was programmed by?
Group of answer choices.
A. Calculating algorithms on paper.
B. Entering code directly into the computer.
C. Flipping switches by hand.
D. Using MS-DOS as the operating system.
C. Flipping switches by hand.
Explanation:
The first electric, general-purpose computer, ENIAC, was programmed by flipping switches by hand.
ENIAC is an acronym for Electronic Numerical Integrator and Computer, it was developed in 1945 by John Mauchly and J. Presber Eckert. ENIAC was used for solving numerical problems or calculation-related tasks by the process of reprogramming.
In order to give the ENIAC a series of machine instructions to follow in the execution of a task, the programmers had to undergo the cumbersome procedure of connecting, removing, reconnecting cables and flipping switches by hand because data couldn't be stored in memory.