Discrete Mathematics (DM) SPPU Endsem Question Paper May 2024

Questions

1. Q1

   1. a)

      From a group of 7 men and 6 women, five persons are to be selected to from a committee so that at least 3 men are there on the committee. In how many ways can it be done?

      Also asked:Dec 2025 ·May 2025

      [6]
   2. b)

      How many 3-digit numbers can be formed from the digits 2,3,5,6,7 and 9, which are divisible by 5 and none of the digits is repeated?

      [6]
   3. c)

      How many 6-digit odd numbers greater than 6,00,000 can be formed from the digits 5,6,7,8,9, and 0 i) If repetition is allowed. ii) If repitition is not allowed

      [6]
   OR

2. Q2

   1. a)

      In how many different ways can the letters of the word ‘OPTICAL’ be arranged so that the vowels always come together

      [6]
   2. b)

      If a committee has eight members. i) How many way can the committee members be seated in a row? ii) How many way can the committee select a president, vice-precident and secretary

      [6]
   3. c)

      In a certain country, the car number plate is formed by 4 digits from the digits 1,2,3,4,5,6,7,8 and 9 followed by 3 letters from the alphabet. How many number plates can be formed if neither the digits nor the letters are repeated? 2

      [6]

3. Q3

   1. a)

      Show that the following graphs are isomorphic

      Also asked:Dec 2025

      [7]
   2. b)

      List and explain the necessary and sufficient conditions for Hamiltonian and eulerian path with suitable examples.

      Also asked:Dec 2025

      [5]
   3. c)

      Define the graph K n and K mn

      [5]
   OR

4. Q4

   1. a)

      Use dijkstras algorithm to find the shortes path between A and Z in figure.

      [7]
   2. b)

      Draw a complete bipartite graph on 2 and 4 vertices K2,4 and 2 and 3 vertices K2,3.

      [5]
   3. c)

      Under What condition K m,n will have eulerian circuit

      [5]

5. Q5

   1. a)

      Define following terms i) Level of a tree ii) Height of a tree iii) Fundamental circuit 3

      Also asked:Dec 2025

      [6]
   2. b)

      Use labeling procedure to find a maximum flow in the transport network given in the following figure. Determine the corresponding minimum cut.

      [6]
   3. c)

      Construct Minimal spanning tree for the following graphs using prims algorithm

      Also asked:Dec 2025

      [6]
   OR

6. Q6

   1. a)

      Define following terms i) Forest ii) Fundamental cutsets iii) Game tree

      Also asked:Dec 2025

      [6]
   2. b)

      Construct Minimal spanning tree of the following graphs using kruskals algorithm

      Also asked:Dec 2025

      [6]
   3. c)

      Construct an optimal tree for 10,11,14,21,16,18 using Huffman conding 4

      Also asked:Dec 2025

      [6]

7. Q7

   1. a)

      Define: i) Cyclic group ii) Abelian group iii) Cosets

      [6]
   2. b)

      This part has equations that don’t show as text. Open the PDF to read it.

      [6]
   3. c)

      This part has equations that don’t show as text. Open the PDF to read it.

      [5]
   OR

8. Q8

   1. a)

      Define: i) Group codes ii) Subgroup iii) Integral domain

      [6]
   2. b)

      Let (A,*) be an algebraic system where * is a binary operation such that for any a,b, belongs to A, a*b=a i) Show that * is an associated operation ii) Can * ever be a communtative operation?

      [6]
   3. c)

      Prove that the set Z of all integers with binary operation * defined by a* b = a+b+1 such that for all a,b belonging to Z is an abelian group 

      Also asked:May 2025

      [5]