Chapter 1 Amortized Analysis
1.1 Exercise
(10 points)
Suppose we are doing a sequence of operations (numbered 1,2,3,…),
Copyright By PowCoder代写 加微信 powcoder
such that the ith operation:
– costs1ifiisnotapowerof2; – costsiifiisapowerof2.
For example, the following table shows the costs for each of the rst few operations:
Operation 1 2 3 4 5 6 7 8 9 … Cost 1 2 1 4 1 1 1 8 1 …
Give the best upper bound you can on the amortized cost per operation.
1.2 Exercise
(20 points)
Suppose we perform a sequence of stack operations on a stack whose size never exceeds k. After every k operations, we make a copy of the entire stack for backup purposes. Show that the cost of n stack operations, including copying the stack, is O(n) by assigning suitable amortized costs to the various stack operations.
1.3 Exercise
(20 points)
What is the time complexity of increment operation using Amortized analysis (show with both methods: aggregate and accounting) A is a bit string. Analyze number of bit ips.
1 2 3 4 5 6 7 8 9
• Aggregate analysis determines the upper bound T(n) on the total cost of a sequence of n operations, then calculates the amortized cost of an operation to be T(n)/n.
• Accounting method determines the individual cost of each operation, combining its immediate execution time and its influence on
the running time of future operations. Usually, many short-running operations accumulate a “debt” of unfavorable state in small increments, while rare long-running operations decrease it drastically. The costs of actions are represented by tokens. One token represent
an operation of one action in the computer. The cheap operations actually account for more token in the accounting method than they actually are (usually still O(1) but with higher constant), and when executing cheap immediate operations, the tokens are accumulated to credit for later \paying” for actual expensive operations.
input : A Increment(A[0…m−1])
while i
Exercises 1.2, page 1
Solution: Charge $2 for each PUSH and POP operation and $0 for each COPY. When we call PUSH, we use $1 to pay for the operation, and we store the other $1 on the item pushed. When we call POP, we again use $1 to pay for the operation, and we store the other $1 in the stack itself. Because the stack size never exceeds k, the actual cost of a COPY operation is at most $k, which is paid by the $k found in the items in the stack and the stack itself. Since there are k PUSH and POP operations between two consecutive COPY operations, there are $k of credit stored, either on
individual items (from PUSH operations) or in the stack itself (from POP operations) by the time a COPY occurs. Since the amortized cost of each operation is O(1) and the amount of credit never goes negative, the total cost of n operations is O(n).
Exercises 1.3, page 2
• Aggregate Method: Assume n increments starting from all 0s.
A[0] ips every increment for n ips.
A[1] ips every 2nd time for n/2 ips.
A[2] ips every 4th time for n/4 ips.
A[i] ips every 2ith time for n/2i i ips. Number of ips n + n/2 + n/4 + . . . = 2n O(n).
Therefore amortized cost of each operation is 2 = O(1).
• Accounting Method: Assume n increments starting from all 0s.
Increment ips exactly one bit from 0 to 1.
Assign an amortized cost of 2 tokens per increment.
Both tokens are assigned to the bit that is ipped from 0 to 1.
Use one token immediately for ip from 0 to 1.
Save other token for when it is ipped back to 0.
All bit ips are accounted for, so the total cost of 2n is number of bit ips.
Exercises 2.1, page 3
a) Worst-case running time with one: n elements examined (if x is at the end of A). With none: n elements examined. With half : bn/2c + 1 elements examined (if all the x ‘s are at the end of A ).
b) Average-case running time with one: (n + 1)/2 (x appears is each position with probability 1/n, so the average number of elements ex- amined is (1+2++n)/n = (n+1)/2. With none: n elements examined (the entire array must be searched, no matter what). With
half: the n/2x ‘s are distributed randomly among the n elements, and we want to nd the expected value of the rst index i such that A[i] = x. We can compare our distribution to a Bernoulli distribution: with probability 1/2, A[1] = x. Also, if A[i] 6= x for all i < j, then Pr[A[j] = x] 1/2. Under the Bernoulli distribution (where each probability is exactly 1/2 ), the expected number of elements exam- ined is 2. Since our distribution has even more mass at the lower values, our expectation is slightly less than 2. c) The answers for the randomized algorithm are exactly those of the average-case analysis of the deterministic algorithm, but we need not make any assumption about the input (because randomly permuting the array ensures that all inputs to the deterministic subroutine are equally likely). That is, with one: (n + 1)/2 examinations. With none: n examinations. With half: less than 2 examinations. Exercises 2.2, page 4 Solution: In the analysis of the min-cut algorithm, it was shown that the algorithm chooses a particular min-cut with probability 1/ n2 . If there were k dierent minimum cuts, then the probability that any one of them would be output is at least k/ n2 . This follows from the fact that these resultant events are all disjoint; if one min-cut is chosen then no other min-cut is chosen on that run of the algorithm. If there were 2 min-cuts, then the probability that any one at all would be chosen would be exactly 1. If there were more, the probability of a min-cut being found would be greater than one, which is a contradiction. Thus the number of min-cuts n in a graph cannot exceed 2 . Note that it is incorrect to argue that since the algorithm collapses edges until two vertices remain, and there are at most 2 pairs of vertices that could be left at the end, the number of min-cuts is bounded by the same number. This reasoning is unsound, as multiple reductions can lead to the same pair of nodes. Consider a ring graph with four nodes, numbered clockwise 1,2,3,4. One could reduce the graph to 1,2 by contracting 3 and 4 into 1, or contracting 3 and 4 into 2. The pair 1,2 represents at least two dierent cuts, one separating the graph into 1 and 2,3,4 and one into 1,3,4 and 2. Thus a pair can represent more than one minimum cut, and the argument that there are 2 pairs of vertices is insucient to prove the Exercises 2.3, page 4 Solution: Each node aibi sends a packet to node biai through node bibi. n/2 logN There are 2 = 2 2 packets that have to be routed through a given node xx. Half of these packets have to ip the n2 + 1 -st bit. All these messages have to cross the one edge that connects xx to the node with a p q dierent n2 + 1 -st bit. Therefore, at least 2N = Ω(pN) = Ω Nn steps are needed. Exercises 3.1, page 5 a) Answer: If ω is an outcome, i.e., a sequence of Heads and Tails of length n, then P(ω)= 1 2n Explanation: Whenever we pick the coin biased with p = 1, we always get Heads. Similarly, when we pick the coin biased with q = 0, we always get Tails. For a given ip, we are equally likely to use each coin, so the ip is equally likely to be Heads or Tails. Moreover, since we randomly pick the coin for each ip, all sequences are equally likely. Thus, we model all sequences as having the same probability: P(ω)= 1 = 1 |Ω| 2n Comment: For the curious, here is a generalization. Suppose the prob- ability of picking the rst coin is r and the probability of picking the second coin is 1 − r. Then, the probability of getting Heads on any given ip is r, so the probability of a sequence depends on the number of Heads and Tails. In particular, if ω is a sequence with k Heads and n − k Tails, P(ω) = rk(1 − r)n−k (The problem didn't ask to solve this generalization; this is here only for your edication.) b) Answer: No, it is dierent. The sample space includes only two outcomes, all Heads (HHH . . . H) and all Tails (TTT . . . T ). The prob- abilities are P(HHH...H) = P(TTT ...T) = 12 Equivalently, we can say that the sample space includes all possible sequences of n Heads and Tails, but the probability of a sequence is 0 if it is not HHH...H or TTT ...T Explanation: In this case, only two sequences are possible: HHH...H or TTT ...T i.e., we either get all Heads (if we choose the coin biased with prob- ability p = 1 ) or we get all Tails (if we choose the coin biased with probability q = 0 ). Since we are equally likely to pick either coin, we model this as P(HHH...H) = P(TTT ...T) = 1 = 1 |Ω| 2 Comment: This answer can also be generalized, if the probability of picking the rst coin is r. Then we get the following probability assignment: P(HHH...H)=r P(TTT...T)=1−r Exercises 3.2, page 6 a) Answer: If ω is a sequence with k Heads and n − k Tails, then 1 1 !k 1 1 !!n−k P(ω)= 2p+2q 1− 2p+2q Explanation: Assume each coin is chosen with probability 12 and consider a single ip. Since the probability of getting Heads with the rst coin is p and the probability of getting heads with the second coin is q, the probability of getting Heads on this ip is 2 p + 2 q. Similarly, the probability of getting Tails is 1− 21 p + 12 q We can then construct the probability of a sequence by multiplying the probabilities for each ip. Thus, the probability of getting a sequence with k heads and n−k tails is the probability of getting heads, to the k th power, times the probability of getting tails, to the n − k th power To provide a more rigorous explanation of the probability of Heads in the rst ip (this is not required for a full mark solution), denote R as the event that the coin with bias p is chosen and R as the event that the coin with bias q is chosen. Since R and R are disjoint and R [ R = Ω (i.e., R and R form a partition of all possible samples), the probability of getting P(H) = P(H \ R) + P (H \ Rc) = P(H | R)P(R) + P (H | Rc) P (Rc) = P ( H | R ) 21 + P ( H | R c ) 21 = 12 p + 12 q Since we get Tails whenever we don't get Heads, the probability of Tails is ! 1− 12p+ 12q = 12(1−p)+ 12(1−q) Comment: A generalization: If the probability of getting the coin with bias p is r, the probability of getting Heads is rp+(1−r)q, and thus the probability of a sequence ω with k heads and n − k tails is P(ω) = (rp+(1−r)q)k (1−(rp+(1−r)q))n−k b) Answer: If ω is a sequence with k Heads and n − k Tails, then P(ω) = 12pk(1 − p)n−k + 12qk(1 − q)n−k Explanation: If we only used the coin with bias p, P(ω) = pk(1 − p)n−k Likewise, if we only used the coin with bias q, we would have P(ω) = qk(1 − q)n−k Since we pick the coin before ipping the sequence, assuming each coin is chosen with probability 12 , we get P(ω) = 12pk(1 − p)n−k + 12qk(1 − q)n−k More formally (this is not required for a full mark solution), let ω be a sequence of length n and let h(ω) be the number of Heads in the sequence (thus, n − h(ω) is the number of Tails). As before, let R be the event that we use the coin with bias p and R be the event that we use the coin with bias q. Then P(ω | R) = ph(ω)(1 − p)n−h(ω) P (ω | Rc) = qh(ω)(1 − q)n−h(ω) and we have P(ω) = P(ω \ R) + P (ω \ Rc) = P(ω | R)P(R) + P (ω | Rc) P (Rc) = P ( ω | R ) 12 + P ( ω | R c ) 12 = 12ph(ω)(1 − p)n−h(ω) + 12qh(ω)(1 − q)n−h(ω) Comment: Generalizing to the case where we pick the rst coin with probability r, we get P(ω) = r ph(ω)(1 − p)n−h(ω) + (1 − r) qh(ω)(1 − q)n−h(ω) Exercises 3.3, page 6 a) We have one random variable C which denotes the coin chosen (1, 2 and 3, with 1 being the fair coin), two random variables F1 and F2 denoting the face that comes up for the rst and second ip, and two random variables X1 and X2 denoting the color of the rst and second ip. There are two stages to the experiment: the selection of a coin to ip coins and the two ips of the coin. Then the possible outcomes are shown in the tree in Figure 1. The probability of each outcome is found by multiplying the probabilities on each branch. Possible outcomes of the colorful coin tossing experiment b) There are nine possible outcomes of the choice of coins in this case, each occurring with probability 19 . Corresponding to each of the nine choices, there are four possible outcomes of the coin tosses (HH, HT, TH, TT). The probability of each outcome can again be calculated by multiply- ing heads or tails probabilities of the appropriate coins in each case. If we don't care whether coin 2 or 3 was chosen, since they are iden- tical, then the nine possible outcomes of choosing two coins reduces to the four outcomes of choosing either the fair coin (1), or a biased coin ( 2 or 3 ) for each ip. Writing out these four cases we have: - 9 probability of choosing two fair coins, and probabilities to get (HH, HT, TH, TT ) of 14 , 14 , 14 , 14 respectively. - −9 probability of choosing a fair coin followed by a biased coin, andprobabilitiestoget(HH,HT,TH,TT)of 12p,12(1−p),12p,12(1−p) , respectively. - 9 probability of choosing a biased coin followed by a fair coin, and probabilitiestoget(HH,HT,TH,TT)of 12p,12p,12(1−p),12(1−p) , respectively. - −9 probability of choosing two biased coins, and probabilities to get (HH,HT,TH,TT) of p2,p(1−p),p(1−p),(1−p)2 , re- spectively. Note that the last three cases for the coins chosen expand into eight dierent cases when we care whether coin 2 or coin 3 is chosen. The outcomes are not the same as in part (a) because now it is possible to have one toss being from the blue-white coin and one toss from a red-blue coin, which was not a possible outcome in part (a). For example, when coins 1 and 2 are chosen, we can get an outcome which is (white, red), which was not possible previously. 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com