Engineering BE Computer Engineering Sem 3 May 2024 2024 Discrete Structures & Graph Theory 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) Prove using Mathematical Induction that 5
   • b) Explain the term poset. Consider a set D165. Find the elements of this set & draw the hasse diagram for this poset. 5
   • c) How many strings of length 7 either begin with 2 zeros or end with 3 ones? 5
   • d) Explain the term partition set with suitable example. 5
   • e) State the Pigeonhole principle and show that If there are 10 marbles in the jar & you have a jar filled with red, green, and blue marbles, you'll always have at least two marbles of the same colour. 5
6. Q1 Explain the term group
   • ii) Prepare the composition table for the above set w.r.t. the operation of addition
   • iii) Determine whether it is a group
   • iv)Whether elements of set A are invertible? If yes, then find the inverses of these
   • v) Determine whether it is a cyclic group Let A = a2, a3, a4, as} and let R be a relation on A whose matrix is : 10 Find out transitive closure of R using Warshall’s algorithm
   • a) A large software development company employs 100 computer programmers. Of them, 45 are proficient in Java, 30 in C#, 20 in Python, six in C# and Java, one in Java and Python, five in C# and Python, and just one programmer is proficient in all three languages above Determine the number of computer programmers that are not proficient in any of these three
   • b) Explain the terms Conjunctive & Disjunctive Normal Form with suitable examples. 6 Determine the sequence b, whose recurrence relation is b, = + 1 with initial condition
   • a) What is a lattice? Determine whether following hasse diagram represents a lattice. 6 Consider (3, 8) an encoding function e : B’ + defined as How many errors can ‘e’ detect & correct?
   • c) What are the necessary conditions for the isomorphism between 2 graphs? Determine 8 whether following 2 graphs are isomorphic
   • a) If the addition & multiplication modulo 10 is defined on a set of integers A={0, 2,4, 6, 8}. Then determine whether this algebraic system is a ring. 8 A function f: R > R is defined by 6
   • c) Define the terms Euler path & a circuit . 6 Determine whether following graphs have Euler path or a circuit
   • a) Explain the following terms with suitable example (any 4) 8
   • v) Cartesian product
   • b) Solve the following using the laws of logic 4 is defined by is defined by g (x) = 4x7 + 1 is defined by h (x) = 7x Find the rule defining
   • iii) (goh)of iv) go(hof)

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