In the class, 20 students have Lenovo laptops, 15 students have Sony laptops and 8 students have both Lenovo and Sony laptops. How many students are there in the class?

Construct a truth table for each of these compound propositions. i) (p  q)  q ii) (p  q)  (p  q)

Use mathematical induction to show that : n3 + 2n is divisible by 3 for all n > = 1

How many different license plates are available if each plate contains a sequence of 3 letters followed by 4 even digits (0, 2, 4, 6, 8) where 0 cannot be taken as 1st digit?

A = {x : x is a natural number less than or equal to 10 and divisible by 2} and B = {x : x is an odd natural number less than or equal to 10} Find i) A – B ii) B – A iii) is A – B = B – A?

What is CNF? Convert p  q into CNF.

In a country club, 60% of women play tennis, 40% play golf, and 20% play both. A woman is chosen at random. Given that she plays tennis, what is the probability that she plays golf?

A committee of 5 people is to be formed from a group of 4 men and 7 women. How many possible committees can be formed if at least 3 women are on the committee?

A man is informed that when a pair of dice were rolled, the result was seven. How much information is there in this message?

A box contain 6 white balls and 5 black balls find the number of ways 4 balls can be drawn from the box if i) Two must be white ii) All of them must have same color

Consider the experiment of tossing a coin three times. What is the probability of getting exactly two tails?

In how many ways can the letters of the word PERMUTATIONS be arranged if the vowels are all together?

Write the contrapositive, the converse, inverse of the following sentence. “If today is Easter, then tomorrow is Monday”.

Show that (3 1) 1 4 7 ...... (3 2) 2 n n n        by Mathematical Induction.

In a survey of 60 people, it was found that, 25 read Business India 26 read India Today 26 read Times of India 11 read both Business India and India Today 9 read both Business India and Times of India 8 read both India Today and Times of India 8 read none of these i) How many read all three? ii) How many read exactly one?

Show that (A – B) – C = A – (B U C) using Venn Diagram.

Prove by truth table : i) ( ) [~ ( )] p q p q    ii) [( ) ( )] ( ) p q q r p r     

Determine the validity of the argument. S1 : If I like discreate mathematics then I will Study. S2 : Either I will study or I will fail. S : If I fail then I do not like discreate mathematics

Find the number of permutations that can be made out of the letters i) COMPUTER ii) ASSASSINATION

Out of 5 males and 6 females, a committee of 5 is to be formed. Find the number of ways in which it can be formed so that among the person chosen in the committee there are, i) Exactly a male and 2 female ii) At least 2 male and 1 female

A single card is drawn from an ordinary deck of 52 cards. Find the probability p that : i) The card is a face card ii) The card is face card and heart iii) The card is face card or heart

In how many ways can 6 men and 5 women be seated in a line so that no two women sit together?

In a group of 6 boys and 4 girls, four children are to be selected. In how many ways can they be selected such that at least one boy should be there.

A bag contains 5 red, 4 white and 8 blue balls. 4 balls are drawn at random. What is the probability that there is at least one ball of each color?

What is Isomorphism in the graph? Explain the rules for graph to be isomorphic with an example.

Construct an optimal tree for the weights 5,7,10,15,35,40. Find the weight of the optimal tree.

Find the fundamental cutset and fundamental circuit for the spanning graph with vertices v4, v2, v1, v3, v5

Explain chromatic numbers with respect to the following graphs i) Complete Graph ii) Star Graph iii) Wheel Graph

Find the maximum flow in the given network

What number of edges are present in a complete graph with n vertices? Explain with the help of a handshaking lemma.

Consider the following relations on {1, 2, 3, 4} : R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}, R2 = {(1, 1), (1, 2), (2, 1)}, R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}, R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}, R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}, R6 = {(3, 4)}. Which of these relations are reflexive?

Use Warshall’s algorithm to find the transitive closure R* of the following relation R on the set A = {1, 2, 3, 4}, where R = {(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (3, 4), (3, 2), (4, 2), (4, 3)}

Show that if seven numbers from 1 to 12 are chosen then two of them will add up to 13.

Consider these relations on the set of integers : R1 = {(a, b) | a < b}, R2 = {(a, b) | a > b}, R3 = {(a, b) | a = b or a = –b}, R4 = {(a, b) | a = b}, R5 = {(a, b) | a = b + 1}, R6 = {(a, b) | a + b < 3} Which of these relations contain each of the pairs (1, 1), (1, 2), (2, 1), (1, –1), and (2, 2)?

Let A = {a1, a2, a3} and B = {b1, b2, b3, b4, b5}. Which ordered pairs are in the relation R and R–1 represented by the matrix?

Show that 7 colors are used to paint 50 bicycles, then at least 8 bicycles of the same color.

Determine quotient and remainder for the following : i) 88 / 10 ii) –88 / 10

State and explain the Euclidean algorithm to computer GCD of two numbers.

Let a = 37 and b = 249. Find i) d = gcd(a, b) ii) Find integers m and n such that d = ma + nb

Find the multiplicative inverse of 40 mod 197 using the Extended Euclidean algorithm.

Using the primality test theorem determine if the following numbers are prime. Justify your answer : i) 131 ii) 253

Using the Chinese Remainder Theorem find the value of X such that : X = 2 mod 3 X = 4 mod 5 X = 3 mod 7

Let R = {0º, 45º, 90º, 135º, 180º, 225º, 270º, 315º} and * = binary operation, so that a*b is overall angular rotation corresponding to successive rotations by a and then by b. Show that (R,*) is a group.

Consider the (2, 6) encoding function e. e(00) = 10111100, e(10) = 10101010 e(01) =00111010, e(11) = 10101101 Find the minimum distance of e. How many errors will e detect?

Define Ring with Unity, with an example.

Prove that the following table on relation of elements of set G = {0,1,2,3,4,5} multiplication mod 6 is not a group.

S = {1,2,3,6,12,28}, where a*b is defined as GCD (a,b). Determine whether it is an Abelian Group or not.

Define Commutative Ring, with an example.

What is a planar graph? Suppose that a connected planar graph has 30 edges. If a planar representation of this graph divides the plane into 20 regions, how many vertices does this graph have?

Build a minimum spanning tree for the following graph using Kruskal’s algorithm.

Define Prefix Code. Which of the following codes are prefix codes? Justify your answer. i) a: 0, e: 1, t: 01, s: 001 ii) a: 101, e: 11, t: 001, s: 011, n: 010

Determine whether the following graphs are isomorphic to each other. Justify your answer.

Using the labeling procedure, find the maximum flow in the following transport network.

Use the nearest Neighborhood method to solve the Traveling Salesperson problem starting with vertex a. Find the cost of the tour.

Consider these relations on the set of integers : R 1 = {(a, b) | a < b}, R 2 = {(a, b) | a > b}, R 3 = {(a, b) | a = b} R 4 = {(a, b) | a = 1 + b} R 5 = {(a, b) | a = b or a = –b}, R 6 = {(a, b) | a + b < 3) Which of these relations contain each of the pairs (1, 1), (1, 2), (2, 1), (1, –1) and (2, 2)?

Solve the following recurrence relation. an = an–1 + 2.an–2 where a0 = 2, a1 = 7

What is the minimum number of students required in a discrete mathematics class to be sure that at least six will receive the same grade, if there are five possible grades, A, B, C, D, and F?

Explain the injective function with an example? Determine whether each of these functions is an injection from R to R. i) f(x) = 2x + 1 ii) f(x) = x2 +1 iii) f(x) = x3 iv) f(x) = (x2 +1)/(x2 + 2)

What is POSET? Let A is set of factors of positive integer m and relation is divisibility on A. i.e. R = { (x, y) | x, y  A, x divides y } For m = 30. Draw Hasse Diagram.

Find the transitive closure by using Warshall’s algorithm for the given relation as: R = {(2, l), (2, 3), (3, 1), (3, 4), (4, 1), (4, 3)}

Using Binary expansion method solve the following (Show step-wise answer) 761 mod 15.

Which of the following is true? Justify your answer. i) 556  1296 (mod 25) ii) 1655  935 (mod 23) iii) 448  788 (mod 10)

Using Chinese Remainder Theorem, find the value of p using following data P  2 (mod 11) P  3 (mod 7)

What is a Mersenne prime number? Which of the following is the Mersenne Prime number? 71, 31, 255, 63, 7 Justify your answer.

Find the Euler’s totient function of the following numbers : i) 47 ii) 45 iii) 65

Find the multiplicative inverse of 1234 mod 4321 using Extended Euclidean Algorithm.

Consider the set A={1, 3, 5, 7, 9, .........} i.e. a set of odd positive integers. Determine whether A is closed under: i) a*b = a + 3b ii) a*b = (a–b) / 2. iii) a*b=max(a, b) iv) a*b=power (a, b) v) a*b = 2a–b vi) a*b=GCD(a, b)

Show that (Z6, +) is an Abelian Group.

Prove that Hamming Distance d(x,y)=d(y,x).

Show that G = {1, w, w2} is an abelian group under multiplication where w is the cube root of unity.

Explain Integral Domain with an example.

Consider the (2,6) encoding function e. e(00)=110000, e(10)=101000 e(01)=011110, e(11)=111001 Find the minimum distance of e.