Discrete Mathematics (DM) SPPU Endsem Question Paper May 2025

Questions

1. Q1

   1. a)

      A committee of 3 persons is to be formed from a group of 2 men and 3 women. In how many ways can this be done?

      Also asked:Dec 2025 ·May 2024

      [6]
   2. b)

      Find the number of arrangements that can be made out of the letters. i) ASSASSINATION ii) GANESHPURI

      [6]
   3. c)

      What is the number of ways of choosing 4 cards from a pack of 52 playing cards? In how many of these i) are face cards. ii) two are red cards and two are black cards.

      [6]
   OR

2. Q2

   1. a)

      Out of 4 officers & 10 clerks, a committee of 2 officers & 3 clerks is to be formed. In how many ways committee can be done? i) Any officer & clerk can be included. ii) A particular clerk must be in committee. iii) A particular officer cannot be in committee.

      [6]
   2. b)

      How many words with or without meaning can be formed using the letters of the word EQUATION using each letter exactly once?

      [6]
   3. c)

      Salad is made with combination of one or more eatables, how many different salads can be prepared from onion, carrot, cabbage & cucumber. 2

      [6]

3. Q3

   1. a)

      Define following terms with example. i) Complete graph ii) Regular graph iii) Bipartite graph iv) Complete bipartite graph v) Paths and Circuits vi) Acyclic Graph iv) Complement of a graph

      [7]
   2. b)

      The graphs G and H with vertex sets V(G) and V(H), are drawn below. Determine whether or not G and H drawn below are isomorphic. If they are isomorphic, give a function g: V(G)-> V(H) that defines the isomorphism. If they are not explain why they are not.

      [5]
   3. c)

      Is it possible to draw a simple graph with 4 vertices and 7 edges. Justify?

      [5]
   OR

4. Q4

   1. a)

      Find the shortest path for a to z in the following graph using Dijkstra’s algorithm:

      [7]
   2. b)

      For the following graph find whether Eulerian graph and circuit exists. If yes write the Eulerian path and circuit. 3

      [5]
   3. c)

      Convert following non planar into planar graph. Also show the validity of Euler’s formula for the given graph.

      [5]

5. Q5

   1. a)

      Construct an optimal binary tree for the set of weights as {8, 9, 10, 11, 13, 15, 22}. Find the weight of an optimal tree. Also assign the prefix codes and write the code words.

      [6]
   2. b)

      Use Kruskal’s algorithm to find the minimum spanning tree for the connected weighted graph G as shown in fig. below.

      [6]
   3. c)

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

      [6]
   OR

6. Q6

   1. a)

      Explain i) Cut set ii) Complete Binary tree iii) Prefix code 4

      [6]
   2. b)

      Use Prim’s algorithm to find minimum spanning. Take A as starting vertex (label remaining vertices)

      [6]
   3. c)

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

      [6]

7. Q7

   1. a)

      Define with examples : i) Ring with unity ii) Fields iii) Integral Domain

      Also asked:Dec 2025

      [6]
   2. b)

      Explain Algebraic system and properties of binary operations.

      [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 with examples : i) Groupoid ii) Monoid iii) Abelian group.

      [6]
   2. b)

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

      [6]
   3. c)

      Prove that (I, +) is an abelian group, where I is a set of all integers with respect to binary operation '+'. JJJ

      Also asked:May 2024

      [5]