DISCRETE STRUCTURES ( CODE:BTCS 302) -NOTES 1-IMPORTANT & EXPECTED QUESTIONS FOR PTU/KUK EXAM

DISCRETE STRUCTURES ( CODE:BTCS 302) 

( IMPORTANT & EXPECTED QUESTIONS FOR PTU/KUK)

SHORT ANSWER TYPE QUESTIONS   (2 MARKS EACH):

Q1. Define a Partial Order relation on a set A.

Q2. Give an example of an equivalence relation on set.

Q3. Define: (a) Euler Graph   (b) Bipartite Graph

Q4. Find the smallest possible simple graph which is not Bipartite.

Q5. Define: (a) Sub- Group (b) Normal Sub-Group of a Group.

Q6. Give an example of Boolean Ring.

Q7. State the necessary conditions for an Integral domain to be  a field.

Q8. Let A={ a, b, c}. Find all permutations on A.

Q9. Give difference between graph and a tree.

Q10. Define Boolean Ring.

Q11. Define Symmetric Relation with example.

Q12. If set A has 'n' elements, how many relations are there from A to A?

Q13. Define Objective function with example.

Q14. Define Asymmetric Relation with example.

Q15. Write Characteristic equation of Recurrence relation.

Q16. Determine whether the following function is a bijection from R to R. f(x)= -3x2+ 7

Q17. What is Chromatic number of Complete Graph( Kn).

Q18. Define Monoid.

Q19. Is K(3,3) is a planar graph? Explain and here K(3,3) is a Bipartite graph.

Q20. What do you mean by principle of Inclusion-Exclusion?

Q21. Is every function is a relation? Comment and explain.

Q22. Prove that an undirected graph has an even number of vertices of Odd degree.

Q23. What do you mean by Euler Circuit? give an example.

Q24. Determine whether the Relation R  on "set of Nil people" is reflexive, symmetric and/or transitive, where (a,b) € R if and only if a is taller than b.

Q25. Prove the absorption law x(x+y)= x using the other identities of Boolean Algebra.