Math 2320 Assignment 1 Solution

Math 2320 Assignment 1 Solution 1. Specify the steps of an algorithm that locates an element in a list of increasing integers by successively splitting the list into four sublists of equal (or as close to equal as possible) size, and restricting the search to the appropriate piece. (Hint: see binary search algorithm.) Solution:

procedure Search(x: integer; a1 , a2 , . . . , an : integers) i := 1 j := n while (i < j − 2) (the list has at least four numbers) begin (l is the last position of the first part, l = i + b j−i l := b j+3i 4 c 4 c) j+i (m is the last position of the second part, m = i + b 2(j−i) c) m := b 2 c 4 3(j−i) 3j+i u := b 4 c (u is the last position of the third part, u = i + b 4 c) if x > au then i = u + 1 (x is in the last part if x is on the list) else if x > am then (x is in the third part if x is on the list) begin i := m + 1 j := u end else if x > al then (x is in the second part if x is on the list) begin i := l + 1 j := m end else j := l (x is in the first part if x is on the list) end (Below checks if x is in the remaining list which has fewer than four elements.) k := b i+j (k is the position of the ”middle” number in the remaining list) 2 c if ai = x then location := i else if ak = x then location := k else if aj = x then location := j else location := 0 {location is the location of x or is 0 if x is not in the list.}

2. (a) Describe an algorithm that locates the last occurrence of the smallest element in a finite list of integers, where the integers in the list are not necessarily distinct. Solution:

1

procedure last smallest(a1 , a2 , . . . , an : integers) min := a1 location := 1 for i := 2 to n begin if ai ≤ min then begin min := ai location := i end end {location is the location of the last occurrence of the smallest element in the list.}

(b) Analyze the complexity of the algorithm you devised in Part (a), measured in terms of the number of comparisons. Solution: For each i = 2, . . . , n, the for loop checks if i is larger than n and the if statement performs one comparison. When i = n + 1, the for statement sees that i > n and exits the loop. Hence if the input is a list of n numbers, the algorithm uses 2(n−1)+1 = 2n−1 comparisons. We say that this algorithm has complexity O(n). 3. The Horner’s method is an algorithm that evaluates polynomials. The following pseudocode shows how to use this method to find the value of an xn + an−1 xn−1 + . . . + a1 x + a0 at x = c. procedure Horner(c, a0 , a1 , a2 , . . . , an : real numbers) y := an for i := 1 to n y := y × c + an−i end {y = an cn + an−1 cn−1 + . . . + a1 c + a0 } (a) Evaluate x2 + 5x + 3 at x = 2 by working through each step of the algorithm. Solution: The inputs are c = 2, a0 = 3, a1 = 5 and a2 = 1. Note that n = 2. At the first step, we set y := a2 = 1. For i = 1, we have y := y × c + a2−1 = 1 × 2 + a1 = 1 × 2 + 5 = 7. For i = 2, we have y := y × c + a2−2 = 7 × 2 + a0 = 7 × 2 + 3 = 17. 2

We finish the for loop, and the output is 17 which is the value of the quadratic polynomial at x = 2. (b) Exactly how many multiplications and additions are used by this algorithm to evaluate a polynomial of degree n at x = c? (Do not count additions used to increment the loop variable.) Solution: In each iteration of the for loop, we computed y := y × c + an−i which consists of exactly one multiplication and one addition. Since there are n iterations in the for loop, so n multiplications and n additions are performed in this algorithm. 4. How many positive integers between 1000 and 9999 inclusive (a) are even? Solution: First note that there are (9999 − 1000 + 1) = 9000 numbers between 1000 and 9999 inclusive. Exactly half of the numbers be= 4500 even tween 1000 and 9999 are even, so there are 9000 2 numbers. (b) have distinct digits? Solution: The left-most digit is one of 1, 2, . . . , 9, so there are 9 possible outcomes. The second left-most digit is one of 0, 1, . . . , 9 except for the one chosen for the left-most digit, so there are 9 possible outcomes. The third left-most digit is one of 0, 1, . . . , 9 except for the one chosen for the two left-most digits, so there are 8 possible outcomes. The fourth left-most digit is one of 0, 1, . . . , 9 except for the one chosen for the three left-most digits, so there are 7 possible outcomes. By the product rule, there are 9 × 9 × 8 × 7 integers between 1000 and 9999 that have distinct digits. (c) are not divisible by 5? Solution: We observe that 200 × 5 = 1000 and 1999 × 5 = 9995 are the 3

smallest and the largest multiple of 5, respectively, between 1000 and 9999 inclusive. Hence there are 1999 − 200 + 1 = 1800 multiples of 5 between 1000 and 9999 inclusive. We conclude that there are 9000 − 1800 = 7200 numbers between 1000 and 9999 inclusive that are not divisible by 5. (d) are divisible by 5 and 7? Solution: A number is divisible by 5 and 7 if and only if it is divisible by 35. We observe that 29 × 35 = 1015 and 285 × 35 = 9975 are the smallest and the largest multiple of 35, respectively, between 1000 and 9999 inclusive. Hence there are 285 − 29 + 1 = 257 multiples of 35 between 1000 and 9999 inclusive. (e) are divisible by 5 or 7? Solution: From our solution of Part (c), there are 1800 numbers between 1000 and 9999 inclusive that are divisible by 5. We observe that 143×7 = 1001 and 1428×7 = 9996 are the smallest and the largest multiple of 7, respectively, between 1000 and 9999 inclusive. Hence there are 1428 − 143 + 1 = 1286 multiples of 7 between 1000 and 9999 inclusive. From the previous part, there are 257 numbers between 1000 and 9999 inclusive that are divisible by both 5 and 7. By the principle of inclusion-exclusion, there are 1286 + 1800 − 257 = 2829 numbers between 1000 and 9999 inclusive that are divisible by 5 or 7. (f) are not divisible by either 5 or 7? Solution: From the previous part, there are 9000 − 2829 = 6171 numbers between 1000 and 9999 inclusive that are not divisible by either 5 or 7. (g) are divisible by 5 but not by 7? Solution: Between 1000 and 9999 inclusive, there are 1800 numbers divisible by 5. Among these 1800 numbers, 257 of them are also divisible by 7. There are 1800 − 257 = 1543 numbers between 1000 and 9999 inclusive that are divisible by 5 but not by 7. 5. How many strings of four decimal digits 4

(a) do not contain the same digit twice? Solution: The left-most digit is one of 0, 1, . . . , 9, so there are 10 possible outcomes. The second left-most digit is one of 0, 1, . . . , 9 except for the one chosen for the left-most digit, so there are 9 possible outcomes. The third left-most digit is one of 0, 1, . . . , 9 except for the one chosen for the two left-most digits, so there are 8 possible outcomes. The fourth left-most digit is one of 0, 1, . . . , 9 except for the one chosen for the three left-most digits, so there are 7 possible outcomes. By the product rule, there are 10×9×8×7 strings of four decimal digits not containing the same digit twice. (b) end with an even digit? Solution: Each of the three left-most digit is one of 0, 1, . . . , 9, so there are 10 possible outcomes. The right-most digit is one of 0, 2, 4, 6, 8, so there are 5 possible outcomes. By the product rule, there are 103 × 5 strings of four decimal digits ending with an even digit. (c) have exactly three digits that are 9’s? Solution: Let A be the set of strings of four decimal digits having exaclty three digits that are 9’s. For i = 1, . . . , 4, let Ai be the set of strings of four decimal digits whose ith digit is not 9 and all the other three digits are 9’s. Then A1 , A2 , A3 and A4 are pairwise disjoint and A = A 1 ∪ A2 ∪ A3 ∪ A4 . By the sum rule, we have |A| = |A1 | + |A2 | + |A3 | + |A4 |. For |Ai |, the ith digit is one of 0, 1, . . . , 8, so there are 9 possible outcomes. Since each of the other three digits is 9, A i contains exactly 9 strings. By the sum rule, |A| = 9 + 9 + 9 + 9 = 36. 5

(d) have at least one digit that is 9? Solution: We first count the number of strings of four decimal digits is 10 4 since each digit is one of 0, 1, . . . , 9. Now the number of strings of four decimal digits containing no 9’s is 94 because each digit is one of 0, 1, . . . , 8. The number of strings of four decimal digits having at least one digit that is 9 is 104 − 94 = 3439. (e) have one digit that is 9 and do not contain the same digit twice? Solution: Let A be the set of strings of four decimal digits having one digit that is 9 and not containing the same digit twice. For i = 1, . . . , 4, let Ai be the set of strings of four decimal digits whose ith digit is 9. Then A1 , A2 , A3 and A4 are pairwise disjoint and A = A 1 ∪ A2 ∪ A3 ∪ A4 . By the sum rule, we have |A| = |A1 | + |A2 | + |A3 | + |A4 |. For |A1 |, the first digit is 9. The second digit one of 0, 1, . . . , 8, so there are 9 possible outcomes. The third digit is one of 0, 1, . . . , 8 except for the one chosen for the second digit, so there are 8 possible outcomes. The last digit is one of 0, 1, . . . , 8 except for the ones chosen for the second and the third digits, so there are 7 possible outcomes. By the product rule, A 1 contains exactly 1 × 9 × 8 × 7 strings. Similarly, |A2 | = |A3 | = |A4 | = 1 × 9 × 8 × 7. By the sum rule, |A| = 4 × 1 × 9 × 8 × 7 = 2016. 6. (a) How many bit strings of length seven either begin with two 0’s or end with three 1’s? Solution: Let A be the set of bit strings of length seven beginning with two 0’s. Let B be the set of bit strings of length seven ending with three 1’s. For the strings in A, the first two digits are 0’s and each of the last five digits is either 0 or 1. Thus |A| = 1×1×2×2×2×2×2 = 32.

6

For the strings in B, the last three digits are 1’s and each of the first four digits is either 0 or 1. Thus |B| = 2×2×2×2×1×1×1 = 16. The strings in A ∩ B have 0’s in the first two digits and 1’s in the last three digits. The third and the fourth digits of these strings is either 0 or 1, so |A ∩ B| = 1 × 1 × 2 × 2 × 1 × 1 × 1 = 4. By the principle of inclusion-exclusion, there are |A| + |B| − |A ∩ B| = 32 + 16 − 4 = 44 bit strings of length seven either begin with two 0’s or end with three 1’s. (b) How many bit strings of length 10 contain either five consecutive 0’s or five consecutive 1’s? Solution: Let A be the set of bit strings of length 10 containing five consecutive 0’s. For i from 1 to 6, let Ai be the set of bit strings of length 10 in which the five consecutive 0’s starts at position i. Then A 1 , A2 , A3 , A4 , A5 and A6 are pairwise disjoint and A = A 1 ∪ A2 ∪ A3 ∪ A4 ∪ A5 ∪ A6 . By the sum rule, we have |A| = |A1 | + |A2 | + |A3 | + |A4 | + |A5 | + |A6 |. For the strings in A1 , the first five digits are 0’s and each of the last five digits can be either 0 or 1. Hence |A1 | = 1 × 1 × 1 × 1 × 1 × 2 × 2 × 2 × 2 × 2 = 32. For the strings in A2 , the first digit is 1, the next five digits are 0’s and each of the last four digits can be either 0 or 1. Hence |A2 | = 1 × 1 × 1 × 1 × 1 × 1 × 2 × 2 × 2 × 2 = 16. For the strings in A3 , the first digit is either 0 or 1, the second digit is 1, the next five digits are 0’s and each of the last three digits can be either 0 or 1. Hence |A3 | = 2 × 1 × 1 × 1 × 1 × 1 × 1 × 2 × 2 × 2 = 16. Similarly, |A4 | = |A5| = |A6 | = 16. 7

Consequently, |A| = 32 + 16 + 16 + 16 + 16 + 16 = 112. Let B be the set of bit strings of length 10 containing five consecuting 0’s. Similar to A, we have |B| = 32 + 16 + 16 + 16 + 16 + 16 = 112. Now A ∩ B = {0000011111, 1111100000}. By the principle of inclusion-exclusion, the number of bit strings of length 10 containing either five consecutive 0’s or five consecutive 1’s is |A ∪ B| = |A| + |B| − |A ∩ B| = 112 + 112 − 2 = 222.

8