6.042/18.] Mathematics for Computer Science March 15, 2005 Srini devadas and Eric Lehman Problem set 6 Solutions Due: Monday, March 28 at 9 PM Problem 1. Sammy the Shark is a financial service provider who offers loans on the fol- lowing terms Sammy loans a client m dollars in the morning. This puts the client m dollars in debt to sammy. Each evening, Sammy first charges a"service fee", which increases the clients debt y f dollars, and then Sammy charges interest, which multiplies the debt by a factor of p. For example, if Sammys interest rate were a modest 5% per day, then p would be1.05 (a)What is the client's debt at the end of the first day Solution. At the end of the first day, the client owes Sammy(m f)p=mp+ fp doll ars (b) What is the clients debt at the end of the second day? Solution((m+ f)p+ fp= mp2+ fp2+ fp (c) Write a formula for the client's debt after d days and find an equivalent clos orm Solution. The clients debt after three days is (((m+ f)p+ fp+f)p=mp'+fp+fp+ fp generalizing from this pattern the client owes k=1 dollars after d days. Applying the formula for a geometric sum gives mp+/./pd+ Problem 2. Find closed-form expressions equal to the following sums. Show your work
� � � 6.042/18.062J Mathematics for Computer Science March 15, 2005 Srini Devadas and Eric Lehman Problem Set 6 Solutions Due: Monday, March 28 at 9 PM Problem 1. Sammy the Shark is a financial service provider who offers loans on the following terms. • Sammy loans a client m dollars in the morning. This puts the client m dollars in debt to Sammy. • Each evening, Sammy first charges a “service fee”, which increases the client’s debt by f dollars, and then Sammy charges interest, which multiplies the debt by a factor of p. For example, if Sammy’s interest rate were a modest 5% per day, then p would be 1.05. (a) What is the client’s debt at the end of the first day? Solution. At the end of the first day, the client owes Sammy (m + f)p = mp + fp dollars. (b) What is the client’s debt at the end of the second day? Solution. ((m + f)p + f)p = mp2 + fp2 + fp (c) Write a formula for the client’s debt after d days and find an equivalent closed form. Solution. The client’s debt after three days is (((m + f)p + f)p + f)p = mp 3 + fp 3 + fp 2 + fp. Generalizing from this pattern, the client owes d mp d + fp k k=1 dollars after d days. Applying the formula for a geometric sum gives: d+1 p − 1 − 1 mp d + f · p − 1 Problem 2. Find closedform expressions equal to the following sums. Show your work
92-72 Solution. Split the expression into two geometric series and then apply the formula for the sum of a geometric series 92-72 11/9 11/7 Solution. Taking the logarithm reduces this product to an easy sum 4+5=3g3(I=34+5) 4i+5 2n(n+1)+5n 5/3 j=1i=0 2j1/3 Solution. This fearsome-looking sum is a paper tiger; we just apply the formula for the sum of a geometric series followed by the formula for the sum of an arithmeti series. n(n+)(n+1)
� � � 2 Problem Set 6 (a) �n 9i − 7i 11i i=0 Solution. Split the expression into two geometric series and then apply the formula for the sum of a geometric series. �n n � �i n � 9i − 7i � 9 � 7 �i = 11i 11 − 11 i=0 i=0 i=0 � 9 �n+1 � 7 �n+1 1 − 11 1 − 11 = 9 1 − 11 − � �n+1 7 1 − 11 � �n+1 11 9 11 7 11 = − + + 2 · 11 4 · 11 4 (b) n 34i+5 i=1 Solution. Taking the logarithm reduces this product to an easy sum. n 3log3( Qn 34i+5) 34i+5 = i=1 i=1 Pn = 3 4i+5 i=1 = 32n(n+1)+5n (c) ��n ∞ � 1 �i j5/3 · 1 − 2j1/3 j=1 i=0 Solution. This fearsomelooking sum is a paper tiger; we just apply the formula for the sum of a geometric series followed by the formula for the sum of an arithmetic series. �� � n 1 n ∞ �i � 1 j5/3 · 1 − 2j1/3 = j5/3 · � 1 � j=1 i=0 j=1 1 − 1 − 2j1/3 n = 2j2 j=1 1 2n(n + 2 )(n + 1) = 3
Problem set 6 Problem 3. There is a bug on the edge of a 1-meter rug. The bug wants to cross to the other side of the rug. It crawls at 1 cm per second. However, at the end of each second,a malicious first-grader named Mildred Anderson stretches the rug by 1 meter. Assume that her action is instantaneous and the rug stretches uniformly. Thus, heres what happens in the first few seconds The bug walks 1 cm in the first second, so 99 cm remain ahead Mildred stretches the rug by 1 meter, which doubles its length. So now there are 2 cm behind the bug and 198 cm ahead The bug walks another 1 cm in the next second, leaving 3 cm behind and 197 cm Then Mildred strikes, stretching the rug from 2 meters to 3 meters. So there are now 33/2)=4.5 cm behind the bug and 197( 3/2)=295. 5 cm ahead The bug walks another 1 cm in the third second, and so on Your job is to determine this poor bugs fate (a) During second i, what fraction of the rug does the bug cross? Solution. During second i, the length of the rug is 100i cm and the bug crosses 1 cm. Therefore, the fraction that the bug crosses is 1/100i (b)Over the first n seconds, what fraction of the rug does the bug cross altogether? Solution. The bug crosses 1/100 of the rug in the first second, 1/200 in the second, 300 in the third, and so forth. Thus, over the first n seconds, the fraction crossed by the bug is This formula is valid only until the bug reaches the far side of the rug (c) Approximately how many seconds does the bug need to cross the entire rug Solution. The bug arrives at the far side when the fraction it has crossed reaches 1. This occurs when n, the number of seconds elapsed, is sufficiently large that Hn/100 1 Now Hn is approximately Inn, so the bug arrives about when ln >1 Inn >100
Problem Set 6 3 Problem 3. There is a bug on the edge of a 1meter rug. The bug wants to cross to the other side of the rug. It crawls at 1 cm per second. However, at the end of each second, a malicious firstgrader named Mildred Anderson stretches the rug by 1 meter. Assume that her action is instantaneous and the rug stretches uniformly. Thus, here’s what happens in the first few seconds: • The bug walks 1 cm in the first second, so 99 cm remain ahead. • Mildred stretches the rug by 1 meter, which doubles its length. So now there are 2 cm behind the bug and 198 cm ahead. • The bug walks another 1 cm in the next second, leaving 3 cm behind and 197 cm ahead. • Then Mildred strikes, stretching the rug from 2 meters to 3 meters. So there are now 3 · (3/2) = 4.5 cm behind the bug and 197 · (3/2) = 295.5 cm ahead. • The bug walks another 1 cm in the third second, and so on. Your job is to determine this poor bug’s fate. (a) During second i, what fraction of the rug does the bug cross? Solution. During second i, the length of the rug is 100i cm and the bug crosses 1 cm. Therefore, the fraction that the bug crosses is 1/100i. (b) Over the first n seconds, what fraction of the rug does the bug cross altogether? Solution. The bug crosses 1/100 of the rug in the first second, 1/200 in the second, 1/300 in the third, and so forth. Thus, over the first n seconds, the fraction crossed by the bug is: �n 1 = Hn/100 100k k=1 (This formula is valid only until the bug reaches the far side of the rug.) (c) Approximately how many seconds does the bug need to cross the entire rug? Solution. The bug arrives at the far side when the fraction it has crossed reaches 1. This occurs when n, the number of seconds elapsed, is sufficiently large that Hn/100 ≥ 1. Now Hn is approximately ln n, so the bug arrives about when: ln n 100 ≥ 1 ln n ≥ 100 100 n ≥ e ≈ 1043 seconds
Problem set 6 that differ by at most 0. 1. Show your work t Problem 4. Use integration to find lower and upper bounds on the following infinite sum 1111 To achieve this accuracy, add up the first few terms explicitly and then use integration to bound all remaining terms Solution. The sum of the first three terms is: 11149 An upper bound on the remaining terms is And a lower bound is x+1)2 Overall, we have 58491 49161 36-36 +-<S<+ These bounds differ by 1/12<0.1. The actual value of the sum is 2/6, though the proof is not easy. Problem 5. A seasoned MIT undergraduate can Complete a problem set in 2 days Write a paper in 2 days Take a 2-day road trip Study for an exam in 1 day. Play foosball for an entire day. An n-day schedule is a sequence of activities that require a total of n days fe here are three possible 7-day schedules 中 pset, foosball Paper, foosball, pset, study road t ad trip, road trip, stud
� 4 Problem Set 6 Problem 4. Use integration to find lower and upper bounds on the following infinite sum that differ by at most 0.1. Show your work. 1 1 1 1 S = + + + + . . . 12 22 32 42 To achieve this accuracy, add up the first few terms explicitly and then use integration to bound all remaining terms. Solution. The sum of the first three terms is: 1 1 1 49 s = + + = 12 22 32 36 An upper bound on the remaining terms is: ∞ 1 1 dx = 3 x2 3 And a lower bound is: � ∞ 1 1 dx = (x + 1)2 3 4 Overall, we have: 58 49 1 49 1 61 + = 36 ≤ 36 + 4 ≤ S ≤ 36 3 36 These bounds differ by 1/12 < 0.1. The actual value of the sum is π2/6, though the proof is not easy. Problem 5. A seasoned MIT undergraduate can: • Complete a problem set in 2 days. • Write a paper in 2 days. • Take a 2day road trip. • Study for an exam in 1 day. • Play foosball for an entire day. An nday schedule is a sequence of activities that require a total of n days. For example, here are three possible 7day schedules: pset, paper, pset, foosball paper, study, foosball, pset, study road trip, road trip, road trip, study
Problem set 6 5 (a) Express the number of possible n-day schedules using a recurrence equation and sufficient base cases Solution S(0)=1, S(1)=2 any schedule for n> 1 days ends with one of 3 possible 2-day activities or one of 2 possible 1-day activities. So S(m)=2S(m-1)+3S(n-2 for n >1 (b) Find a closed-form expression for the number of possible n-day schedules br Solution. The characteristic polynomial for this linear homogeneous recurrence is 2-2.c-3=(r+1(a-3). Hence the solution is of the form S(n)=a(-1)"+b3n Letting n=0, we conclude that a+b= l, and letting n= l, we conclude -a+3b= 2, so b=3/4, a=1/4, and the solution is (-1) 4 Problem 6. Find a closed-form expression for T(n), which is defined by the following recurrence T(0)=0 T(1)=1 T(n)=5T(n-1)-6T(n-2)+6 for all n 22 Solution. The characteristic equation is x2-5x+6=0, which has roots r=2 and 3. Thus, the homogenous solution is T(m)=A.2n+B·3 For a particular solution, let's first guess T(n)=c Our guess was correct; T(n)=3 is a particular solution. Adding this to the homogenous solution gives the general solution T(m)=A.2+B.32+3
Problem Set 6 5 (a) Express the number of possible nday schedules using a recurrence equation and sufficient base cases. Solution. S(0) = 1, S(1) = 2. Any schedule for n > 1 days ends with one of 3 possible 2day activities or one of 2 possible 1day activities. So S(n) = 2S(n − 1) + 3S(n − 2) for n > 1. (b) Find a closedform expression for the number of possible nday schedules by solving the recurrence. Solution. The characteristic polynomial for this linear homogeneous recurrence is 2 x − 2x − 3 = (x + 1)(x − 3). Hence the solution is of the form S(n) = a(−1)n + b3n . Letting n = 0, we conclude that a+b = 1, and letting n = 1, we conclude −a+3b = 2, so b = 3/4, a = 1/4, and the solution is: 3n+1 + (−1)n S(n) = . 4 Problem 6. Find a closedform expression for T(n), which is defined by the following recurrence: T(0) = 0 T(1) = 1 T(n) = 5T(n − 1) − 6T(n − 2) + 6 for all n ≥ 2 2 Solution. The characteristic equation is x − 5x + 6 = 0, which has roots x = 2 and x = 3. Thus, the homogenous solution is: 2n 3n T(n) = A · + B · For a particular solution, let’s first guess T(n) = c: c = 5c − 6c + 6 ⇒ c = 3 Our guess was correct; T(n) = 3 is a particular solution. Adding this to the homogenous solution gives the general solution: T(n) = 2n 3n A · + B · + 3
Problem set 6 Substituting n=0 and n= l gives 0=A+B+3 1=2A+3B+3 Solving this system gives A=-7 and B=4. Therefore T(m)=-7·2+4.32+3 Problem 7. Determine which of these choices e(n), 0(n2logn), e(n2), 0(1), 0(2 ) 0(2n Inn), none of these describes each functions asymptotic behavior. Proofs are not required, but briefly explain your answers +Inn+(Inn) Solution. Both n> Inn and n>(In n)2 hold for all sufficiently large n. Thus, for all sufficiently large n n<n+Inn+(Inn)-<n+n+n So n+Inn+(Inn)2=e(n) (b) +2m-3 Solution. Observe that +2m-3 lim his means, that for all sufficiently large n, the fraction lies, for example, between, 0.99 and 1.01 and is therefore e(1) Solution. Geometric sums are dominated by their largest term, which is 22n+ 2 4". This is e(4n), which does not appear in the list provided (d) In(n Solution. By Stirlings formula
� � � 6 Problem Set 6 Substituting n = 0 and n = 1 gives: 0 = A + B + 3 1 = 2A + 3B + 3 Solving this system gives A = −7 and B = 4. Therefore: T(n) = −7 2n + 4 3n · · + 3 Problem 7. Determine which of these choices Θ(n), Θ(n 2 log n), Θ(n 2 ), Θ(1), Θ(2n), Θ(2n ln n), none of these describes each function’s asymptotic behavior. Proofs are not required, but briefly explain your answers. (a) n + ln n + (ln n) 2 Solution. Both n > ln n and n > (ln n)2 hold for all sufficiently large n. Thus, for all sufficiently large n: n < n + ln n + (ln n) 2 < n + n + n So n + ln n + (ln n)2 = Θ(n). (b) n2 + 2n − 3 n2 − 7 Solution. Observe that: n2 + 2n − 3 lim = 1 n→∞ n − 7 2 This means, that for all sufficiently large n, the fraction lies, for example, between, 0.99 and 1.01 and is therefore Θ(1). (c) n 22i+1 i=0 Solution. Geometric sums are dominated by their largest term, which is 22n+1 = 2 4n. This is Θ(4n · ), which does not appear in the list provided. (d) ln(n 2 !) Solution. By Stirling’s formula: 2 2 n n 2 2 ! ∼ √ 2πn n e
Problem set 6 Taking logarithms gives In(n2!)In(v2rn' In(V2Tn2)+In The first term is tiny compared to the second which we can rewrite as: In =n21n e(nIn n Solution. The expression in parentheses is always at least 1/2 and at most 1. Thus ze have the bounds Since the first expression and the last are both e (n), so is the one in the middle Problem 8. A triangular number is an integer n of the form n=1+2+3+...+k k(k+1) where k is a positive inte (a)Describe a solution to the four-peg Towers of Hanoi puzzle with k(k+1)/2 disks that requires Tk moves, where Solution Move all but the k largest disks to another peg recursively. This requires T(k Move the k largest disks to another peg using the three-peg strategy. This re- 2k-1 Now move all the other disks on top of the k largest disks recursively. This requires T(k-1)moves
� � � � � � � � Problem Set 6 7 Taking logarithms gives: 2 2 2 n ln(n !) ∼ ln(√ 2πn2 n ) e 2 2 n = ln(√ 2πn2) + ln n e The first term is tiny compared to the second, which we can rewrite as: 2 2 n 2 n ln = n 2 ln n = Θ(n 2 ln n) e e (e) �n � �1 k 1 − 2k k=1 Solution. The expression in parentheses is always at least 1/2 and at most 1. Thus, we have the bounds: n �n � � n 1 � 1 � k ≤ k k 2 1 − 2k ≤ k=1 k=1 k=1 Since the first expression and the last are both Θ(n2), so is the one in the middle. Problem 8. A triangular number is an integer n of the form k(k + 1) n = 1 + 2 + 3 + . . . + k = 2 where k is a positive integer. (a) Describe a solution to the fourpeg Towers of Hanoi puzzle with k(k + 1)/2 disks that requires Tk moves, where: T1 = 1 Tk = 2Tk−1 + 2k − 1 Solution. • Move all but the k largest disks to another peg recursively. This requires T(k − 1) moves. • Move the k largest disks to another peg using the threepeg strategy. This requires 2k − 1 moves. • Now move all the other disks on top of the k largest disks recursively. This requires T(k − 1) moves
Problem set 6 Thus, with this strategy, the total number of moves required to move a stack of k(k+ 1)/2 disks is T(k)=2T(k-1)+2-1 (b)Find a closed form expression equal to Tk Solution. This is an inhomogenous linear equation. Let's begin by trying to find a particular solution. There is both an exponential term(2 )and a constant term,so we might guess something of the form a2+c a2k+c=2(a2k-1+c)+2-1 (a+1)2k+2c-1 0 Evidently, the constant term is c=l, but the exponential part is more complicated Our recipe says we should next try a particular solution of the form a2*+bk2*+ 24+bk2+1=2(a2-1+b(k-1)2k-1+1)+ a-b+1)2+bk2-1 Equating the coefficients of the 2 terms gives a =a-b+l, which implies b=1 Thus, a2*+k2+l is a particular solution for all a. As long as we have this degree of freedom, we might as well choose a so this solution is consistent with the boundary condition T1= l and be done Therefore the solution to the recurrence is Tk 1)2+1 (c) Approximately how many moves are required to solve the four-peg, n-disk Tow- ers of Hanoi puzzle as a function of n? Assume n is a triangular number. (For style points, make correct use of asymptotic notation. Solution. We have k=i(v8n+1-1)=v2n +O(1). So the number of moves required is(√i2
8 Problem Set 6 Thus, with this strategy, the total number of moves required to move a stack of k k(k + 1)/2 disks is T(k) = 2T(k − 1) + 2 − 1. (b) Find a closed form expression equal to Tk. Solution. This is an inhomogenous linear equation. Let’s begin by trying to find a particular solution. There is both an exponential term (2k) and a constant term, so we might guess something of the form a2k + c: k a2k + c = 2(a2k−1 + c) + 2 − 1 = (a + 1)2k + 2c − 1 ⇒ 0 = 2k + (c − 1) Evidently, the constant term is c = 1, but the exponential part is more complicated. Our recipe says we should next try a particular solution of the form a2k + bk2k + 1: k k a2k + bk2 + 1 = 2(a2k−1 + b(k − 1)2k−1 + 1) + 2 − 1 k = (a − b + 1)2k + bk2 − 1 Equating the coefficients of the 2k terms gives a = a − b + 1, which implies b = 1. Thus, a2k +k2k +1 is a particular solution for all a. As long as we have this degree of freedom, we might as well choose a so this solution is consistent with the boundary condition T1 = 1 and be done: a21 + 1 · 21 + 1 = 1 ⇒ a = −1 Therefore, the solution to the recurrence is Tk = (k − 1)2k + 1. (c) Approximately how many moves are required to solve the fourpeg, ndisk Towers of Hanoi puzzle as a function of n? Assume n is a triangular number. (For style points, make correct use of asymptotic notation.) 1 Solution. We have k = 2 ( √8n + 1 − 1) = √2n + O(1). So the number of moves required is Θ(√n2 √2n)