IGNOU MCS-212 - Discrete Mathematics

Q1: Use Mathematical Induction to prove that: 12 + 22 + ……..+ n2 = n(n+1)(2n+1)/6 Q2: How many different permutations arepossible of the letters, taken all at a time, of the word: ASSESSES? Q3: A die is rolled once. What are the probabilities of the following events: a. Getting an odd number b. Getting at least a value 2 c. Getting at most a value 2 d. Getting at least 7 Q4: Draw a hypercube graph Q3 (also called the cubical hypercube). Check whether the hypercube Q3 is Hamiltonian Q5: What is isomorphism? Find, if the following graphs G1 and G2 are isomorphic or not. Explain how you arrived at your answer. Q6: What is a finite automata? Why is it needed? How is a finite automata represented? Also explain the term regular expression with the help of an example. Q7: Differentiate between a. Deterministic and Non-deterministic finite automata b. Deterministic and Non-deterministic Turing Machine c. Moore and Mealy Machine Q8: Describe the divide-and-conquer approach to solve recurrences? Explain how this approach can be used to apply binary search in a sorted list. Q9: What is proposition? Explain with the help of an example. Explain Disjunction and Conjunction with the help of truth table for each. Q10: Prove the following theorem by direct proof method: ‘‘The square of an even integer is an even integer.’’ Q11: Given the Boolean expression (a′ ∨ (b ∧ c′)) ∨ (b ∨ d′),draw the corresponding circuit, where a, b, c and d are the inputs to the circuitry. Q12: Define the terms Domain, Co-domain and Range in the context of a function. Also find the domain, co-domain and range for a function A to B, where A = {1,2,3,4} and B = {1,4,9,16,25}. Q13: A committee consisting of 2 male and2 female workers is to be constituted from 8 male and 9 female workers. In how many distinct ways can this be done? Q14: In a tennis tournament, each entrant plays a match in the first round. Next, all winners from the first round play a second-round match. Winners continue to move on to the next round, until finally only one player is left as the tournament winner. Assuming that tournaments always involve n = 2k players, for some k, find the recurrence relation for the number rounds in a tournaments of n players. 15: Show, using the pigeonhole principle, that in any group of 30 people, 5 people can always be found who were born on the same day of the week. Q16: Define the following in the context of graph, with the help of an example: a. Complete graph b. Degree of a vertex c. Cycle d. Path e. Circuit Q17: What is a bipartite graph ? Explain with the help of an example. Give one or two applications of bipartite graphs. Q18: How Hamiltonian graphs differ from the Eulerian graphs? Give Dirac’s and Ore’s criterion for the Hamiltonian graphs. Q19: Differentiate between Eulerian graph and Eulerian circuit. Find the Eulerian circuit in the graph given below(if it exists). Q20: Write Short notes on following a. Travelling Salesman Problem b. Vertex Coloring c. Edge Coloring d. Planar graphs e. Pascal’s Formula

Q1: Attempt the following, all questions are compulsory, and each question carries 2 marks for each a) Prove by mathematical induction that b) Verify whether √11 is rational or irrational. c) What are Demorgan’s Law? Explain the use of Demorgen’s law with example. d) Make truth table for followings: e) Obtain the truth value of disjunction of “ Water is essential for life” and “2+2=4”. f) Write the following statements in the symbolic form. i) Some students can not appear in exam. ii) Everyone cannot sing. g) Draw logic circuit for the following Boolean Expression: (x y z) + (x+y+z)'+(x'zy' ) h) What is dual of a boolean expression? Explain with the help of an example. i) Show using truth table whether (P ∧ Q ∨ R) and (P ∨ R) ∧ (Q ∨ R) are equivalent or not. j) Explain whether (P ∧ Q) → (Q → R) is a tautology or not. Q2: Attempt the following, all questions are compulsory, and each question carries 2 marks for each a) Set A,B and C are: A = {1, 2, 3,5, 7, 9 11,13}, B = { 1,2, 3 ,4, 5,6, 7,8,9 } and C { 1,2 ,4,5,6,7,8,10,13}. b) What is power set? Write power set of set A={1,2,3,4,5,6,7,9}. c) Give geometric representation for followings: i) { -3} x R ii) {1, -2) x ( 2, -3) d) What is proper subset? Explain with the help of example. e) What is relation? Explain properties of relations with example. f) Explain whether function: f(x) = x2 posses an inverse function or not. g) Write the finite automata corresponding to the regular expression (a + b)*ab h) If L1 and L2 are context free languages then, prove that L1 U L2 is a context free language. i) Explain Decidable and Undecidable Problems. Give example for each. j) What is equivalence relation? Explain use of equivalence relation with the help of an example. Q3: Attempt the following, all questions are compulsory, and each question carries 2 marks for each a) Suppose we want to choose two persons from a party consisting of 35 members as Manager and Assistant Manager. In how many ways can this be done? b) There are three Companies, C1, C2 and C3. The party C1 has 4 members, C2 has 5 members and C3 has 6 members in an assembly. Suppose we want to select two persons, both from the same Company, to become president and vice president. In how many ways can this be done? c) Suppose there are five married couples and they (10 people) are made to sit about a round table so that neither two men nor two women sit together. Find the number of such circular arrangements. d) How many words can be formed using letter of DEPARTMENT using each letter at most once? i) If each letter must be used, ii) If some or all the letters may be omitted. e) What is the probability that a 13-card hand has at least one card in each suit? f) What is the probability that a number between 1 and 10,000 is divisible by neither 2, 3, 5 nor 7? g) Explain inclusion-exclusion principle and Pigeon Hole Principle with example. h) In a tennis tournament, each entrant plays a match in the first round. Next, all winners from the first round play a second-round match. Winners continue to move on to the next round, until finally only one player is left as the tournament winner. Assuming that tournaments always involve n = 2k players, for some k, find the recurrence relation for the number rounds in a tournaments of n players. i) Find an explicit recurrence relation for minimum number of moves in which the n-disks in tower of Hanoi puzzle can be solved! Also solve the obtained recurrence relation through an iterative method. j) Find the solution of the recurrences relation an = an-1 + 2an-1, n > 2 with a0 = 0, a1=1 Q4: Attempt the following, all questions are compulsory, and each question carries 2 marks for each a) Draw 2-isomorphic graphs and 3 non- isomorphic graphs on five vertices. b) Prove that the complement of c) Draw the following graphs and state which of following graph is a regular graph? (i)C5 (ii) W5 (iii) Q4 (iv) K5,5 d) What is a chromatic number of a graph? What is a chromatic number of the following graph? e) Determine whether the above graph has a Hamiltonian circuit. If it has, find such a circuit. If it does not have, justify it f) Explain and prove the Handshaking Theorem, with suitable example g) Show that C6 is bipartite and K3 is not bipartite. h) Explain the terms PATH, CIRCUIT and CYCLES in context of Graphs. i) What is the difference between an Eulerian graph and an Eulerian circuit? j) Explain the Dirac’s Criterion and Ore’s Criterion for Hamiltonian graphs