Important questions for DIS (BCSE 0306)

1. What is an ordered set. & Explain the concept of a partially ordered set with an example.
2. Short note on properties of lattices, a well-ordered set and a Hasse diagram
3. Explain the concept of a bounded lattice, complemented lattice and distributive [Link] an example.
4. what the concept of isomorphism to verify if two given ordered sets are isomorphic.
5. Consider the poset A = {a, b, c, d, e, f, g} be ordered shown in fig. Also let B = {c, d, e}. Determine the upper and
lower bound of B.
6. Explain the difference between an ordered set and a partially ordered set.
7. Prepare a Hasse diagram for the partial ordering {( A, B): A ⊆ B } on the power set P (S) where S = {a, b, c}
8. What is the concept of an isomorphic ordered set with an example.
9. Let A = {1, 2, 3, 4, 6, 8, 9, 12, 18, 24} be ordered by relation "a divides b". Draw the Hasse diagram.
10. Analyze the properties of the lattice formed by the power set of {a, b}.
11. Distinguish between isomorphic and non-isomorphic ordered sets with a case.

12. Determine the least upper bound and greatest lower bound of B = {a, b, c} if they exist, of the poset whose Hasse diagram
is shown in fig:
13. Define an ordered set and give an example. And List and describe the key properties of lattices.
14. Classify the given lattices into their respective types based on their properties
15. Explain the concept of a Hasse diagram, Construct a Hasse diagram for {1,2,3,6,12} under divisibility and explain your
steps.
16. State the axioms of a well-ordered set.
17. Differentiate between a partially ordered set and a totally ordered set with examples.
18. Define the role of complemented lattices in logic and computer science & what is a complemented lattice with a specific
example.
19. What are the application of distributive lattices in simplifying Boolean expressions.

20. Analyze the properties of a lattice formed by the power set of {x, y, z} under set intersection and union.
21. Compare and contrast bounded and unbounded lattices with examples.
22. Examine the differences between well-ordered sets and totally ordered sets with a practical example.
23. Evaluate the effectiveness of Hasse diagrams in visualizing complex [Link] is the process of constructing a Hasse
diagram and its use in analysing posets.
24. Consider the set A = {4, 5, 6, 7}. Let R be the relation ≤ on A. Draw the directed graph and the Hasse diagram of R.
25. Define an ordered set. Given the set S= {a, b, c, d} with the relation R={(a, b),(a, c),(b, d),(c, d)} determine whether
(S,R) is a partially ordered set. Justify your
26. Construct the Hasse diagram for the partially ordered set (S , ≤), where S={1, 2 ,4, 8, 16} and ≤ represents divisibility.
27. Explain the concept of isomorphic ordered sets. Verify whether the ordered sets A= {1,2,3,4} with the usual order and
B={a, b, c, d} with the order a < b < c < d, are isomorphic.
28. Determine whether the lattice formed by the subsets of S={a, b, c} is complemented. Provide examples of complemented
elements.
29. Define composition of relation and give example and Define a set. Give an example of a finite
and infinite set.
30. A computer company must hire 20 programmers to handle system programming and 30
programmers to handle application programming. 5 programmers are supposed to perform job
of both types. How many programmers must be hired?
31. Define Improper sets and give a example. And Define the universal set and complement of a
 Important questions for DIS (BCSE 0306)

set with an example.

32. Define: (i) Equal set (ii) Subset , Define Equal and Equivalent Set with example.
33. Explain partially ordered set (poset)? Provide an example.
34. Differentiate between a reflexive relation and a symmetric relation? Define an equivalence
[Link] an example of each.
35. If R={(1,2),(2,3),(3,4)} and S={(2,5),(3,6)}, find R∘S (composition of relations).
36. Let R={(a,a),(b,b),(c,c)}. R reflexive? Is it symmetric?
37. Define the transitive closure of a relation. How is it computed?
38. In how many ways we can represent sets in set [Link] with example. Write the
following sets in set builder form:
(i)A={2,4,6,8} (ii)
B={1,3,5,7,9}

39. Let A = {a, b, c}, B = {x, y}, and C = {0, 1}. Find A x B x C, C x B x A, C x A x B, B x B x B
40. Differentiate between finite, infinite, countable, and uncountable sets with examples.
41. Explain and provide examples of union, intersection, and difference of sets.
42. Let R={(1,1),(2,2),(3,3)} on A={1,2,3}.
Is R an equivalence relation?

43. Define the cardinality and power set of a set. Find the cardinality of Power set of A={a,b,c,d}.
44. Prove that (i) A∩B=B∩A
(ii)A∪B=B∪A

45. Explain the properties of reflexive, symmetric, and transitive relations with examples.
46. Prove that the relation R={(a,b)∣a≤b} is a partial order.
47. What is the composition of relations? Given two relations R 1={(1,2),(2,3)} and
R 2={(2,4),(3,5)}, find
R 1 ∘ R 2 (composition of relations).
48. Differentiate between partial order and total order with examples.
49. Let R={(a,b)∣a divides b,a,b∈{1,2,3,4}}. Write down all the ordered pairs in R.
50. Define a binary relation. Is R={(1,2),(2,3),(3,1)} transitive? Justify.
51. Let A={1,2,3,4,5} and B={3,4,6,7}. Find:
a) A∪B,
b) A∩B,
c) A−B,
d) B−A.
52. If A={1,2,3}, find the power set P(A) and determine its cardinality.
If A={a,b,c} and B={1,2}, find the Cartesian product A×B.

53. Consider A={1,2,3} and R={(1,2),(2,3)}. Find the transitive closure of R.

54. In a class of 60 students, 40 students like maths, 36 students like science, 24 like both the
subjects. Find the number of students who like;
i) Only maths
ii) Only science
iii) Either maths or science
iv) Neither maths nor science
55. For U={1,2,3,4,5,6,7,8,9,10}, let A={2,4,6,8,10} and B={1,2,3,4,5}. Find:
a)A△B (symmetric difference),
b) complement of (A∪B)

56. Let A={1,2,3} and R={(1,1),(2,2),(3,3),(1,2)}. Check if R is reflexive, symmetric, or transitive.

57. Differentiate between reflexive and irreflexive relation, give their example.
58. Prove that the binary relation {(1,1), (2,1), (2,2), (2,3), (2,4), (3,1), (3,2)} on the set {1, 2, 3} is
neither reflective, nor irreflexive but transitive. (CO1)
59. A= {1, 2, 3} and R= { (1, 2), { 2, 3), (3, 1). Find following for R :a) Symmetric closure b)
Reflexive Closure c) Transitive Closure
 Important questions for DIS (BCSE 0306)

60. Explain composition of relation. List the basic need for composition of relation and also give its
example.
61. Differentiate between complement and inverse of a relation. Give example using Venn
diagram.
62. State two ways to represent the relation with an example. Differentiate among symmetric,
asymmetric and antisymmetric relation.
63. Define Ordered set and Ordered pairs. If set A have 5 numbers of elements and set B have 4
number of elements then what will be the cardinality of A X B give example.
64. Explain the idea of Subset and Super set with example. State how a Null set can be a subset
of Singleton set.
65. Define relation. Explain various types of relations with example.
66. a) Define the composition of relations and compute an example involving three relations R1,
R2 and R3.
b) Prove that composition of relations is associative.

67. Among 100 students, 32 study mathematics, 20 study physics, 45 study biology, 15 study
mathematics and biology, 7 study mathematics and physics, 10 study physics and biology and
30 do not study any of three subjects. (a) find the number of students studying all three
subjects. (b) find the number of students studying exactly one of the three subjects.

68. Out of 250 students who failed in an examination, it was revealed that 128 failed in
mathematics,87 failed in physics and 134 failed in chemistry.31 failed in maths and physics,54
failed in chemistry and mathematics,30 failed in chemistry and [Link] how many
candidates failed in:
[a]in all the three subjects.
[b]in mathematics but not in physics.
[c] in chemistry but not in mathematics.
[d]in physics but not in chemistry or in mathematics.
[e]in chemistry or in mathematics but not in physics.

69. Let A={1,2,3} and R={(1,1),(2,2),(3,3),(1,2)}. Check if R is reflexive, symmetric, or transitive.

70. Let R={(a,b)∣a≤b,a,b∈{1,2,3,4}}. Write all ordered pairs in R and verify if it is a partial order.
71. Verify if the relation R={(x,y)∣x divides y} is a partial order on {1,2,3,4,6}.
72. Explain associative property on sets? Let A={1,2,3},B={2,3,4},C={3,4,5}. Verify both
the parts of associative property.
73. A survey shows out of 150 students, 90 students like cricket, 60 like football, and 40
like both. How many students like:
a) Only cricket,
b) Only football,
c) Neither sport. Use Venn diagrams to justify your answer.
74. Define a bipartite graph and illustrate it with an example.

75. State Euler’s Theorem for an Eulerian graph.

76. Interpret the concept of a regular graph and give an example.

77. Define the conditions under which a graph is planar.

78. Evaluate the conditions that need to be met for a graph to be Hamiltonian and illustrate with an example.

79. Define Hamiltonian paths and Hamiltonian circuits. Explain the conditions under which a graph contains a Hamiltonian
path or circuit with examples.

80. List and describe the basic terminology of graphs, including vertices, edges, degree, and their significance in graph theory.
 Important questions for DIS (BCSE 0306)

81. Explain the difference between a walk, path, and cycle in a graph. Discuss how these concepts are used in graph theory
and real-world applications.

82. Discuss the importance of graph connectivity in real-world networks. Explain how graph connectivity is tested and how it
affects the structure of the graph.

83. Design an algorithm to check if a graph is Eulerian. Explain the steps involved and provide a detailed example where this
algorithm can be applied.

84. Create an example of a Hamiltonian graph and demonstrate the process of finding the Hamiltonian path and Hamiltonian
circuit within the graph.

85. Construct a graph coloring algorithm that minimizes the number of colors used. Apply the algorithm to a given graph and
demonstrate the process.

86. Design a connected graph and illustrate how to transform it into an Eulerian graph by adding or removing edges. Justify
the changes made in the graph.

87. Evaluate the significance of Euler’s Theorem in finding Eulerian circuits in practical applications.

88. Define a graph in detail. Discuss the different types of graphs (e.g., directed, undirected, weighted, unweighted) with
examples and explain their applications.

89. Provide a detailed explanation of Euler's Theorem. Apply it to find if a graph with 6 vertices and 8 edges contains an
Eulerian circuit.

90. Explain the concept of a regular graph. Illustrate with examples and explain how the regularity property impacts the
degree of vertices.

91. List and explain all graph representations (adjacency matrix, adjacency list, incidence matrix). Compare them in terms of
time complexity and space usage.

92. Discuss Eulerian graphs and Hamiltonian graphs in terms of their properties. Provide examples and discuss their practical
uses.

93. Describe the concept of a bipartite graph. Provide detailed steps to check if a given graph is bipartite and illustrate with an
example.

94. Explain the process of graph coloring in detail. Discuss its applications in real-world problems like scheduling or map
coloring, using an example.

95. What is the largest number of vertices in a graph with 35 edges if all verteces are degree atleast3

96. Given a graph, apply Euler’s Theorem to determine whether it contains an Eulerian circuit. Show your working step-by-
step.

97. Prove that a simple graph with n vertices must be connected if it has more than [(n-1)(n-2)]/2 edges.

98. Analyze the concept of graph isomorphism. Explain how to test whether two graphs are isomorphic, using a step-by-step
approach and a detailed example.

99. Given a real-world scenario of a social network with 5 users (vertices) and 6 relationships (edges), construct a graph
representing the network. Represent this graph using both an adjacency matrix and an adjacency list. Then, determine if
 Important questions for DIS (BCSE 0306)

the graph is connected or disconnected. Explain the steps involved in determining its connectivity.

100. You are given a graph with 6 vertices and 8 edges, and you need to determine if it contains an Eulerian circuit.
Apply Euler’s Theorem to check the degree of each vertex and the graph’s connectivity. If an Eulerian circuit exists, trace
the path and explain the reasoning behind your solution.