1
LOYOLA COLLEGE (AUTONOMOUS), CHENNAI 600 034
M.C.A.DEGREE EXAMINATION COMPUTER APPLICATIONS
FIRSTSEMESTER APRIL 2018
17PCA1MC01- DISCRETE STRUCTURES
Date: 27-04-2018 Dept. No. Max. 100 Marks
Time: 09:00-12:00
Section A (10 X 2 20 Marks)
Answer all Questions
1. Define Quantifiers.
2. What do you mean by predicates?
3. List out the set operations.
4. Define Partial Ordering.
5. What is permutation and combination?
6. What are the basics of counting?
7. Define a Hamiltonian path.
8. What is minimum spanning tree?
9. Define Semigroup.
10. Define Monoids.
Section B X 8 40 Marks)
Answer all Questions 11. a)What is conjunctive Normal form? Convert v into Conjunctive Normal Form.
or
What is disjunctive Normal form? Convert v into disjunctive Normal Form.
12. Explain the types of Function with example.
Or
Explain the properties of a Function. Give example.
13. Discuss about pigeon hole principle. Write example.
Or
Discuss about Recurrence relations with example.
14. Write about representation of graphs.
Or
Discuss about the minimum spanning tree.
15. Explain Homomorphism with example.
Or
Write about Finite state machine with no output
2
Section C X 20 40 Marks)
Answer any TWO Questions
16. Prove the following using laws ≡ ¬p ii) → ≡ q
Explain Mathematical Induction and Structural Induction.
17. Discuss in detail the Inclusion and Exclusion principle with their applications.
Explain any one shortest path method with an example
18.a) Explain the Finite state machine with output. Give example
Discuss in detail about the Tree traversal.