Homework
Part I.
Q#1.
a) What is the definition of: Composite Function, Inverse Function and definition of Big-O? Provide with example in each case for illustration.
b) What is the order of magnitude of the function? S(2n) = 2 + 4 + 6 + … + 2n ?
Q#2.
Explain in your own words, with an example what are the elements, differences of Mathematical Proofs and Principle of Mathematical Induction?
Q#3.
Please provide a formal proof for the following:
If X is odd then X^2 + X iseven
a) Provide a general definition of a One-to-One (Injective) Function b) the definition of an On-to (Surjective) Function.
c) Is the following function X and Y, 1-to-1 and on-to, why?
G
X 0 1 Y
1 3
3
d) Assume the domain and co-domain is I, the set of integers; can you find out the function h (x) = x^3 + 7 is one to one or onto? (Note: x^3; means x to the power of 3)
Q#5.
Use mathematical proofs to show that:
1 + 3 + 5 + . . . + (2n − 1) = n^2 (^2 means n to the power of 2)
Q#6.
Let n and k be some integers with 0 <= k <= n. Then, what is the binomial coefficient formula expression in terms of n and k?
Explain and provide proofs for the following:
Q#8.
1.) Construct the truth tables for the following propositions:
a. p and (q or not p)
b. (p or q) and (q or not p)
c. p and (q or not r)
d. (p and q) or (p and r)
2. ) Use truth tables to determine whether the following is valid argument:
if p then q
if q then p therefore p or q
For every positive integer n,
Let P(n) be the formula: 12 + 22 + ... + n2 = (n (n+1)(2n + 1)) / 6 a. What is the value of P(1)? Is P(1) true?
b. What is the value of P(10)? Is P(10) true?
c. What is the value of P(k), the value of P(k+1)?
Q#10.
Please provide a counterexample to disprove each of the following:
a. For all real numbers a and b, if a2 = b2 then a = b
b. For all real numbers a and b, if a3 = b3 then a = b
c. For all integers m and n, if 2m + n is odd then m and n are odd d. For all integers m and n, if 2m - n is even then m and n are even
Q#11.
• Use Venn diagrams to determine whether each of the following is true or false:
a. (A union B) intersect C = A union (B intersect C)
b. A intersect (B union C) = (A intersect B) union (A intersect C)
• Calculate the number of integers divisible by 4 between 50 and 500, inclusive.
• Use the permutation formula to calculate the number permutations of the set {a, b, c, d} taken two at a time. Also list these permutations.
• Determine whether each of the following functions is 1-to-1 and whether it is onto. Assume the domain and co-domain is Z, the integers. Explain your answers.
a. f(n) = n / 2, assuming integer division
b. g(n) = 4n + 5
Q#12.
Give detailed example for the following: (a) A function f is said to be one- to-one, or an injection under what condition? (b) Explain when a function f : X -> Y is onto, or a surjection? (c) A function that is both one-to-one and onto is called a bijection, or a one-to-one correspondence, why? Please give an example. (d) A bijection from a set onto itself is called a permutation, why? Provide another example to show your point.
Q#13.
Write down all the functions from (a) the 2-element set {1, 2} to the 2- element set {a, b}. (b) How many functions are there from a 2-element set to a 3-element set? (c) How many functions are there from a 3-element set to a
2-element set?
Q#14.
a) What is the formal definition of a function? Why function is a relation with additional constraints? Can you provide with an example? b) At what time when two relations not functions? Please provide with a complete example for these two relations. c) What important properties that a function can have if they are one-to-one (1-to-1) and onto?
Part II.
Q#15.
What is the meaning of isomorphic for graphs? Please provide an example for it. What happen if two graphs are not isomorphic? Can you illustrate with an example?
Q#16.
Let A, B, C, D be four remote satellite campus served by University of
Maryland as shown in this digraph:
a) What is the corresponding Boolean adjacency matrix for this graph of remote satellite campus? b) Now, please construct all four Boolean adjacency matrices and calculate the reachable matrix for the graph in the adjacency matrix in part (a) and finally, c) provide the definition of reachable vertex.
Q#17.
a) What is the formal definition of trees in discrete mathematics? Please provide an example of a tree with root n. Please indicate the drawing of relationship between a parent node and its children. b) Construct an ordered tree to calculate the following mathematical expression: (a + b
– c * d) / e
Q#18.
a) Define the meaning of a rooted tree. What are the meanings of parent, descendant and sibling for a given rooted tree? b) Describe a spanning tree, what is the major different from a non-spanning tree? How to construct a spanning tree? How to perform breadth-first searching, depth-first searching and may be even backtracking of such a tree?
Q#19.
a) What are decision trees? b) Why they are helpful structures in determining the outcomes of certain scenarios and as problem-solving tools? c) Can you construct a tree depicting all possible moves in the game of tic- tac-toe? Please provide all diagrams.
Q#20.
What is a binary tree? Please construct a binary tree and use it as your example. How to make a binary tree full?