CMPS 211 Homework 4 with Solution, Spring 2016

American University of Beirut Department of Computer Science CMPS 211 - Spring 2015-16 Assignment 4 - Solution Key The following exercises are to be completed by Wednesday 23rd of March 2016. Late submissions will not be accepted. You are expected to submit to moodle and another printed copy during class. Only typed submissions will be accepted from now on, and those who submit in LATEX will get extra credits. Associated Readings: Sections 3.1, 5.1 and 5.2 of your text book Exercise 1 (10 Points) Can you guess the next number? 1 3, 1 15, 1 35, 1 63, ... a) Find a formula for the nth element in the list (Hint: Check the divisors of the denominator). Solution: Notice that the denominator of the first element is equal to 3 = 3 × 1. The denominator of the second element is 15 = 5 × 3. The denominator of the second element is 35 = 7 × 5. The denominator of the second element is 63 = 9 × 7. So it seems like the nth denominator is the product of the nth and (n+1)th odd number. In other words an = 1 (2n − 1)(2n + 1) n ≥ 1 b) Find a formula for the sum of the first n elements: Sn = n � i=1 ai = a1 + a2 + a3 + ... + an Solution: 1 Using the formula for the nth element from part (a) we have: Sn = n � i=1 ai = n � i=1 1 (2i − 1)(2i + 1) Using few values for n we get: S1 = 1 3 S2 = 1 3 + 1 15 = 2 5 S3 = 1 3 + 1 15 + 1 35 = 3 7 S4 = 1 3 + 1 15 + 1 35 + 1 63 = 4 9 It seems as if the partial sum Sn has numerator n, and its denominator is the (n+1)th odd number. We can conjuncture that: Sn = n 2n + 1 c) Prove the formula you conjectured in part (b) using Induction. Solution: We want to prove (By induction) that n � i=1 1 (2i − 1)(2i + 1) = n 2n + 1 Base case (n = 1): n � i=1 1 (2i − 1)(2i + 1) = n 2n + 1 = 1 3 Inductive Step: Assume the result for n n � i=1 1 (2i − 1)(2i + 1) = n 2n + 1 2 We want to show that it holds for n + 1. n+1 � i=1 1 (2i − 1)(2i + 1) = ( n � i=1 1 (2i − 1)(2i + 1)) + 1 (2(n + 1) − 1)(2(n + 1) + 1) = n 2n + 1 + 1 (2n + 2 − 1)(2n + 2 + 1) by inductive hypothesis = n 2n + 1 + 1 (2n + 1)(2n + 3) = n(2n + 3) + 1 (2n + 1)(2n + 3) = 2n2 + 3n + 1 (2n + 1)(2n + 3) = (2n + 1)(n + 1) (2n + 1)(2n + 3) = (n + 1) (2n + 3) = Sn+1 which completes the proof Note: You could have broken up the fractions more, and then recollapsed it and reached same result. Exercise 2 (10 Points) a) Show that 4 divides n4 − n2 using mathematical induction. Solution: Base Case (n = 0): n4 − n2 = 0 divides 4. Inductive Step: Assume n4 − n2 divides 4, show that (n + 1)4 − (n + 1)2 divides 4. (n + 1)2 = n2 + 2n + 1 (n + 1)4 = (n + 1)2(n + 1)2 = (n2 + 2n + 1)(n2 + 2n + 1) = n4 + 4n3 + 6n2 + 4n + 1 (n+1)4−(n+1)2 = n4+4n3+6n2+4n+1−(n2+2n+1) = n4−n2+4n3+6n2+2n We know that n4 − n2 (by inductive hypothesis), and 4n3 are both divisible by 4, so it remains to show that 6n2 + 2n = 2n(3n + 1) is divisible by 4. Now we complete the proof by considering the following cases: 3 (i) n = 4k, clearly 2n(3n + 1) is divisible by 4 then. (ii) n = 4k + 1, then 2n(3n + 1) = 2 · (4k + 1)(3(4k + 1) + 1) = 2 · (4k + 1)(12k + 4) = 2 · 4 · (4k + 1)(3k + 1) which is divisible by 4. (iii) n = 4k + 2, then 2n(3n + 1) = 2 · (4k + 2)(3(4k + 2) + 1) = 2 · 2 · (2k + 1) · (3(4k + 2) + 1) = 4 · (2k + 1)(3(4k + 2) + 1), which is divisible by 4. (iv) n = 4k + 3, then 2n(3n + 1) = 2 · (4k + 3)(3(4k + 3) + 1) = (8k + 6)(12k + 10) = 2 · 2(4k + 3)(6k + 5) = 4(4k + 3)(6k + 5), which is divisible by 4. Therefore, n4 − n2 divides 4. b) Show that 3 divides n4 − n2 using mathematical induction. Base Case (n = 1): n4 − n2 = 0 divides 3. Inductive Step: Assume n4 − n2 divides 3, show that (n + 1)4 − (n + 1)2 divides 4. (n + 1)2 = n2 + 2n + 1 (n + 1)4 = (n + 1)2(n + 1)2 = (n2 + 2n + 1)(n2 + 2n + 1) = n4 + 4n3 + 6n2 + 4n + 1 (n+1)4−(n+1)2 = n4+4n3+6n2+4n+1−(n2+2n+1) = n4−n2+4n3+6n2+2n We know that n4 − n2 (by inductive hypothesis), and 6n2 are both divisible by 3, so it remains to show that 4n3 + 2n = 2n(2n2 + 1) is divisible by 3. Now we complete the proof by considering the following cases: (i) n = 3k, clearly 2n(2n2 + 1) is divisible by 3 then. (ii) n = 3k + 1, therefore 2n(2n2 + 1) = 2(3k + 1)(2(3k + 1)2 + 1) = (6k + 2)(18k2 + 12k + 3) = 3(6k + 2)(6k2 + 2k + 1), which is divisible by 3. (iii) n = 3k + 2, then 2n(2n2 + 1) = 2(3k + 2)(2(3k + 2)2 + 1) = (6k + 4)(18k2 + 24k + 9) = 3(6k + 4)(6k2 + 8k + 3), which is divisible by 3. Therefore, n4 − n2 divides 3. 4 c) Conclude that 12 divides n4 − n2. Solution: Since n4 − n2 divides 4 and 3, it can be written as 4m and 3k for naturals m, k. Since 4 and 3 are relatively prime then 4m = 3k = 4.3z = 12z for some natural z. Since n4 − n2 = 12z then clearly n4 − n2 divides 12. Exercise 3 (10 Points) Consider the proposition 2n > n3. a) Find an integer N such that the proposition is true whenever n is greater than N. Solution: We need to look for n such that the proposition is true, by trying different values of n, we can find that when n = 10: 210 = 1024 > 1000 = 103 Therefore N = 10 − 1 = 9 b) Prove your result for all n > N using mathematical induction. Solution: Base case (n = N + 1 = 10) Already shown. Inductive Step: Assume 2n > n3 for n > 9, prove it for n + 1. (n + 1)3 = (n + 1)(n2 + 2n + 1) = n3 + 3n2 + 3n + 1 2n+1 = 2n × 2 > 2 × n3 (Using Inductive Hypothesis) = n3 + n3 > n3 + 9n2 (since n ¿ 9) = n3 + 3n2 + 6n2 > n3 + 3n2 + 6 · 9n (since n ¿ 9) = n3 + 3n2 + 54n = n3 + 3n2 + 3n + 51n > n3 + 3n2 + 3n + 1 (since 51n ¿ 1 for n ¿ 9) = (n + 1)3 Therefore 2n+1 > (n + 1)3 for all n > N = 9. 5 Exercise 4 (10 Points) Assume you can only use 7-cent and 11-cent stamps. a) Determine which amounts of postage can be formed by the given stamps. Solution: We can only form amounts of the form n = 7a + 11b for a, b ≥ 0. So we can form 0, 7, 11, 14, 18, 21, 22, 25, 28, 29, 32, 33, 35, 36, 39, 40, 42, 43, 44, 46, 47, 49, 50, 51, 53, 54, 55, 56, 57, 58, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 71, ... We can form any amount greater than or equal to 60. b) Prove your answer to (a) using the principle of mathematical induction. Be sure to state explicitly your inductive hypothesis in the inductive step. Solution: Base case: We can form 60 as shown in part a. Inductive step: We assume that we can form some amount n ≥ 60, we want to show that we can form amount n + 1. Since we can form amount n then there exist some naturals a, b such that n = 7a + 11b. We have n + 1 = 7a + 11b + 1 we want to show that n + 1 = 7a‘ + 11b‘ for some a‘, b‘ naturals. We want to find combinations of a and b such that |7a − 11b| = 1, Notice that 7 ∗ 3 = 21 and 11 ∗ 2 = 22, therefore 7(a − 3) + 11(b + 2) = 7a − 7 ∗ 3 + 11b + 22 = 7a + 11b + 1 = n + 1. So if n = 7a + 11b where a ≥ 3 we can use the derivation above to form n + 1. However it is possible that a < 3. Notice that 7 ∗ 8 = 56, while 11 ∗ 5 = 55. Therefore, if a < 3 we can try 7(a + 8) + 11(b − 5) = 7a + 56 + 11b − 55 = n + 1. So if n = 7a + 11b and either a ≥ 3 or b ≥ 5 we can form n + 1. 6 Take the remaining case where a < 3 and b < 5, the biggest amount we can form from such a combination is 7∗2+11∗4 = 14+44 = 58, However we assumed that n ≥ 60. Therefore it is never the case that a < 3 and b < 5, and we can always form n + 1 for n ≥ 60. c) Prove your answer to (a) using strong induction. How does the inductive hypoth- esis in this proof differ from that in the inductive hypothesis for a proof using mathematical induction? Solution: Base case: We can form amounts 60, 61, 62, 63, 64, 65, 66 as shown in part a. Inductive Step: We assume that we can form amounts from 60 to n − 1 inclusive, in other words ∀k : 60 ≥ k ≤ n − 1, ∃a, b ∈ N : k = 7a + 11b. We need to show that we can form n + 1. Take n + 1 − 7 since n + 1 − 7 < n then by the inductive hypothesis we have n + 1 − 7 = 7a + 11b for some a, b ∈ N . Consider a‘ = a + 1, we have 7a‘ + 11b = 7a + 7 + 11b = (n + 1) − 7 + 7 = n + 1 Therefore we can form n + 1. Exercise 5 (30 Points) Given a list of n distinct integers, we wish to design and analyse an algorithm for each of the following: 1. To produce the product of the two elements with value closest to the average of the list, such that one of them is greater than the average and the other is lower than the average. 2. To produces all pairs in the list with sum equal to a given value k. This methods take the list, and an integer k as input arguments. So for example, if the sum of the pair a1 and a4 is equal k, then the algorithm should print a1, a4, and all other pairs with the same property 3. To locate the position of the element with largest difference with the element before it. 7 For each algorithm above, do the following: a) Give a complete design using pseudo-code. b) Calculate the number of operations required by each algorithm. c) Calculate the amount of space required by each algorithm. d) State a loop invariant (don’t prove it). First Algorithm Procedure avg prod(integer c1, ..., integer cn) avg := 0 for i := 1 to n avg := avg + ci avg := avg / n a := 0 b := +∞ for i := 1 to n if ci < avg and ci > a then a := ci else if ci > avg and ci < b then b := ci return a × b Number of operations 1. the first loop (to calculate average) requires 1 assignment and 1 addition in each iteration. It has n iterations: so the number of operations associated with this step is: n � i=1 c = cn → n as n → ∞ 2. the second loop has n iterations, in each iteration we can have at most 4 comparisons and 1 assignment. The number of operations associated with this step is: n � i=1 c′ = c′n → n as n → ∞ 3. we have 1 division, 1 multiplication, and 3 assignment outside of both loops. In total, the maximum number of operations tends to n as n → is ∞. Space: The algorithm uses n slots of memory for the input and a constant amount of space for intermediary and final output. In total, the space is dominated by n as n → ∞. Invariant: P(i) = “After the i’th iteration, a is the closest value to the average that is smaller than it inside c[0...i] and b is the closest value to the average that is greater than it inside c[0...i]. 8 Second Algorithm Procedure kpair(integer c1, ..., integer cn, integer k) for i := 1 to n count = 0 for j := i+1 to n if ci + cj equals k count = count + 1 A[count] = (ci, cj) Number of operations: Each iteration from the inner loop contains a comparison and a write in the worst case. For every iteration of the outer loop with value i, the inner loop has n − i iterations. The outer loop has n iterations. T(n) = �n i=1 �n j=i+1 c = c ��n i=1 �n j=i+1 1 � = c (�n i=1(n − i)) = c (�n i=1 n − �n i=1 i) = c � n2 − n(n+1) 2 � → n2 as n → ∞ rcl Space: The algorithm requires about n records for input and at most n records for output and so the space complexity is dominated by n as n goes to ∞. Invariant: P(i) = “After the i’th iteration, count represents the number of all pairs (cp, cq) such that cp + cq = k and p ≤ i, q ≤ j and all elements in A[1, . . . , count] record those pairs. Third Algorithm Procedure largestDiff(integer c1, ..., integer cn) max := -∞ i max := 0 for i := 2 to n if ci − ci−1 > max max := |ci − ci−1| i max := i return i max Number of operations: Each iteration incurs at most 2 subtractions, 2 assignments, and 1 comparison. There are n − 1 iterations in total. So T(n) → n as n → ∞. Space: The algorithm requires n records for storing the input and three variables for tracing the output (constant amount of memory independent of n). Hence, the space complexity is domianted by n as n → ∞. 9 Invariant: P(i) = “After the i’th iteration, max = max{|ci − ci−1|} and i max is such that cimax − cimax−1 = max{|ci − ci−1|}. Exercise 6 (30 Points) Give an estimate as n → ∞ for the run-times of the following segments of algorithms. Procedure alg1(integer n, integer m) (3 points) s := 0 while n > 0 s := s + m return s Solution: The loop does not terminate, the terminating condition for the loop is when n ≤ 0, However n is not changed during or before the loop. We have two cases: Either n is given as a non positive number (in which case no loops will be excuted and run time is constant), or n is given positive, in which case the loop goes on forever, and the runtime is +∞. Procedure alg2(integer n) (3 points) t := 0 for i := 1 to n for j := i + 1 to n for k := j + 1 to n t := i + j + k Solution: Outermost loop has n iterations, for each of which the loop within it has n - i iterations, for each of which the inner most loop has n - j iterations. 10 T(n) = n � i=1 n � j=i+1 n � k=j+1 c = c n � i=1 n � j=i+1 (n − j) = c   n � i=1 n � j=i+1 n − n � i=1 n � j=i+1 j   = c   n � i=1 n n � j=i+1 1 − n � i=1 n � j=i+1 j   = c � n � i=1 n(n − i) − n � i=1 (n(n + 1) 2 − i(i + 1) 2 ) � = c � n3 − n2(n + 1) 2 − n2(n + 1) 2 + n � i=1 i(i + 1) 2 � = c � −n2 + 1 2 � n � i=1 i2 + n � i=1 i �� = c � −n2 + 1 2 �n(n + 1)(2n + 1) 6 + n(n + 1) 2 �� This goes to n3 as n goes to ∞ Procedure alg3(integer n) (4 points) i := 1 t := 0 while i ≤ n t := t + i i := 10 ∗ i Solution: The while loop begins with i = 1, at every iteration i gets multiplied by 10 and n remains unchanged. i takes the values of 1, 10, 100, 1000, ... in other words, for n < 10 the loop needs one iteration to terminate, for 10 < n < 100 it needs 2, for 100 < n < 1000 it needs 3, for 10k−1 < n < 10k it needs k iterations. Taking the log of both sides, we realize that for n the loop will terminate within log10(n) iter- ations. The runtime tends to log10(n) as n → ∞. Procedure alg4(integer n) (5 points) k := 1 for i := 1 to n t := i while t > 0 k := k + t t := t/2 11 Solution: Outermost loop has n iterations, The inner loop depends on t = i. For t = 2 the loop is executed twice, for t = 4 the loop is executed 3 times, for t = 8 the loop is executed 4 times, for t = 2k the loop is executed k, therefore the inner loop executes log2(i) + 1 times for each i. n � i=1 log2(i)+1 � t=1 c < n � i=1 log2(n)+1 � t=1 c = n(log2(n) + 1) This tends to n log(n) as n → ∞. Exercise 7 (15 Points) For each of the following algorithms, state a loop invariant and then prove it. Algorithm 1: This procedure compute xn Procedure power(integer x, integer n) power := 1 for i := 1 to n power := power × x return power; Solution: The loop invariant: P(i) = “At the start of the i’th iteration we have power = xi−1”. Initialization: Show P(1): at the start of the first iteration, we have power = 1 which is equal to xi−1 = x0. Maintenance: Assume that at the start of iteration i we have power = xi−1. During the i’th iteration, the algorithm updates power by a multiplication with x and so we now have power = xi by the end of the i’th iteration (which is by the beginning of the i + 1’st iteration. We thus maintain P(i + 1). Termination: Since the for loop varies over the range [1, n]. Upon Termination we have i = n + 1 (Termination Condition), and power = xi−1 (Invariant). At this stage of the code, we have i = n + 1 ∧ power = xi−1 → power = xn+1−1 → power = xn 12 Algorithm 2: This procedure compute |n| Procedure abs(integer n) int absolute := 0 if n < 0 absolute := −n else absolute := n return absolute Solution: The invariants and assertions are stated as in-line comments. Idea: There is one and only one iteration. All we have to do is state the “meaning” of every instruction mathematically. More or less, this is an example of a loop invariant that only has P(1) instance. Procedure abs(integer n) int absolute := 0 if n < 0 {{ n is negative }} absolute := −n {{ n is negative and absolute = −n }} {{ absolute = |n| }} else {{ n is non-negative }} absolute := n {{ n is non-negative and absolute = n }} {{ absolute = |n| }} {{ absolute = |n| }} return absolute The proof is a straightforward justification of the way the absolute value function is defined. 13 Algorithm 3: This procedure computes quotients and remainders for the division of p by d. Procedure division(integer p, integer d) q := 0 {q is the quotient} r := p {r is the remainder} while r ≥ d r := r − d q := q + 1 return (q, r) Solution: The loop invariant: P(i) = “At the beginning of the i’th iteration p = ri + qi ∗ d”, where ri and qi designate the values of r and q respectively, at the beginning of the i’th iteration. Initialization: before starting the loop, we have q1 = 0 and r1 = p. Therefore p = r1 + q1 ∗ d. Maintenance: Assume P(i) = “At the beginning of the i’th iteration i, we have p = ri+qi∗d”. In the duration of the i’th iteration, we are updating the estimates on r and q as follows: re+1 = ri − d → ri = ri+1 + d qi+1 = qi + 1 → qi+1 = qi − 1 By substituting the values in the induction hypothesis, we get: p = (ri+1 + d) + (qi+1 − 1) ∗ d p = ri+1 + d + qi+1 ∗ d − d p = ri+1 + qi+1 ∗ d Therefore p = ri+1 + qi+1 ∗ d holds at the end of the i’th iteration (which is the beginning of the i + 1’st iteration – hence P(i + 1) is established. Termination: The loop terminates when r < d, since d is a finite number and at every iteration r is decremented by a constant amount, therefore r will eventually become less than d allowing termination. That is when r is a valid remainder and q is the final quotient. Extra Practice (Not To Be Submitted) From the textbook ”Discrete Mathematics and Its applications 7th Edition” Sec. 3.1 (exercises 1 → 36, 38 → 43) Sec. 5.1 (exercises3 → 7, 9, 31 → 35) Sec. 5.2 (exercises 3, 4, 8) 14