Discrete math test
ndrnima
CS220FinalExamPracticeQuestions.pdf
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 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”. 3. Prove that the square of an odd integer is an odd integer. 4. A = {a, b}, B = {b, c, d}, C = A×B ∩ B×A. Write down the members of C using set notation. 5. A, B and C are sets. Is it true that ∀ A,B,C ( A ⊆ B → A×C ⊆ B×C) ? 6. Give the first six terms of the following sequences. Sequence indices start from 0. a) b0 = 1, b1 = 3, and bn = bn-1 - 7·bn-2 for n ≥ 2. b) g0 = 2 and g1 =1. The rest of the terms are given by the formula gn = gn-1 + n·gn-2. c) a0 = 1, a1 = 1, and an = (2·an-1) mod n + (3·an-2) mod n for n ≥ 2. 7. For the sequence above (at 6c), give a reasonably tight upper bound simple function using Big-O notation. Justify it.
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. b) Which monthly payment value Y causes the loan balance to stay the same each month? Find it in terms of X and r. 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?
10. Prove that for any positive integer n, , by induction.(j )∑ n
j=1 j − 1 = 3
n(n −1) 2
11. Prove that n! > 2n for n > 3 by induction. 12. Prove by induction: 5 evenly divides 9n - 4n for all n ∈ ℤ+. 13. The sequence {an} is defined with the recurrence relation an = an-1 + n + 1, and the base case a0 = 0. Prove that .an = 2
n(n+3)
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. 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 λ. 16. Give a recursive definition for the set of integers (both positive and negative) divisible by 7.
17. A full binary tree is defined recursively as below. Basis: A single vertex is a full binary tree. Recursive rule: If T1 and T2 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 T1 and T2. x becomes the root of the new full binary tree. Draw all possible full binary trees with 7 vertices. 18. Give a recursive algorithm (in pseudocode) that finds the maximum value in a given sequence. 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). 20. Prove that ∀ a,b,c ((a,b,c ∈ ℤ ∧ (a | b ∨ a | c)) → (a | bc)). 21. Prove that (x mod m) + (y mod m) = (x+y) mod m. 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? 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? 24. How many strings over the alphabet {x, y} have length 12 and have exactly 5 x in it?
25. How many bit strings of length 10 have less than 3 0s? 26. How many 10-bit strings are there where the first 3 bits are the same as the last 3 bits? 27. How many permutations of the multiset A = {1, 1, 1, 2, 3, 4} does not have all 1s next to each other? 28. Count the number of strings of length 10 over the alphabet {a, b, c} if it has to contain 9 consecutive b’s.
29. . If x5 cannot be more than 9, how many different combinations of values the xi0∑ 10
i=1 xi = 2
variables can take? 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? 31. How many edges are there in K4,5? Is it a regular graph? 32. How many edges are there in K5,5? Is it a regular graph? 33. Is it possible to have a 1-regular graph with 9 nodes? If yes, draw it, if not, tell why. 34. Is it possible to have a 2-regular graph with 9 nodes? If yes, draw it, if not, tell why. 35. Is it possible to have a 3-regular graph with 9 nodes? If yes, draw it, if not, tell why.
36. Are the following two graphs isomorphic? If yes, provide an isomorphism function. If not, tell why they cannot be isomorphic.
37. Are the cube graph Q2 and the complete bipartite graph K2,2 isomorphic? If not, tell why they cannot be. 38. Does the below graph have an Euler circuit? Euler trail? Hamiltonian cycle? Hamiltonian path? Either show it or tell why there cannot be.
39. A forest has 50 nodes and 40 edges. How many connected components does it have? 40. A full 4-ary tree has 19 leaves. How many internal vertices does it have? 41. What is the minimum possible height of a tree with 20 internal vertices? 42. What is the minimum height of a binary tree with 100 vertices?
