Discrete math test

Final Exam Practice Questions 1.​ Is the following argument valid? If yes, show why by applying rules of inference to arrive at the conclusion. If not, show that the conclusion can be false while all the hypotheses are true. p → q q ∨ s → r p ____ ∴ r 1. p → q Hypothesis 2. p Hypothesis 3. q Modus ponens (1, 2) 4. q ∨ s Addition (3) 5. q ∨ s → r Hypothesis 6. r Modus ponens (4, 5) 2.​ P(x) means x is prime. E(x) means x is even. Use quantifier logic to generate the statement “there is exactly one prime that is even”. ∀x,y( (P(x) ​∧ E(x) ∧ ​P(y) ​∧ E(y) ​→ x = y) 3.​ Prove that the square of an odd integer is an odd integer. Direct proof: We can represent the odd integer as 2k + 1 where k is an integer. (2k + 1)​2​ = 4k​2​ + 4k + 1 = 2(2k​2​ + 2k) + 1. Since 2k​2​ + 2k is an integer, 2(2k​2​ + 2k) + 1 has to be odd. 4.​ A = {a, b}, B = {b, c, d}, C = A×B ∩ B×A. Write down the members of C using set notation. C = {(b, b)} 5.​ A, B and C are sets. Is it true that ∀ A,B,C ( A ⊆ B → A×C ⊆ B×C) ? Yes. 6.​ Give the first six terms of the following sequences. Sequence indices start from 0. a)​ ​b​0​ = 1, b​1​ = 3, and b​n​ = b​n-1​ - 7·b​n-2​ for n ≥ 2. 1, 3, -4, -25, 3, 178

b)​ g​0​ = 2 and g​1​ =1. The rest of the terms are given by the formula g​n​ = g​n-1​ + n·g​n-2​. 2, 1, 5, 8, 28, 68 c)​ a​0​ = 1, a​1​ = 1, and a​n​ = (2·a​n-1​) mod n + (3·a​n-2​) mod n for n ≥ 2. 1, 1, 1, 2, 0, 4 7.​ For the sequence above (at ​6c​), give a reasonably tight upper bound simple function using Big-O notation. Justify it. The recurrence relation formula for a​n​ is the sum of two numbers in mod n. It can be at most 2n-2. Since this is an upper bound, we can say the function is O(n). 8.​ A borrower takes a loan of amount ​X​ with monthly interest rate of ​r​. The loan is taken at month 0, and a payment of amount ​Y​ is made at the start of each month, starting at month 1. a)​ Give a recursive relation and a base case that define the sequence that gives the remaining balance on the borrower’s account. a​0​ = X a​n​ = (1 + r)a​n-1​ - Y b)​ Which monthly payment value ​Y​ causes the loan balance to stay the same each month? Find it in terms of ​X​ and ​r​. If it is not changing, then a​0​ = a​1​. Which means: X = (1 + r) X - Y Y = r X 9.​ Remember the Fibonacci series and how it is related to reproduction of biological organisms? Each adult organism produces one offspring at each time-step, and a newborn organism grows to an adult in one time-step. Now assume each adult produces two offspring organisms instead of one at each time-step. What is the recurrence relation of the new sequence? a​n​ = a​n-1​ + 2a​n-2

10.​ Prove that for any positive integer n, , by induction.(j )∑ n

j=1 j − 1 = 3

n(n −1) 2

Base case: For n = 1 1 (0) = 0 = 1 (1​2​ - 1) / 3 = 0. It is true for n = 1. Inductive case: Assume the equation is true for n = k. We will show it is also true for n = k + 1.

For n = k: (j )∑ k

j=1 j − 1 = 3

k(k −1) 2

For n = k + 1: = + (k+1)k(j )∑ k+1

j=1 j − 1 (j ))( ∑

k

j=1 j − 1

= + (k+1)k3 k(k −1) 2

= 3 k(k −1) + 3k(k+1) 2

= 3 k −k + 3k + 3k 3 2

= 3 k + 3k + 2k 3 2

If we put k+1 in the original formula, we get

3 (k+1)((k+1) −1) 2 = 3

(k+1)((k +2k+1) −1) 2

= 3 (k+1)(k +2k ) 2

= 3 k + 3k + 2k 3 2

Since we arrive at the same expression, we showed the formula is correct for n=k+1 if it is correct for n=k. Therefore, the original formula is correct. 11.​ Prove that n! > 2​n​ for n > 3 by induction. Base case: For n=4, 4! > 2​4

24 > 16, the base case is correct. Inductive step: We will assume that the inequality is true for n=k and will show that it is also true for n=k+1. k! > 2​k​ → (k+1)! > 2​k+1 If we multiply both sides of “k! > 2​k​” with k+1, we get (k+1)! > (k+1) 2​k Since we know that (k+1) 2​k​ > 2.2​k​ (because k+1 > 2 for k > 3), we can write (k+1)! > 2​k+1 Therefore, the original inequality is true. 12.​ Prove by induction: 5 evenly divides 9​n​ - 4​n​ for all n ∈ ℤ​+​. Base case: For n=1, 5|9​1​-4​1​, so the argument is correct.

Inductive step: We will assume that the argument is correct for n=k, and show that it is also correct for n=k+1. If 5 evenly divides 9​k​ - 4​k​, then we can write 9​k​ - 4​k​ = 5x for some integer x. Solve this for 9​k​. 9​k​ = 5x + 4​k For n=k+1, the question is whether 5 | 9​k+1​-4​k+1​. Since 9​k+1​ = 9.9​k​ = 9(5x+4​k​), we can rewrite the expression as 9(5x+4​k​) - 4​k+1​. Which is equal to = (5 . 9x) + (9 . 4​k​) - (4. 4​k​) = (5 . 9x) + (5 . 4​k​) = 5 (9x + 4​k​) Since 9x + 4​k​ is an integer, 5 | 5 (9x + 4​k​), so the argument is true for n=k+1. Therefore, 5|9​n​-4​n​ for all n ∈ ℤ​+​. 13.​ ​The sequence​ {a​n​} is defined with the recurrence relation a​n​ = a​n-1​ + n + 1, and the base case a​0​ = 0. Prove that .an = 2

n(n+3)

Base case: For n = 0, a​0​ = 0, 0 (0+3) / 2 = 0. The base case is true. Inductive step: We will show that if the closed formula for the function is true for n=k, then it is also true for n=k+1.

Assume a​k​ = . We will show that ​a​k+1​ = 2 k(k+3)

2 (k+1)(k+4) = 2

k +5k+42

Using the recurrence relation, a​k+1​ = a​k​ + k + 2 = + k + 2 = 2 k(k+3)

2 (k(k+3))+2(k+2) = 2

k +5k+42

Therefore, the equation is true for n=k+1. Therefore, the closed formula for the recursive function is correct. 14.​ Prove that using only 3-cent and 7-cent stamps, we can generate any amount of postage that is worth 12 cents or more. Base case: 12 cents can be generated by 4 3-cents. 13 cents can be generated by a 7-cent and 2 3-cents. 14 cents can be generated by 2 7-cents. Inductive step: Assume that for k ≥ 14 we can generate j cents worth of postage using only 3-cent and 7-cents for any j in the range from 12 to k. We will show that we can generate the amount k+1 using only 3-cents and 7-cents. Since k ≥ 14, then k - 2 ≥ 12. Therefore k - 2 falls in the range from 12 through k, and by the inductive hypothesis, it is possible to make k - 2 cents worth of stamps using only 3-cent and 7-cent stamps. By adding one 3-cent stamp, the amount of postage becomes (k - 2) + 3 = k + 1.

Therefore, it is possible to make k + 1 cents worth of postage using only 3-cent and 7-cent stamps. 15.​ Give a recursive definition of the set of palindromic words P. You can assume an empty string is also palindromic and denote it with the symbol ​λ​. Base case: ​λ ∈ S, ​a​ ∈ S, where ​a​ is a letter.  Recursive rule: if ​x​ ∈ S then ​axa​ ∈ S, where ​a​ is a letter.  16.​ Give a recursive definition for the set of integers (both positive and negative) divisible by 7. Base case: 0 ​∈ S  Recursive rule: If ​x​ ∈ S then  

x​ + 7 ∈ S  x​ - 7 ∈ S 

17.​ A full binary tree is defined recursively as below. Base case: A single vertex is a full binary tree. Recursive rule: If T​1​ and T​2​ are full binary trees, then a new full binary tree can be generated by taking a new vertex x, and connecting it to the roots of T​1​ and T​2​. x becomes the root of the new full binary tree. Draw all possible full binary trees with 7 vertices. There are 5 possible trees.

18​. Give a ​recursive​ algorithm (in pseudocode) that finds the maximum value in a given sequence. algorithm​ max(a​1​, a​2​, … a​n​) x := a​n y := max(a​1​, ... , a​n-1​) if​ x > y ​then ​return​ x else ​return​ y

end if 19.​ Assume a programming language does not support the multiplication operation between numbers, but supports addition and recursive calls. Give a recursive algorithm that can multiply two given integers in that programming language (as pseudocode). algorithm​ sum (a, b) if​ (b == 0) then ​return​ 0 else if​ (b > 0) ​then ​return​ a + sum(a, b-1) ​else ​return​ -a + sum(a, b+1) 20.​ Prove that ∀ a,b,c ((a,b,c ∈​ ℤ​ ∧ (a | b ∨ a | c)) → (a | bc)). Case 1: If a|b, then b = ka for some integer k. Then bc = kac, therefore it is divisible by a. Case 2: If a|c, then c = ka for some integer k. Then bc = bka, therefore it is divisible by a. So in any case, a|bc. 21.​ Prove that (x mod m) + (y mod m) = (x+y) mod m. Disproof by counterexample: 3 mod 5 + 4 mod 5 = 7. This is not equal to (3+4) mod 5, which is equal to 2. 22.​ The relation R is defined on set A = {23, 51, 36, 75, 35, 11, 102, 9, 10, 29}, and aRb means a ≡ b mod 3. a)​ Draw R in digraph notation.

b)​ Is R reflexive? symmetric? anti-symmetric? transitive? partial ordering? equivalence relation? Reflexive, symmetric, not antisymmetric, transitive, not partial ordering, it is an equivalence relation.

23.​ How many permutations of the set A = {0, 1, 2, 3, 4} are there for which the sum of the last two elements is smaller than 3? The last two elements will have either 0 and 1, or 0 and 2. Let’s focus on the first case: last two elements are 0 and 1. First 3 elements have 3! permutations, last two elements have 2! permutations. They are independent, so there are 3!2! ways to combine them. Case 2 is calculated the exact same way, there are 2.3!2! = 24 permutations. 24.​ How many strings over the alphabet {x, y} have length 12 and have exactly 5 x in it? C(12, 5) 25.​ How many bit strings of length 10 have less than 3 0s? C(10, 2) + C(10, 1) + C(10, 0) 26.​ How many 10-bit strings are there where the first 3 bits are the same as the last 3 bits? Since the last 3 bits are the same with first 3 bits, we can ignore the last 3 bits for counting. The answer is 2​7​. 27.​ How many permutations of the multiset A = {1, 1, 1, 2, 3, 4} does not have all 1s next to each other? Without the constraint, there are 6!/3! permutations. If all three 1s are next to each other, we can treat those as if a single element, so there are 4! permutations. We need to subtract this from the unconstrained case. The answer is (6!/3!) - 4! = 96 28.​ Count the number of strings of length 10 over the alphabet {a, b, c} if it has to contain 9 consecutive b’s. Since there will be 9 consecutive b’s, there is only one position left. It can be either at the start of the string or at the end of the string. In each case, all 3 letters can occupy this single position. These two cases cannot happen at the same time, so we need to sum up their counts. 3​1​ + 3​1​ = 6.

29.​ . If x​5​ cannot be more than 9, how many different combinations of values the x​i0∑ 10

i=1 xi = 2

variables can take? We find that by subtracting complement of the condition from the unconstrained case. Unconstrained: C(20 + 10 - 1, 10 - 1) = C(29, 9) Complement: Give 10 to x​5​, so there is only 10 more values to distribute. C(10 + 10 - 1, 10 - 1) = C(19, 9).

Answer: C(29, 9) - C(19, 9) = ​10015005 - 92378 = 9922627 30.​ A biased die will roll to 6 with probability 3/8. All other numbers have equal probability. There are 3 dice in a bag, 2 of them are fair and one of them is this specific biased die. We pick a die randomly, roll and get 5. What is the probability that we picked the biased die? E: We picked biased die F: We roll 5 P(E | F) = P(F | E) P(E) / (P(F | E) P(E) + P(F | Ē) P(Ē)) P(E) = 1/3 P(Ē) = 2/3 P(F | E) = 1/8 P(F | Ē) = 1/6 P(E | F) = (1/8 1/3) / ( (1/8 1/3) + (1/6 2/3) ) = 3 / 11 31.​ How many edges are there in K​4,5​? Is it a regular graph? 20 edges. Not regular. 32.​ How many edges are there in K​5,5​? Is it a regular graph? 25 edges, it is 5-regular. 33.​ Is it possible to have a 1-regular graph with 9 nodes? If yes, draw it, if not, tell why. In a 1-regular graph, each edge connects two pendants. Therefore the number of edges is half the number of vertices. This means the number of vertices can only be an even number. 34.​ Is it possible to have a 2-regular graph with 9 nodes? If yes, draw it, if not, tell why. C​9 35.​ Is it possible to have a 3-regular graph with 9 nodes? If yes, draw it, if not, tell why. In an undirected graph, the number of odd-degree vertices has to be even. So 9 vertices cannot all have degree 3. 36.​ Are the following two graphs isomorphic? If yes, provide an isomorphism function. If not, tell why they cannot be isomorphic.

They are isomorphic. f(a) = 2, f(b) = 3, f(c) = 1, f(d) = 6, f(e) = 4, f(f) = 5 37.​ Are the cube graph Q​2​ and the complete bipartite graph K​2,2​ isomorphic? If not, tell why they cannot be. Yes they are. Q​2​ is also C​4​. If we label the vertices of C​4​ clockwise as 1, 2, 3, 4, then all the edges will be between an odd-labeled vertex and an even-labeled vertex. Additionally, all odd-labeled vertices are connected to every even-labeled vertex and vice versa, therefore it is K​2,2​. 38.​ Does the below graph have an Euler circuit? Euler trail? Hamiltonian cycle? Hamiltonian path? Either show it or tell why there cannot be.

No Euler circuit or trail because the graph has 8 odd-degree vertices. The graph has a Hamiltonian cycle: a,b,f,e,g,h,d,c,a Remove the last step, it becomes a Hamiltonian path. 39.​ A forest has 50 nodes and 40 edges. How many connected components does it have? A forest has n - m edges. 50 - m = 40. m = 10 connected components. 40.​ A full 4-ary tree has 19 leaves. How many internal vertices does it have? The tree has 4i+1 vertices. The number of leaves is the total minus the number of internal vertices i. 4i + 1 - i = 19 Solve this equation for the number of internal vertices. i = 6

41.​ What is the minimum possible height of a tree with 20 internal vertices? Minimum height is achieved when all internal vertices except the root is at level 1. If there are internal vertices at level 1, their children will be at level 2. This is the minimum possible height. 42.​ What is the minimum height of a binary tree with 100 vertices? It is 6. Minimum height is achieved when the tree is balanced and its levels are complete with possible exception of the last level. A complete binary tree with 1 level will have 3 vertices, with 2 levels it will have 7 vertices. When the n​th​ level is complete, the tree will have 2​n+1​-1 vertices. When the 5th level is complete, the tree will have 63 vertices, when the 6​th​ level is complete, the tree will have 127 vertices. Since we have 100 vertices, the three height have to be higher than 5. But it can stay at height 6 because 100 is lower than 128. 6 is the minimum height possible.