Discrete Mathematics Answers

State TRUE or FALSE justifying your answer with proper reason.

a. 2𝑛^2 + 1 = 𝑂(𝑛^2 )

b. 𝑛^2 (1 + √𝑛) = 𝑂(𝑛^2 )

c. 𝑛^2 (1 + √𝑛) = 𝑂(𝑛^2 log 𝑛)

d. 3𝑛^2 + √𝑛 = 𝑂(𝑛 + 𝑛√𝑛 + √𝑛)

e. √𝑛 log 𝑛 = 𝑂(𝑛)

solve the following recurrence relations

a. 𝑇(𝑛) = 𝑇( 𝑛/4) + 𝑇( 𝑛/2 ) + 𝑛^2

b. T(n) = T(n/5) + T(4n/5) + n

c. 𝑇(𝑛) = 3𝑇( n/4 ) + 𝑐𝑛^2 

f. 𝑇(𝑛) = (𝑛/𝑛−5) * 𝑇(𝑛 − 1) + 1

g. 𝑇(𝑛) = 𝑇(log 𝑛) + log 𝑛

h. 𝑇(𝑛) = 𝑇 (𝑛^ 1/ 4) + 1

i. 𝑇(𝑛) = 𝑛 + 7 √𝑛 ∙ 𝑇(√𝑛)

j. 𝑇(𝑛) = 𝑇 ( 3𝑛/4 ) + 1/root(n)

solve the following recurrence relations

a. 𝑇(𝑛) = 𝑇( 𝑛/4) + 𝑇( 𝑛/2 ) + 𝑛^2

b. T(n) = T(n/5) + T(4n/5) + n

c. 𝑇(𝑛) = 3𝑇( n/4 ) + 𝑐𝑛^2 

f. 𝑇(𝑛) = (𝑛/𝑛−5) * 𝑇(𝑛 − 1) + 1

g. 𝑇(𝑛) = 𝑇(log 𝑛) + log 𝑛

h. 𝑇(𝑛) = 𝑇 (𝑛^ 1/ 4) + 1

i. 𝑇(𝑛) = 𝑛 + 7 √𝑛 ∙ 𝑇(√𝑛)

j. 𝑇(𝑛) = 𝑇 ( 3𝑛/4 ) + 1/root(n)

Define a relation R on {a,b,c, int i* e . a Reflexive but not symmetric ↳ Symmetric but not transitive <> Transitive but not reflexive

Define a relation - on the set of real numbers by

x-ymeans I x | + I y I : I x+y l.

which of the properties for an equivalence relation does - satisfy?

Draw the Hasse diagram for the lattice (D₂4, 1). Hence find. a) maximal & minimal element b) glb of 446 geb of 8 & 2 d) lub of 8 & 6

Consider a relation R=\ (1,1),(1, ), (0,2), (2,3) (3,1)) on the set A=\ 1,2,3\ Find transitive closure of the relation R using algorithm Warshall's

For the relation R = {(p,p) ,(q,p),(q,q),(r,r),(r,s),(s,s) ,(s,m) ,(m,m)}

1.Using warshall algorithm find the transitive closure R* of R

2.write matrix representation of R*

3.Check whether the relation of R* is an equivalence relation or a partial order.

A pet store keeps track of the purchases of customers over a fours hour period. The store manager classifies purchases as containing a dog product, a cat product, a fish product, or product for a different kind of pet. He found!

83 purchased a dog product

101 purchased a cat product

22 purchased a fish product

31 purchased a dog and a cat product

8 purchased a dog and a fish product

10 purchased a cat and a fish product

6 purchased a dog, a cat, and a fish product

34 purchased a product for a pet other than a dog, cat, or fish.

Draw a Venn diagram to find that:

(1) How many purchases were for a dog product only?

(ii) How many purchases were for a cat product only?

How many purchases were for a dog or a fish product?

(iv) How many purchases were there in total?

Let a and b be two cardinal numbers. Modify Cantor’s definition of a < b to define a ≤ b. (Hint: Examine what happens if you drop condition (a) from Cantor’s definition of a < b.) 2. Prove that a ≤ a. 3. Prove that if a ≤ b and b ≤ c, then a ≤ c. 4. Do you think that a ≤ b and b ≤ a imply

a = b? Explain your reasoning. (Hint: This is not as trivial as it might look.)