Discrete Mathematics Answers

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)

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 𝑛 = 𝑂(𝑛)

The following formulas have been abbreviated based on the common abbreviation rules. Follow the steps below and translate the formulas into good English.

·       Step 1: Re-add the omitted brackets.

·       Step 2: If necessary, convert them into some other logically equivalent formula

so as to make it more readable. Write out the rule(s) you use for conversion.

·       Step 3: Translate the formulas into `good' English. Try to make your translation as brief/understandable as possible. (For instance, `John and Bill are coming' is better than `John is coming and Bill is coming.')

p: John wants to come to the class.

q: John will come to the class today.

r: John audits the class.

s: John is enrolled in the class.

Hint:

`No matter whether John is going or not, I'm going.' is the translation for (j à i) ^ (⌐j à i),

in which j = John is going, i = I'm going.)

Let A, B, C, D denote, respectively, art, biology, chemistry, and drama courses.

Find the number N of students in a dormitory given the data:

12 take A, 5 takeAand B, 4 takeB and D, 2 take B, C,D,

20 take B, 7 takeAand C, 3 takeC and D, 3 take A, C,D,

20 take C, 4 takeAand D, 3 take A, B,C, 2 take all four,

8 take D, 16 takeB and C, 2 take A, B, D, 71 take none.

Draw a simple, undirected graph yourself, the vertices are connected with each other including 8 vertices and 14 edges. Find the shortest path from two arbitrary vertices:​

a) The weight of each edge is 1.​

b) Self-weighting for edges

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.)

Obtain the Conjunctive Normal Form of (x^y) V (-x^y)

The argument is p→~q,~r→p,q|–r in true table in mathematical foundations of computer science

Let R={(1,2),(1,4),(2,1),(2,4),(3,2),(3,4)}

R={(1,2),(1,4),(2,1),(2,4),(3,2),(3,4)}

is a relation on set A={1,2,3,4}

A={1,2,3,4}

Suppose a Rn b

means that there is a path of length n from a

to b

Which of the elements are R3?

Suppose there are 10 male and 6 female professors to teach Discrete mathematics. In how

many ways a student can choose Discrete mathematics professor.