Discrete Structures - Midterm 2 Homework Problems

List all the steps used by Algorithm 1 to find the maximum of the list 1, 8, 12, 9, 11, 2, 14, 5, 10, 4

[3.1 #1]

max := 1,
i := 2,
max := 8,
i := 3,
max := 12,
i := 4,
i := 5,
i := 6,
i := 7,
max := 14,
i := 8,
i := 9,
i := 10,
i := 11

Determine which characteristics of an algorithm the following procedure has and which it lacks:

procedure double(n: positive integer)
while n > 0
n:=2n

[3.1 #2a] This procedure is not finite, since execution of the while loop continues forever.

Determine which characteristics of an algorithm the following procedure has and which it lacks:

procedure divide(n: positive integer)
while n >= 0
m := 1/n
n := n-1

[3.1 #2b] This procedure is not effective, because the step m := 1/n cannot be performed when n = 0, which will eventually be the case

Determine which characteristics of an algorithm the following procedure has and which it lacks:

procedure sum(n: positive integer)
sum := 0
while i < 10
sum := sum + 1

[3.1 #2c] This procedure lacks definiteness, since the value of i is never set.

Determine which characteristics of an algorithm the following procedure has and which it lacks:

procedure choose(a,b: integers)
x := either a or b

[3.1 #2d] This procedure lacks definiteness, since the statement does not tell whether x is to be set equal to a or to b.

Devise an algorithm that finds the sum of all the integers in a list

[3.1 #3]

procedure AddUp(a1,… , an: integers)
sum := a1
for i :=2 to n
sum := sum + a_i
return sum

Describe an algorithm that takes as input a list of n integers and produces as output the largest difference obtained by subtracting an integer in the list from the one following it

[3.1 #4] Set the answer to be −∞. For i going from 1 through n − 1, compute the value of the (i + 1)st element in the list minus the i th element in the list. If this is larger than the answer, reset the answer to be this value.

Describe an algorithm that takes as input of list n integers in nondecreasing order and produces the list of all values that occurs more than once.

[3.1 #5]

procedure duplicates(a1, a2,… , an: integers in nondecreasing order)
k := 0 {this counts the duplicates}

j := 2

while j ≤ n

if a_j = a_j−1 then

k := k + 1

c_k := a_j

while j ≤ n and aj = ck

j := j + 1

j := j + 1

{c₁, c₂,… , c_k is the desired list}

Describe an algorithm that takes an input a list of n integers and finds the number of negative integers in the list

[3.1 #6]

procedure negatives(a₁, a₂, . . . , a_n : integers)

k := 0

for i := 1 to n

if a_i < 0 then k := k + 1

return k {the number of negative integers in the list}

List all the steps used to search for 7 in the sequence given for both a linear search and a binary search

1, 3, 4, 5, 6, 9, 11

[3.1 #14]

a) With linear search we start at the beginning of the list, and compare 7 successively with 1, 3, 4, 5, 6, 8, 9, and 11. When we come to the end of the list and still have not found 7, we conclude that it is not in the list.

b) We begin the search on the entire list, with i = 1 and j = n = 8. We set m := 4 and compare 7 to the fourth element of the list. Since 7 > 5, we next restrict the search to the second half of the list, with i = 5 and j = 8. This time we set m := 6 and compare 7 to the sixth element of the list. Since 7 6> 8, we next restrict ourselves to the first half of the second half of the list, with i = 5 and j = 6. This time we set m := 5, and compare 7 to the fifth element. Since 7 > 6, we now restrict ourselves to the portion of the list between i = 6 and j = 6. Since at this point i 6 !< j, we exit the loop. Since the sixth element of the list is not equal to 7, we conclude that 7 is not in the list.

Devise an algorithm that finds all terms of a finite sequence of integers that are greater than the sum of all previous terms of the sequence

[3.1 #34]

Assume the input is strings a_1,a₂…an and b,₁b₂…b_n, where each character is a letter, A through Z. Assume also that a function index is available, such that index(x) is the position of the letter x in the alphabet (index(‘A’) = 1, ..., index(‘Z’) = 26).

a) Initialize a-count and b-count to be lists of length 26 with all values equal to 0. For i from 1 to n increment a-count(index(a_i)) and b-count(index(b_i)). If a-count(i) = b-count(i) for all i from 1 to 26, then return “true”; otherwise return “false.”

b) Sort both strings into alphabetical order. Then the two original strings were anagrams if and only if the sorted strings are identical

Sort this list using the selection sort

3, 5, 4, 1, 2

[3.1 #43a]
1, 5, 4, 3, 2;
1, 2, 4, 3, 5;
1, 2, 3, 4, 5;
1, 2, 3, 4, 5

Use the cashier’s algorithm to make change using quarters, dimes, nickels, and pennies for 99 cents

[3.1 #56c] The algorithm uses three quarters, leaving 24 cents, then two dimes, leaving 4 cents, then four pennies

Determine whether this function is O(x²)

f(x) = 17x +11

[3.2 #2a] Yes, since 17x + 11 ≤ 17x + x = 18x ≤ 18x² for all x > 11. The witnesses are C = 18 and k = 11

Determine whether this function is O(x²)

f(x) = xlogx

[3.2 #2c] Yes, since x log x ≤ x · x = x² for all x in the domain of the function. (The fact that log x < x for all x follows from the fact that x < 2^x for all x, which can be seen by looking at the graphs of these two functions.) The witnesses are C = 1 and k = 0.

Determine whether this function is O(x²)

f(x) = 2^x

[3.2 #2e] No. If 2x were O(x²), then the fraction 2^x/x² would have to be bounded above by some constant C. It can be shown that in fact 2x > x³ for all x ≥ 10 (using mathematical induction—see Section 5.1—or calculus), so 2^x/x² ≥ x³/x² = x for large x, which is certainly not less than or equal to C.

Determine whether this function is O(x²)

f(x) = x² + 1000

[3.2 #2b] Yes, since x² + 1000 ≤ x 2 + x² = 2x² for all x > √1000. The witnesses are C = 2 and k = √1000

Determine whether this function is O(x²)

f(x) = x⁴ / 2

[3.2 #2d] No. If there were a constant C such that x⁴/2 ≤ Cx² for sufficiently large x, then we would have C ≥ x²/2. This is clearly impossible for a constant to satisfy

Determine whether this function is O(x²)

f(x) = floor[x] * ceiling[x]

[3.2 #2f] Yes, since floor[x]*ceiling[x] ≤ x(x + 1) ≤ x · 2x = 2x² for all x > 1. The witnesses are C = 2 and k = 1.

Use the definition of “f(x) is O(g(x))” to show that 2^x + 17 is O(3^x)

[3.2 #4] If x > 5, then 2^x + 17 ≤ 2^x + 2^x = 2 · 2^x ≤ 2 · 3^x. This shows that 2^x + 17 is O(3^x) (the witnesses are C = 2 and k = 5).

Let P(n) be the statement that 1²+2²+…+n² = n(n+1)(2n+1)/6 for the positive integer n

a) What is the statement P(1)

b) Show that P(1) is true, completing the basis step of a proof that P(n) is true for all positive integers n

c) What is the inductive hypothesis of a proof that P(n) is true for all positive integers n?

d) What do you need to prove in the inductive step of a proof that P(n) is true for all positive integers n?

e) Complete the inductive step of a proof that P(n) is true for all positive integers n, identifying where you use the inductive hypothesis

f) Explain why these steps show that this formula is true whenever n is a positive integer

[5.1 #3]

Prove that 1²+3²+5²+…+(2n+1)² = (n+1)(2n+1)(2n+3)/3

[5.1 #5]

Prove that 2ⁿ > n² if n is an integer greater than 4

[5.1 #21]

Determine which amount of postage can be formed using just 4-cent and 11-cent stamps

Prove your answer using strong induction. How does the inductive hypothesis in this proof differ from that in an inductive hypothesis for a proof using mathematical induction?

[5.2 #5a,c]

What is the quotient and remainder when 44 is divided by 8?

[4.1 #14a] Since 8 · 5 = 40 and 44 − 40 = 4, we have quotient 44 div 8 = 5 and remainder 44 mod 8 = 4.

What is the quotient and remainder when 777 is divided by 21?

[4.1 #14b] Since 21 · 37 = 777, we have quotient 777 div 21 = 37 and remainder 777 mod 21 = 0.

What is the quotient and remainder when -123 is divided by 19?

[4.1 #14c] As above, we can compute 123 div 19 = 6 and 123 mod 19 = 9. However, since the dividend is negative and the remainder is nonzero, the quotient is −(6 + 1) = −7 and the remainder is 19 − 9 = 10. To check that −123 div 19 = −7 and −123 mod 19 = 10, we note that −123 = (−7)(19) + 10.

What time does a 24-hour clock read 168 hours after it reads 19:00?

[4.1 #16c] Because 168 ≡ 0 (mod 24), the clock read 19:00

Find a div m and a mod m when a = -111, m = 99

[4.1 #28a] 111/99 is between 1 and 2, so the quotient is −2 and the remainder is −111−(−2)·99 = −111+198 = 87.

Find a div m and a mod m when a = -9999, m = 101

[4.1 #28b] −9999/101 = −99, so that is the quotient and the remainder is 0

Is 37 congruent to 3 modulo 7?

[4.1 #34a] No → 37 − 3 mod 7 = 34 mod 7 = 6 6 != 0, so 37 6 !≡ 3 (mod 7)

Is 66 congruent to 3 modulo 7?

[4.1 #34b] Yes → 66 − 3 mod 7 = 63 mod 7 = 0, so 66 ≡ 3 (mod 7)

Is -17 congruent to 3 modulo 7?

[4.1 #34c] No → −17 − 3 mod 7 = −20 mod 7 = 1 6= 0, so −17 6≡ 3 (mod 7)

Is -67 congruent to 3 modulo 7?

[4.1 #34d] Yes → −67 − 3 mod 7 = −70 mod 7 = 0, so −67 ≡ 3 (mod 7)

Find the prime factorization for 39

[4.3 #4a] 39 = 3 · 13

Find the prime factorization for 81

[4.3 #4b] 81 = 3⁴

Find the prime factorization for 101

[4.3 #4c] 101 = 101 (prime)

Find the prime factorization for 143

[4.3 #4d] 143 = 11 · 13

Find the prime factorization for 289

[4.3 #4e] 289 = 17²

Find the prime factorization for 899

[4.3 #4f] 899 = 29 · 31

Which positive integers less than 12 are relatively prime to 12?

[4.3 #14] We must find, by inspection with mental arithmetic, the greatest common divisors of the numbers from 1 to 11 with 12, and list those whose gcd is 1. These are 1, 5, 7, and 11. There are so few since 12 had many factors—in particular, both 2 and 3.

Show that 6 and 28 are perfect

[4.3 #18a] Since 6 = 1 + 2 + 3, and these three summands are the only proper divisors of 6, we conclude that 6 is perfect. Similarly 28 = 1 + 2 + 4 + 7 + 14.

What are the greatest common divisor of:

2×3×5×7×11×13

2¹¹×3⁹×11×17¹⁴

[4.3 #24a] 2² · 3³ · 5²

What are the greatest common divisor of:

17

17¹⁷

[4.3 #24b] 2 · 3 · 11

Use the Euclidean algorithm to find gcd(11111, 111111)

[4.3 #32f] gcd(11111, 111111) = gcd(11111, 1) = gcd(1, 0) = 1

Encrypt the message STOP POLLUTION by translating the letters into numbers, applying the given encryption function, and then translating the numbers back into letters:

f(p) = (p+4) mod 26

[4.6 #2a] WXST TSPPYXMSR

Encrypt the message STOP POLLUTION by translating the letters into numbers, applying the given encryption function, and then translating the numbers back into letters:

f(p) = (p+21) mod 26

[4.6 #2b] NOJK KJHHPODJI

Encrypt the message STOP POLLUTION by translating the letters into numbers, applying the given encryption function, and then translating the numbers back into letters:

f(p) = (17p + 22) mod 26

[4.6 #2c] QHAR RABBYHCAJ

Decrypt this message that was encrypted using the Caesar cipher → f(p) = (p+3) mod 26

EOXH MHDQV

[4.6 #4a] BLUE JEANS

Decrypt this message that was encrypted using the Caesar cipher → f(p) = (p+3) mod 26

WHVW WRGDB

[4.6 #4b] TEST TODAY

Decrypt this message that was encrypted using the Caesar cipher → f(p) = (p+3) mod 26

HDW GLP VXP

[4.6 #4c] EAT DIM SUM

For the following relation on the set {1,2,3,4}, decide whether it is reflexive, symmetric, antisymmetric, and/or transitive

{(2,2),(2,3),(2,4),(3,2),(3,3)(3,4)}

[9.1 #3a] Transitive

For the following relation on the set {1,2,3,4}, decide whether it is reflexive, symmetric, antisymmetric, and/or transitive

{(1,1), (1,2), (2,1), (2,2), (3,3), (4,4)}

[9.1 #3b] Reflexive, symmetric, transitive

For the following relation on the set {1,2,3,4}, decide whether it is reflexive, symmetric, antisymmetric, and/or transitive

{(2,4), (4,2)}

[9.1 #3c] Symmetric

For the following relation on the set {1,2,3,4}, decide whether it is reflexive, symmetric, antisymmetric, and/or transitive

{(1,2), (2,3), (3,4)}

[9.1 #3d] Antisymmetric

For the following relation on the set {1,2,3,4}, decide whether it is reflexive, symmetric, antisymmetric, and/or transitive

{(1,1), (2,2), (3,3), (4,4)}

[9.1 #3e] Reflexive, symmetric, antisymmetric, transitive

For the following relation on the set {1,2,3,4}, decide whether it is reflexive, symmetric, antisymmetric, and/or transitive

{(1,3), (1,4), (2,3), (2,4), (3,1), (3,4)}

[9.1 #3f] None of these properties

Determine whether the relation R on the set of all Web pages is reflexive, symmetric, antisymmetric, and/or transitive, where (a,b) are members of R if and only if everyone who has visited Web page a has also visited Web page b

[9.1 #5a] Reflexive, transitive

Give an example of a relation on a set that is both symmetric and antisymmetric

[9.1 #10a] the empty set on {a} (vacuously symmetric and antisymmetric)

Give and example of a relation on a set that is neither symmetric nor antisymmetric

[9.1 #10b] {(a, b),(b, a),(a, c)} on {a, b, c}

Use the cashier’s algorithm to make change using quarters, dimes, nickels, and pennies for 87 cents

[3.1 #56a] This is immediate from the definition, since R is reflexive if and only if it contains all the pairs (x, x), which in turn happens if and only if R̅ contains none of these pairs, i.e., R̅ is irreflexive.

Prove that part iii of Theorem 1 is true

[4.1 #4] Suppose a | b, so that b = at for some t, and b | c, so that c = bs for some s. Then substituting the first equation into the second, we obtain c = (at)s = a(ts). This means that a | c, as desired.

Prove that if a and b are integers and a divides b, then a is odd or b is even

[4.1 #9] It is given that b = m ⋅ a for some integer m. If a is not odd, then a = 2k for some integer k, whence b = 2km. This means by definition that b is even

Prove that if a and b are nonzero integers, a divides b, and a+b is odd, then a is odd

[4.1 #10] It is given that b = m · a for some integer m. Assume, contrary to the goal, that a is even, i.e., a = 2k for some integer k . Then a + b = 2k + m(2k) = 2(k + mk). This means that a + b is even, contrary to the given condition that it is odd. Therefore a must be odd.

What is:

(177 mod 31 + 270 mod 31) mod 31

[4.1 #36a] (177 mod 31 + 270 mod 31) mod 31 = (22 + 22) mod 31 = 44 mod 31 = 13

What is:

(177 mod 31 × 270 mod 31) mod 31

[4.1 #36b] (177 mod 31 · 270 mod 31) mod 31 = (22 · 22) mod 31 = 484 mod 31 = 19

Let P(n) be the statement that 1³+2³+…+n³ = (n(n+1)/2)² for the positive integer n.

a) What is the statement P(1)?

b) Show that P(1) is true, completing the basis step of the proof of P(n) for all positive integers n

c) What is the inductive hypothesis of a proof that P(n) is true for all positive integers n?

d) What do you need to prove in the inductive step of a proof that P(n) is true for all positive integers n?

f) Explain why these steps show that this formula is true whenever n is a positive integer

[5.1 #4]

Prove that 1×1!+2×2!+…+(2n+1)² = (n+1)! -1 whenever n is a positive integer

[5.1 #6]