Paper 2 CS Discrete Structures and Optimization Part 2

“→ An undirected graph possesses an eulerian circuit if and only if it is connected and its vertices all of even degree.
→ Eulerian circuit (or) Euler tour in an undirected graph is a cycle that uses each edge exactly once. “

“Here, we have to find all possible integers between 250 which was divisible by 2,5 and 7.
Solving this problem by 2 methods:
1. Venn diagram
2. Mathematical substitution.
In this problem, we are using Mathematical substitution method.
Step-1: According to condition, we can perform least common multiple(LCM) of 2,5 and 7=70
Step-2: Total number of integers= ⌊250/70⌋
= 3
Note: Divisible numbers are 70,140 and 210. “

“Probability of events for a Poisson distribution:
An event can occur 0, 1, 2, … times in an interval. The average number of events in an interval is designated (lambda). is the event rate, also called the rate parameter. The probability of observing k events in an interval is given by the equation
P(k events in interval)=e-λ [(λk)/k!]
Where
→ λ is the average number of events per interval
→ e is the number 2.71828… (Euler’s number) the base of the natural logarithms
→ k takes values 0, 1, 2, …
→ k! = k × (k − 1) × (k − 2) × … × 2 × 1 is the factorial of k.
→ Now it is given that in 1 hour (60 minutes) 20 requests are made
→ In 1 minute number of requests made= 20/60
→ In 45 minutes total number of requests made = (20/60) * 45
= 15
Probability= (e-15 *(15)0) / 0!
= e-15 “

“From the given question, → The symbol ∃ is call the existential quantifier and represents the phrase “there exists” or “for some”. The existential quantification of P(x) is the statement “P(x) for some values x in the universe”, or equivalently, “There exists a value for x such that P(x) is true”, which is written ∃xP(x). So the statement ∃!xP(x) → ∃xP(x) is true.
→ If P(x) is true for at least one element in the domain, then ∃xP(x) is true. Otherwise it is false.
→ Accordingly DeMorgan’s laws for quantifiers:the following statements are true.
¬∀xP(x) ≡ ∃x¬P(x)
¬∃xP(x) ≡ ∀x¬P(x) then the statement is ∃!x ⌐P(x) →⌐∀xP(x) is true. “

“From the question, the propositions consists of exactly two of the variables should true and final proposition should be true.
Only option C consists of exactly two of the variables are true and all remaining variables deviating this rule.
In this proposition, (p ∧ q ∧⌐ r) ∨ ( p ∧ ⌐q ∧ r) ∨ (⌐ p ∧ q ∧ r)
(p ∧ q ∧⌐ r) → p and q are true
( p ∧ ⌐q ∧ r) → p and r are true
(⌐ p ∧ q ∧ r) → q and r are true
Finally the proposition consists of “V” operation , so the entire proposition is true. “

“The relation “divides” on a set of positive integers is Anti symmetric and Transitive.
Proof:
Let assume a,b two set elements.
The relation is antisymmetric if and only if for every a,b in the set.
IF(a∣b AND b∣a), then it must follow that a=b.
→ If it’s FALSE then both a∣b AND b∣a, then it’s perfectly consistent to have a≠b.
→ The only time a∣b AND b∣a is exactly when a=b, since then we have a∣b ⟺ a∣a is TRUE for all a.
Hence the relation is antisymmetric. “

“Cyclomatic complexity uses 3 formulas:
1. The number of regions corresponds to the cyclomatic complexity
2. V(G),Flow graph is defined as V(G)=E-N+2 where E is the number of flow graph edges, and N is the number of flow graph nodes.
3. V(G),Flow graph is defined as V(G)=P+1 where p is the number of predicate nodes contained in the flow graph G. “

Draw the truth table and A is the answer. Its a very simple question.

“Identical digits means similar(same) digits.
Any integer composed of 3n identical digits.
For example n=1, 3n= 31=3 which means three identical digits (111,222,333,444 and so on)
n=2, 32 =9 which means nine identical digits (111111111, 222222222 and so on)
The above numbers are is divisible by 3
111 is divisible by 3.
222, 333 and 444 are multiple of 3 “

“Probability of getting a number = 1/10
Probability of not getting a number = 1- 1/(10) = 9/10
Now probability that correct number is chosen in first chance= 1/10
probability that correct number is chosen in second chance= (9/10)* (1/10)
probability that correct number is chosen in first chance= (9/10)* (9/10) *(1/10)
So total probability = (1/10)+ [(9/10)* (1/10) ]+ [(9/10)* (9/10) *(1/10)]
= (1/10)+(9/100)+(81/1000)
= 271/1000, Hence none of the above “

Draw the truth table

“Given data,
— Hash table has space =75 slots.
— For 6% filling it must take =6 slots.
— Probability of no collision for first 6 entries=?
Step-1: According to given data,
= (75P6) / (756)
= 0.814586387
Step-2: We have to find at least one collision occurs in 6 entries
=1-Probability of no collision for first 6 entries
= 1-0.814586387
= 0.185413613 , Hence none of the above “

The set of vertices has size n, the number of such subsets is given by the binomial coefficient C(n,2)⋅C(n,2) = n(n-1)/2

“→ The 4-colour theorem of the planar graph describes that any planar can at most be colored with 4 colors.
→ The sufficient number of colors in worst case is 4 colors for any planar graph. “

“An equivalence relation is a binary relation that is reflexive, symmetric and transitive.
The relation “”is equal to”” is the canonical example of an equivalence relation, where for any objects a, b, and c:
a = a (reflexive property),
if a = b then b = a (symmetric property), and
if a = b and b = c then a = c (transitive property)
“

“→ A relation on a set A is called an equivalence relation if it is reflexive, symmetric, and transitive.
1. Reflexivity: f(x) = f(x)
True, as given the same input, a function always produces the same output
2. Symmetry: if f(x) = f(y) then f(y) = f(x)
True, by the definition of equality
3.Transitivity: if f(x) = f(y) and f(y) = f(z) then f(x) = f(z)
True, by the definition of equality
Option-2: { (0,0), (1,1), (2,2), (3,3) }
Has all the properties, thus, is an equivalence relation
Option-1: { (0,0), (0,2), (2,0), (2,2), (2,3), (3,2), (3,3) }
Not reflexive: (1,1) is missing
Not transitive: (0,2) and (2,3) are in the relation, but not (0,3)
Option-3: { (0,0), (0,1) (0,2), (1,0), (1,1), (1,2), (2,0), (2,2), (3,3) }
Not symmetric: (1,2) is present, but not (2,1)
Not transitive: (2,0) and (0,1) are in the relation, but not (2,1)
Option-4: Similarly, option-4 also not TRUE “

Here, number of models is nothing but number of TRUEs in final statement. Draw the truth table and count the “True” values in final output

“Given f(x) = x​ 4​ , g(x) = √ x 2 + 1 , h(x) = x​ 2​ + 72
for, ho(gof)
gof=g(f(x))
=g(x​ 4​ )
=√(x​ 8​ +1)
ho(gof)=h(gof)
=h(√(x​ 8​ +1))
=(√(x​ 8​ +1)​ 2​ +72
=x​ 8​ +1+72
=x​ 8​ +73
√ x 2 + 1 , h(x) = x​ 2​ + 72
for, (hog)of,
hog=h(g(x))
=h(√(x​ 2​ +1)
=(√(x​ 2​ +1)​ 2​ +72
=x​ 2​ + 1+72
=x​ 2​ +73
(hog)of=(hog)(f(x))
=(hog)(x​ 4​ )
=(x​ 4​ )​ 2​ +73
=x​ 8​ +73

“Probability that the value k=1 appears in the printout at least once is
1-p(x=0)
We will apply the formula of binomial distribution
1-(​ 1000000​ C​ 0​ (1/1000000)​ 0​ * (999999/1000000)​ 10^6​ )
=1-(1*1*0.367879)
=0.632121 “

“Option-A: It is not complete graph because it won’t have n(n-1)/2 edges.
Option-B: It is not Bipartite Graph because it takes more than 2 colours. Bipartite Graph have exactly 2 colours.
Option-C: Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. “

“Here, they are clearly mentioned that “certain tree”
The tree contain maximum n-1 edges. Here, ‘n’ is number of vertices.
→ According to the handshaking lemma “sum of degrees of all vertices=2|e|”.
→ Two vertices of degree 4, we can write into (2*4)
→ One vertex of degree 3, we can write into (1*3)
→ One vertex of degree 2, we can write into (1*2).
→ Other vertices(X) have degree 1, we can write into (X*1)
Step-1: (2*4)+(1*3)+(1*2)+(X*1)
=2(X+4-1) [Note: ‘X’ value is not given ]
X=7
Step-2: To find total number of vertices, we are adding X+4 because they already given 4 vertices.
=X+4
=7+4
=11 “

“The above problem is in the form of (AUB) = (A)+(B)-(A∩B)
A=1000/3
B=1000/5
(A∩B)=66
(AUB)=467 “

“→ A function f : X → Y is defined to be one-one (or injective), if the images of distinct elements of X under f are distinct, i.e., x1 , x2 ∈ X, f(x1) = f(x2) ⇒ x1=x2.
→ The possible value of “x” is 0 then
f(x1)=x1/2=0/2=0
f(x2)=x2/2=0/2=0
for x1 , x2 ∈ X, f(x1) = f(x2) ⇒ x1 = x2. “

If a graph is complete, total number of spanning trees are N​ N-2

“→ For any given numbers a and b which belongs to natural numbers , the options (A) and (D) are false
→ The set of natural numbers, denoted N, can be defined in the following ways: N = {0, 1, 2, 3, …}
→ A prime number (or a prime) is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers.
→ ‘a-b’ may be gives the non negative values which is not prime number but the a+b may give the prime value. “

“→ There are 10 pair of shoes available in the dark room which means 20 individual shoes are available in the room.
→ If you pick shoes from one to ten individual shoes, there may be chance of getting same individual shoes.
→ There is no guarantee that getting one proper pair from 10 individual shoes.
→ If You pick 11 shoes, then there may chance of 10 individual shoes of same type and one individual shoe of another type. So we will get at least one proper pair shoe from 11 individual shoes. “

“A relation R is an equivalence relation if and only if it is reflexive, symmetric, and transitive.
1. The relation is reflexive: x mod 3 = x mod 3
2. The relation is symmetric: if x mod 3 = y mod 3, then y mod 3 = x mod 3
3. The relation is transitive: if x mod 3 = y mod 3, and y mod 3 = z mod 3, then x mod 3 = z mod 3 “