Search & Filtering
List the ordered pairs in the relation R from A = {0, 1, 2, 3, 4} to B = {0, 1, 2, 3}, where (a, b) ∈ R if and only if a | b.
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?
LetR={(1,2),(2,1),(2,3),(2,4),(4,1),(4,3)}
R={(1,2),(2,1),(2,3),(2,4),(4,1),(4,3)}
is a relation on
setA={1,2,3,4}
Suppose aRnb
means that there is a path of length n
from a to b
Which of elements are of
R∞
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.
1. 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.)
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)
15.Determine whether f: R to R, defined as f (x) = −3x + 4 is a bijection. Is f invertible, and if it is,
what is its inverse?
16.Find the inverse of f (x) =
𝑥+1
𝑥+2
, on a suitable subset of R.
Labelled and Unlabelled trees.
(a) How many labelled trees of order 5 are there?
(b) Draw all unlabeled tree of order 5 (under isomorphism). Hint: make cases on the diameter size.
How many 5 vertices unlabelled trees are there? How would I draw them?
