Paper 2 CS Discrete Structures and Optimization Part 5

With the help of Pigeonhole principle we can get the solution. The idea is that if you n items and m possible containers. If n > m, then at least one container must have two items in it. So, total 13 minimum number of students.

∀x(P(x)) = ~∃x(~P(x))

“Use the subtraction rule.
1. Number of bit strings of length eight that start with a 1 bit: 27 = 128
2. Number of bit strings of length eight that end with bits 00: 26 = 64
3. Number of bit strings of length eight that start with a 1 bit and end with bits 00: 25 = 32
The number is 128+64+32 = 160 “

“Step-1: There are 4A, 2L, 1H, 1B and 1D.
Step-2: Total number of alphabets! / alphabets are repeating using formula (n!) / (r1! r2!..).
Step-3: Repeating letters are 4A’s and 2L’s
= 9! / (4!2!)
= 7560 “

“Sum of degree of vertices = 2*no. of edges
d*n = 2*|E|
∴ |E| = (d*n)/2 “

“→ To find probability that for the 7th toss head appears exactly 4 times. We have find that past 6 run of tosses.
→ Past 6 tosses, What happen we don’t know. But according to 7th toss, we will find that head appeared for 3 times.
→ Any coin probability of a head=½ and probability of a tail=½
→ If we treat tossing of head as success,then this leads to a case of binomial distribution.
→ According to binomial distribution, the probability that in 6 trials we get 3 success is
6C3*(½)3 *(½)3= 5/16 (3 success in 6 trials can happen in 6C3 ways). → 7th toss, The probability of obtaining a head=1/2
→ In given question is not mention that what happens after 7 tosses.
→ Probability for that for 7th toss head appears exactly 4 times is =(5/16)*(1/2)
=5/32. “

“Euler’s Formula : For any polyhedron that doesn’t intersect itself (Connected Planar Graph), F(faces) + V(vertices) − E(edges) = 2.
Here as given, F=?,V=25 and E=17
→ F+25-17=2
→ 40 “

“To get total number of simple graphs, we have a direct formula is 2(n(n-1)/2).
=26(5)/2
=215 “

A Hasse diagram is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction.

“Lower–Upper (LU) decomposition or factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix. The product sometimes includes a permutation matrix as well. LU decomposition can be viewed as the matrix form of Gaussian elimination. Computers usually solve square systems of linear equations using LU decomposition, and it is also a key step when inverting a matrix or computing the determinant of a matrix.
1. The LU decomposition method fails if any of the diagonal elements of the matrix is zero.
2. The LU decomposition is guaranteed when the coefficient matrix is positive definite. “

“If G1 ≡ G2 then
1. |V(G1)| = |V(G2)|
2. |E(G1)| = |E(G2)|
3. Degree sequences of G1 and G2 are same.
4. If the vertices {V1, V2, … Vk} form a cycle of length K in G1, then the vertices {f(V1), f(V2), … f(Vk)} should form a cycle of length K in G2
→ Graph G and H are having same number of vertices and edges. So, it satisfied first rule.
→ u1 degree 2, u2 degree 3, u3 degree 3, u4 degree 2, u5 degree 3, u6 degree 3.
→ V1 degree 2, V2 degree 3, V3 degree 3, V4 degree 2, V5 degree 3, V6 degree 3.
→ But it violates the property of number of cycles. The number of cycles are not same. “

“Given undirected graph on n=3x vertices (x>=1) with chromatic number 3.
→ Maximum number of edges are=n. “

“M2 is null Matrix
The easiest way we can prove this is by looking at the determinant, since det(AB)=det(A)det(B)
and a matrix A is singular iff det(A)=0 “

“True: Number of vertices of odd degree is always even.
True: Sum of degrees of all the vertices is always even. “

“Let a,b,c be 3 different digits, the sum of the different 2 digit numbers formed with them is
=(a*10+b)+(b*10+a)+(a*10+c)+(c*10+a)+(b*10+c)+(c*10+b)
=2(a+b+c)(10+1)
=22 “

“→ If n ≥ 2 and there are no odd length cycles, Then it is bipartite graph.
→ A bipartite graph has the chromatic number 2.
Eg: Consider a square, which has 4 edges. It can be represented as bipartite ,with chromatic number 2. “

The average rate of convergence of the bisection method is 1/2.

Draw venn diagrams and you will find option 3 is the correct one

“F(x) ⇒ x is my friend
P(x) ⇒ x is perfect
There doesn’t exist any person who is my friend and perfect “

“Definition Given a plane graph G, the dual graph G* is the plane graph whose vtcs are the faces of G.
→ The correspondence between edges of G and those of G* is as follows:
if e∈E(G) lies on the boundaries of faces X and Y, then the endpts of the dual edge e*∈(G*) are the vertices x and y that represent faces X and Y of G. “

“Given data,
8 vertices and distinct cycles length=5
Step-1: To find number of distinct cycles
C(n,r)=C(8,5)
=8! / (5!(8−5)!)
= 56 “

If every minimal cut has an even number of edges, then in particular the degree of each vertex is even. Since the graph is connected, that means it is Eulerian.

“→ First fix one boy and place other 7 in alternative seats so total ways is 7! Because they are seated in circular table. (n-1)!.
→ Now place each girl between a pair of boys. So, total ways of seating arrangement of girls is 8!
→ Finally, 7!8! Possible ways are possible. “

“Prime factorize: 162
⇒162 =2×3×3×3×3 = 33×(2×3)
For (2×3) to be a perfect cube, it should be multiplied by (22×32)
∴ Required number = y = 22×32 = 36 “

The convergence of the bisection method is very slow. Although the error, in general, does not decrease monotonically, the average rate of convergence is 1/2 and so, slightly changing the definition of order of convergence, it is possible to say that the method converges linearly with rate 1/2.

M has n rows. If all the elements of a row are multiplied by , the determinant value becomes 2*5. Multiplying all the n rows by 2, will make the determinant value 2​ n ​ *5=40. Solving n= 3.

“The Rank of a Matrix
→ You can think of an r x c matrix as a set of r row vectors, each having c elements; or you can think of it as a set of c column vectors, each having r elements.
→ The rank of a matrix is defined as (a) the maximum number of linearly independent column vectors in the matrix or (b) the maximum number of linearly independent row vectors in the matrix. Both definitions are equivalent.
For an r x c matrix,
1. If r is less than c, then the maximum rank of the matrix is r.
2. If r is greater than c, then the maximum rank of the matrix is c.
→ The rank of a matrix would be zero only if the matrix had no elements. If a matrix had even one element, its minimum rank would be one. “

“A binary relation R on a set A is a total order on A iff R is a connected partial order on A.
“