Engineering B.E. (Computer Engineering) Sem 3 Discrete Structures and Graph Theory May 2023 DSE Question Paper - Mumbai University | munotes

Questions asked in this paper

1. Q1 Q.1 is compulsory
2. Q2 Solve any 3 questions out of remaining 5 questions
3. Q3 Assumptions made should be clearly stated
4. Q4 Draw the figures wherever required
5. Q1 Solve any four of the following questions
   • a) Check if (p—q)—[(~p—q)—q] is a tautology? 5
   • b) Draw the Hasse diagram for [{2,4,5,8,10,12,20,25}, /]. Is it a Poset? 5
   • c) Define Eulerian and Hamiltonian Graph. Give examples of following type of graph 5
   • i) Eulerian but not Hamiltonian
   • ii) Not Eulerian but Hamiltonan
   • d) Explain types of Quantifiers . Represent the following sentences using Quantifiers 5
6. Q1 All hardworking students are clever
   • ii) There is a student who can speak Hindi but does not know Marathi
   • e) State the Pigeonhole principle and prove that in any set of 29 persons at least five persons must have been born on the same day of the week 5
   • a) Show that the set of all positive rational numbers forms an abelian group 10 under the composition * defined by a*b=(ab)/2
   • a) What is a transitive closure? Explain Warshall's algorithm for finding transitive closure with an example. 10
   • a) By using mathematical induction, prove that the given equation is true for all positive
   • b) Define Lattice? Which of the following is lattice? 8
   • c) Determine the sequence of which recurrence relation 1s ay = — With initial
   • a) Let A={1, 3,6,9,15,18,21} & R be the relation of divisibility. 8
7. Q1 Write the pairs in a relation set R
   • ii) Construct the Hasse diagram What are the Maximal and Minimal elements?
   • iv) Is this poset a distributive lattice? Justify your answer Let H= 1 be a parity check matrix. Determine (3, 6) group code e,, >
   • c) Write a short note on Types of Graphs. 6
   • a) Let(Z,*) be an algebraic structure, where Z is set of integers and the operation * is defined by a*b= maximum of (a,b). Is (Z,*) a Semigroup? Is (z,*) a Monoid? Justify your answer. 8
   • b) Define the term Surjective function. Let E be the set of all even numbers then f: N-->E:f(x)=2x , check if it is surjective ,bijective?Justify your answer. 4
   • c) Give the examples of relation R on S = {a, b, c,d} having stated property. 8
8. Q1 R is an equivalence relation
   • ii) R is symmetric but not transitive
   • iii) R is both symmetric and antisymmetric
   • iv) R is neither symmetric nor antisymmetric
   • a) Define Isomorphic graphs and check whether the following graphs are Isomorphic ? 8
   • b)In a group(G,*) , Prove that the inverse of any element is unique and identity element is also unique. 6
   • c) Define Relation. Let 6 f: ROR is defined as f(x) g: ROR is defined as g(x) h: is defined as h(x) =9x-2

Read from the scan above, so a character or two may differ. The scan is the original.