IGNOU MCA Discrete Mathematics Previous Years Unsolved Papers MCS 212 E-Book

Manish Soni

• Herausgeber: Poorav Publications
• Kategorie: Wissenschaft und neue Technologien
• Serie: IGNOU MCA Unsolved Books Series
• Sprache: Englisch

Seitenzahl: 123

Veröffentlichungsjahr: 2024

Beschreibung

Welcome to Discrete Mathematics: Theory, Problems, and Solutions, a comprehensive resource designed to enhance your understanding of this fundamental area of mathematics. This book is specifically tailored for students, educators, and enthusiasts seeking to deepen their grasp of discrete mathematics through the lens of unsolved and challenging questions.
This book seeks to bridge that gap. By presenting a collection of IGNOU-MCS 212 PREVIOUSLY UNSOLVED QUESTION PAPERS(MCA-NEW), we provide a unique opportunity to engage with the material in a new and dynamic way. Each question is carefully selected to challenge and provoke thought, encouraging a deeper exploration of the subject matter.
Our goal is not only to present problems but to foster a deeper appreciation for the beauty and utility of discrete mathematics. We hope that by working through these questions, you will develop a stronger intuition for the subject and acquire problem-solving skills that will serve you well in both academic and professional contexts.
We extend our heartfelt gratitude to the numerous educators and students who have contributed to the evolution of this book. Their insights and feedback have been invaluable in shaping its content. We also acknowledge the efforts of the authors and researchers whose work has inspired the selection of these problems.
As you embark on this journey through the pages of Discrete Mathematics: Theory, Problems, and Solutions, we encourage you to approach each problem with curiosity and determination. Embrace the challenge, and allow the process of solving these questions to deepen your understanding and appreciation of discrete mathematics.
May this book serve as a valuable tool in your educational endeavors and inspire a lifelong interest in the fascinating world of discrete mathematics.

Leseprobe

IGNOU MCA Discrete Mathematics Previous Years Unsolved Papers MCS 212

Manish Soni

Preface

Welcome toDiscrete Mathematics: Theory, Problems, and Solutions, a comprehensive resource designed to enhance your understanding of this fundamental area of mathematics. This book is specifically tailored for students, educators, and enthusiasts seeking to deepen their grasp of discrete mathematics through the lens of unsolved and challenging questions.

This book seeks to bridge that gap. By presenting a collection of IGNOU-MCS 212 PREVIOUSLY UNSOLVED QUESTION PAPERS(MCA-NEW), we provide a unique opportunity to engage with the material in a new and dynamic way. Each question is carefully selected to challenge and provoke thought, encouraging a deeper exploration of the subject matter.

Our goal is not only to present problems but to foster a deeper appreciation for the beauty and utility of discrete mathematics. We hope that by working through these questions, you will develop a stronger intuition for the subject and acquire problem-solving skills that will serve you well in both academic and professional contexts.

We extend our heartfelt gratitude to the numerous educators and students who have contributed to the evolution of this book. Their insights and feedback have been invaluable in shaping its content. We also acknowledge the efforts of the authors and researchers whose work has inspired the selection of these problems.

As you embark on this journey through the pages of Discrete Mathematics: Theory, Problems, and Solutions, we encourage you to approach each problem with curiosity and determination. Embrace the challenge, and allow the process of solving these questions to deepen your understanding and appreciation of discrete mathematics.

May this book serve as a valuable tool in your educational endeavors and inspire a lifelong interest in the fascinating world of discrete mathematics.

Table of Contents

Chapter 1: Term-End Examination, December 2021

Chapter 2: Term-End Examination, June 2022

Chapter 3: Term-End Examination, December 2022

Chapter 4: Term-End Examination, June 2023

Chapter 5: Term-End Examination, December 2023

Chapter 6: Most Asked Questions Part-A

Chapter 7: Most Asked Questions Part-B

Master Of Computer Applications (MCA)

Chapter 1: Term-End Examination, December 2021

MCS-212: Discrete Mathematics

Time: 3 Hours

Maximum Marks: 100

Note: Question No. 1 is compulsory and carries 40 marks.

Attempt any three questions from the rest four questions (Question Nos. 2 to 5).

1. (a) Make the truth table for:5 (i) (ii) r

(b) Show that is irrational using the proof by contradiction. 5

(c) If A={a,b,c} and B={x,y,z} find: (i) A×B 2 (ii) A×A 2

(iii) A×ϕ1

(d) Find the regular expression for the language: L={aa,aba,abba,abbba,....} 3

(e) Give one difference between Deterministic Finite Automata and

Non-deterministic Finite Automata. 2

(f) Find the order and degree of the following recurrence relations:3 (i) (ii)

(g) Determine the number of integer solutions of the equation:4

where

(h) How many three-letter words, which have a vowel in the middle position, can be formed using

the letters of the English alphabet? 3

(i) Consider graph on four vertices a, b, c, d. Make three sub-graphs of graph G. 3

(j) Show that is a bipartite graph. 3

(k) Does the following graph have an Eulerian circuit? If yes, give the Eulerian circuit;

if no, explain the reasons.4

2. (a) What is a tautology? Find, if the following is a tautology:5

(b) Explain how the principle of mathematical induction can be used to prove:8

(c) Find the Boolean expression for the output of the given logic circuit. 3

(d) Find if the following Boolean expressions are equivalent over the two-element

Boolean algebra B={0,1}: and 4

3. (a) Find the power set of the set A={a,b,c,d}. 3

(b) If A={1,2,3,4}and B={2,3,4,5,6,7} and is defined by , then find the

domain and range of f. 4

(c) If and , then find and .4

(d) Explain the meaning of each symbol in the finite automata definition 3

(e) Consider the following finite automata:

(i) What would be the values of for the automata given above? 3

(ii) Give one string that will be accepted and one string that will not be accepted by this finite automata. 3

4. (a) If there are 7 men and 5 women, how many circular arrangements are possible in which

women do not sit adjacent to each other? 5

(b) What is the probability that a number between 1 to 1,000 is divisible by neither 2, nor 3, nor 5? 5

(c) What is the meaning of ‘distributions’ of objects? Explain with the help of an example. 5

(d) Explain the Fibonacci numbers. Also, explain the recurrence relation for Fibonacci numbers. 5

5. (a) Define the following terms in the context of a graph, with the help of an example: (i) Digraph 2

(ii) Complete graph of three vertices 2 (iii) Degree of a vertex 2 (iv) A regular graph 2

(b) Explain the terms tree and forest in the context of graphs, with the help of an example. 5

(c) What are Hamiltonian graphs? Explain with the help of an example. 5

(d) State the travelling salesperson problem. 2

Master Of Computer Applications (MCA)

Chapter 2: Term-End Examination, June 2022

MCS-212: Discrete Mathematics

Time: 3 Hours

Maximum Marks: 100

Note: Question No. 1 is compulsory and carries 40 marks.

Attempt any three questions from Questions No. 2 to 5.

1. (a) Write the mathematical notation for the following:4 (i) The set of all odd numbers (ii) The set of all natural numbers whose square is more than 26.

(b) Assuming that p and q are two propositions, find if the following two statements are logically

equivalent or not by constructing the truth table:5

(c) Use the principle of mathematical induction to prove that:

for each n ∈ N.5

(d) Define the term "regular expression" with the help of an example. 5

(e) How many different permutations are possible of the letters, taken all at a time, of the word:

ASSESSES? 3

(f) A die is rolled once. What are the probabilities of the following events:4(i) Getting an odd number. (ii) Getting at least a value of 2. (iii) Getting at most a value of 2. (iv) Getting at least 7.

(g) Define the problem of the Tower of Hanoi. Explain the recurrence relation to solve this problem. 6

(h) Draw a hypercube graph (also called the cubical hypercube). 3

(i) Find if the following graphs are isomorphic or not. 5

Explain how you arrived at your answer.

2. (a) Define the degree and order of a recurrence relation. Find the degree and order of the

following recurrence relations:

(i) (ii) 3

(b) What is finite automata? Why is it needed? How is finite automata represented?

Explain with the help of an example. 8

(c) What is the divide-and-conquer approach? Explain how this approach can be used to

apply binary search in a sorted list. 6

3. (a) What is a proposition? Explain with the help of an example. Explain Disjunction and

Conjunction with the help of truth tables for each. 6

(b) Prove the following theorem by direct proof method: “The square of an even integer is an even integer.” 6

(c) Given the Boolean expression:8 draw the corresponding circuit, where a,b,c and d are the inputs to the circuitry.

4. (a) Show the intersection and difference operations on two sets using Venn diagrams.4

(b) 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 from set A to set B,

where A={1,2,3,4} and B={1,4,9,16,25}6

(c) A committee consisting of 2 male and 2 female workers is to be constituted from 8 male

and 9 female workers. In how many distinct ways can this be done? 4

(d) 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. 3

(e) Find how many four-digit numbers are even. 3

5. (a) Define the following in the context of graphs, with the help of an example:6(i) Complete graph (2 marks)(ii) Star topology (2 marks)(iii) Degree of a vertex (2 marks)

(b) Find the complement of the following graph:5

(c) What is a bipartite graph? Explain with the help of an example.4(d) Differentiate between Eulerian graph and Eulerian circuit. Find the Eulerian circuit in the

following graph, if it exists.5

Master Of Computer Applications (MCA)

Chapter 3: Term-End Examination, December 2022

MCS-212: Discrete Mathematics

Time: 3 Hours

Maximum Marks: 100

Note: Question No. 1 is compulsory

Attempt any three questions from Questions No. 2 to 5.

1. (a) Differentiate between predicate and proposition. Also, write De Morgan’s laws for both. 5

(b) Use De Morgan’s law to derive an AND gate from a NOR gate. 5

(c) Explain the conditions for a relation to be an equivalence relation. 5

(d) Prove that , where S is a set of strings. 5

(e) Briefly discuss a non-deterministic Turing machine. 5

(f) What is the addition principle? Use the addition principle to solve the following case: "Say there are three political parties having 4, 5, and 6 members respectively." In how many ways can we select two persons from the same party to become President

and Vice President? 5

(g) What is a power set? Find the power set for the following given sets: (i) A={0,1,3,5} (ii) B={ϕ,A,B,C,E} 5

(h) Briefly discuss the Pigeonhole principle with a suitable example. 5

2. (a) Using induction, verify: 5

(b) Define “Stirling number of the second kind.” Calculate5

(c) Explain the Handshaking theorem with a suitable example. 5

(d) What is a spanning tree? Can we have a unique spanning tree?

Draw three spanning trees for the graph given below:5

3. (a) For any two propositions x and y, verify that:

5

(b) Find the number of three-letter words that can be formed using the letters of the

English alphabet. How many of them end in ‘x’? How many of them have a vowel in

the middle position? 7

(c) What is a regular expression? Find a regular expression to describe

each of the following languages:2+3+3(i) {a,b,c}(ii) {λ,a,abb,abbbb,…}

4. (a) Differentiate between the following:(i) Deterministic finite automata and Non-deterministic finite automata 5(ii) Moore machines and Mealy machines 5

(b) Briefly discuss the Halting problem. 5

(c) A box contains 3 red, 3 blue, and 4 white balls. In how many ways can 8 balls be

drawn out of the box, one at a time provided order is important? 5

5. (a) Determine the recurrence relation and iterative relation for the power set of a set ‘S’. 10

(b) Write short notes on the following:2*5=10(i) Path in a graph (ii) Circuits in a graph (iii) Cycles in a graph (iv) Degree of a vertex

(v) Regularity of graph

Master Of Computer Applications (MCA)

Chapter 4: Term-End Examination, June 2023

MCS-212: Discrete Mathematics

Time: 3 Hours

Maximum Marks: 100

Note: Question No. 1 is compulsory

Attempt any three questions from Questions No. 2 to 5.

1. (a) Verify that is a contradiction and is a tautology.5

(b) Reduce the Boolean expression to its simplest form.5

(c) Find the inverse of the function .5

(d) What is Kleene closure? Find Kleene closure for Σ={0,1}.5

(e) What is the multiplication principle? Use it to find the number of ways to choose two persons as President and Vice President from a party of 35 members.5

(f) Briefly discuss the Inclusion-Exclusion principle with a suitable example.5

(g) What is an Eulerian graph? Explain with the help of a suitable diagram.5

(h) What is Tautology? Show that the given expression is a tautology:

5

2. (a) Using induction, show that: 5

(b) In how many ways can 20 employees be assembled into 3 groups?5

(c) Explain isomorphic graphs with a suitable example.5

(d) What are Bipartite graphs? Show that is a Bipartite graph.5

3. (a) Check whether are logically equivalent.5

(b) What is the chromatic number of a graph? Draw a graph with chromatic number 5.5

(c) Write short notes on the following:(i) Hamiltonian Graph(ii) Vertex Cover Problem10

4. (a) Show that the number of words of length ‘n’ on an alphabet for ‘m’ letters is 5

(b) Construct the logic circuit and truth table for the given expression:5 + 5

(c) Given two switches, a battery, and a bulb, design the Boolean circuit for AND gate .

and OR gate.5

5. (a) Briefly discuss the following with suitable examples for each: (i) Finite Automata (ii) Regular expression5

(b) Differentiate between Turing Acceptable Language and Turing Decidable Language.5

(c) If is the number of comparisons required to sort a list of n integers,

determine the recurrence relation and iterative relation for 10

Master Of Computer Applications (MCA)

Chapter 5: Term-End Examination, December 2023

MCS-212: Discrete Mathematics

Time: 3 Hours

Maximum Marks: 100

Note: Question No. 1 is compulsory

Attempt any three questions from Questions No. 2 to 5.

1. (a) Apply the precedence rules and write the truth table for the expression:4

(b) Show that is a tautology without using a truth table.4

(c) What is Dynamic Programming? Write four major steps involved in dynamic programming.4

(d) Explain Conjunctive Normal Form (CNF) with a suitable example.4

(e) Find the inverse of the function:4

(f) What is Kleene closure? Write Kleene closure for the following set of alphabets: (i) Σ={aa,b} (ii) Σ={a,ba}4

(g) What is a Turing machine? Discuss the elements of the six-tuple form of the

Turing machine (Half State Version).4

(h) Suppose A and B are mutually exclusive events such that P(A)=0.3

and P(B)=0.4. What is the probability that: (i) A or B occurs (ii) Either A or B does not occur4

(i) State Pigeonhole principle and Inclusion-Exclusion principle.4

(j) Write and prove the Handshaking theorem.4

2. (a) Write down the statement “If it is raining and the rain implies that no one can go to play the match, then no one can go to play the match” as a compound proposition. Show that this proposition is a tautology by using the principles of logical equivalence.7

(b) Write Floyd Warshall’s algorithm and apply it to find the shortest path for the graph given below (starting from vertex 1):8

(c) Realize Conjunction, Disjunction, and Negation (i.e., AND, OR, and NOT) operations using switches. Also, write the truth table for each.5

3. (a) If A is a set with n elements, then prove that , where P(A) is the power set of A.5

(b) Compare Moore and Mealy machines.5

(c)