CMPS 211 Final Sample, Fall 2010

Problem 1 (10 Points) a. (5)Determine whether the following two propositions are logically equivalent: p → (¬q ∧ r) ¬p ∨ ¬(r → q). b. (5) Suppose you have a Boolean expression involving n Boolean variables, and you want to build its truth table. How many rows will there be in the truth table? Why? Problem 2 (10 Points) a. (5) Use the Principle of Mathematical Induction to prove that 5 | (7n − 2n) for all n ≥ 0. b. (5) Find the error in the following “proof” of the “theorem”: Theorem: Every positive integer equals the next largest positive integer. Proof: Let P(n) be the proposition 'n = n + 1'. To show that P(k) → P(k + 1), assume that P(k) is true for some k, so that k = k + 1. Add 1 to both sides of this equation to obtain k + 1 = k + 2, which is P(k + 1). Therefore P(k) → P(k + 1) is true. Hence P(n) is true for all positive integers n. Problem 3 (20 Points) Suppose that A and B are two given finite sets, with |A| = m and |B| = n. Answer the following questions, with a brief justification. a. (5) How many functions can there be from A to B? b. (5) How many of these functions are one-to-one functions? c. (5) How many onto functions are there? d. (5) How many relations are there from A to B? Problem 4 (10 Points) Consider the following recursive algorithm where n is a positive integer and a is a real number. procedure foo(a: real number, n: positive integer) if n = 1 then foo(a,n) : = a else foo(a,n) : = a + foo(a,n − 1). a. What does this algorithm compute? b. Perform a complexity analysis for this algorithm to find T(n) the count of additions performed. (Ignore subtractions, and the overhead needed to call a procedure and the overhead needed to implement the if-then-else statement) First give a recursive definition of T(n), and then find T(n). Problem 5 (15 Points) Consider the equation x + y + z = 24. a. (5) How many solutions are there for the equation x + y + z = 24, where x, y, and z are nonnegative integers? Why? b. (5) Answer the same question in (a) if we also want y ≥ 10 and z ≥ 6. Why?. c. (5) How many solutions are there for the inequality x + y + z ≤ 24. , where x, y, and z are nonnegative integers? Why? Problem 6 (10 Points) In the questions below suppose you have 40 different books (20 math books, 15 history books, and 5 geography books). a. (3) You pick one book at random. What is the probability that the book is a history book? b. (3) You pick one book at random. What is the probability that the book is not a geography book? c. (4) You pick two books at random, one at a time. What is the probability that both books are history books? Problem 7 (10 Points) a. (5) What is the probability that the sum of the numbers on two dice is even when they are rolled? b. (5) Find and correct the error in the solution to the following problem: Problem: When a coin is flipped the outcome is either a head H or a tail T. You flip two coins and want to find the probability that both coins show heads. Solution: There are three possible outcomes: 2 heads, 2 tails, or 1 head and 1 tail. Since a “success” is one of these three outcomes, p(bothheads) = 1/3. Problem 8 (15 Points) Here C(n, r) is n! / [r! (n-r)!] a. (5) Use the binomial theorem to prove the following: 6 6 6 6 2 0 1 6 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ + +...+ = ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ . i.e. C(6,0) + C(6,1) + … + C(6,6) = 26 b. (5) Show that C(2n,2) = 2 C(n,2) + n2 using algebraic manipulation. c. (5) Show that C(2n,2) = 2 C(n,2) + n2 using a combinatorial argument. Problem 9 (10 Points) a. (5) How many ways are there to arrange the letters of the word NONSENSE? b. (5) How many of these ways start or end with the letter O? Problem 10 (15 Points) a. (5) Eight persons are to be seated in the front row at a banquet. How many different arrangements are there for the people? b. (5) Suppose that two persons A and B are at feud and are not to be seated next to each other, how many arrangements are possible? c. (5) If the 8 persons are to hold discussions on a round table, how many different arrangements are possible? Problem 11 (15 Points) Let R be the relation on the set A={0, 1, 2, 3} given by R={ (0,1), (1,1), (1,2), (2,0), (2,2), (3,0)}. a. (4) Show how R can be represented as a directed graph. b. (3) Show how R can be represented as a 0-1 matrix. c. (4) What elements not in R should be added to R to get the reflexive closure of R. d. (4) What elements not in R should be added to R to get the symmetric closure of R. Problem 12 (15 Points) Let S be the set of students, C be the set of courses, and P be the set of professors. Define the following binary relations: T is the relation from S to C where sTc means that student s is taking course c. G is the relation from C to P where cGp means that course c is given(taught) by professor p Assume that a student can take several courses at least 4 and at most 5. Also assume that up to 25 students can take a course. Further, assume that a course is taught by one professor, but a professor can be giving more than one course. a. (5) From what set to what set is the relation T-1 defined, and what does xT-1y mean? b. (5) Let H denote the composite of G and T (i.e. H = GoT ). From what set to what set is the H defined, and what does xHy mean? c. (5) Let U be the relation on S defined by xU y means that “student x is taking a course which student y is also taking”. Show that U is the composite of two of the relations mentioned above. Problem 13 (10 Points) Let A and B be two sets, and let R be a relation from A to B. (i.e. R ⊆ A × B ). We say that A has full participation in R if for any element a in A there is an element b in B such that aRb; or (a,b) ∈ R. If A does not have full participation, we say that it has partial participation.Similarly, we say that B has full participation in R if for any element b in B there is an element a in A such that aRb. We also say that R is many-to-one if an element a in A cannot be related to more than one element in B. Similarly, we say that R is one-to-many if an element b in B cannot be related to more than one element in A. In general R is many-to-many. a. (6) Write these definitions in terms of Boolean expression… complete the following: A has full participation in R: ∀x [x∈A → ∃y [y∈B ∧ ]]. B has full participation in R: R is many-to-one: b. (4) In terms of the definitions above, when does R represent a function from A to B? Problem 14 (5 Points) Let C be the set of courses. Define the following binary relations E and P on the set C: E is the relation on C where xEy means that course x is equivalent to course y; i.e. they have the same number of credits and they cover similar material.. P is the relation on C where xPy means that course x is co-requisite to course y; i.e. course x must be taken in the same semester with course y or x must completed before course y. a. Circle all the properties that E satisfies: Reflexive Symmetric Anti-symmetric Transitive Equivalence Partial Order Total Order b. Circle all the properties that P satisfies: Reflexive Symmetric Anti-symmetric Transitive Equivalence Partial Order Total Order Problem 15 (5 Points) Let A = Z the set of integers, and let R be the binary relation on A defined by R = { (n, n+1) : n∈Z} a. Circle the properties that R satisfies. Reflexive Symmetric Anti-symmetric Transitive Equivalence Partial Order Total Order b. What is the transitive closure R* of R ? Problem 16 (5 Points) Let A be the set of people, and R = { (x, y) : person x is a child of person y} a. Circle the properties that R satisfies. Reflexive Symmetric Anti-symmetric Transitive Equivalence Partial Order Total Order b. What is the transitive closure R* of R (What does it represent)? Problem 17 (10 Points) Suppose A is the set N+×N+ composed of all ordered pairs of positive integers. Let R be the relation defined on A where (a,b)R(c,d) means that ad = bc. (So e.g. (1,2)R(3,6) since 1*6=2*3…) a. (4) Prove that R is an equivalence relation. b. (4) What is is [(2,4)] the equivalence class of the pair (2,4) ? c. (2) Give an interpretation of the equivalence classes for the relation R. [Hint: Look at the ratio a/b corresponding to (a,b)] Problem 18 (10 Points) Suppose that f : A→ B is a function from A to B. Consider the following relation R on A : aRb if f(a) = f(b). You may want to use the notation f -1(b) = { a : a A and f(a) = b} a. Show that R is an equivalence relation. b. What are the equivalence classes of R? c. Suppose for this part that A = B = Z the set of integers, and that f(n) = n2. What is [m] R the equivalence class of m, for m in Z ? Problem 19 (10 Points) Let F = { f | f : N → N }, and define the binary relation T on F to be f T g if f(n) is O(g(n)) ; i.e. f is related to g if they have the same rate of growth asymptotically. Show that T is a partial order on F. Problem 20 (5 Points) Show that in a directed graph that has n vertices, any path of length greater than or equal to n (i.e. the path has at least n edges) must have a cycle. (a cycle is a path that starts at a vertex and ends at the same vertex). (Hint: Use the pigeon hole principle.)