1
LOYOLA COLLEGE (AUTONOMOUS), CHENNAI 600 034
M.C.A. DEGREE EXAMINATION COMPUTER APPLICATIONS
FIRST SEMESTER NOVEMBER 2017
CA 1804 DISCRETE STRUCTURES
Date: 02-11-2017 Dept. No. Max. 100 Marks
Time: 01:00-04:00
Section A (10 X 2 20 Marks)
Answer all Questions
1. What is biconditional statement. Write the truth table.
2. Define Quantifiers. Write example.
3. What is a function? Give Example.
4. Define Lattice. Write example.
5. Define Combination.
6. What is Binomial coefficient?
7. What is connected graph? Give example.
8. Define Spanning tree.
9. What is Homomorphism?
10. Define a Grammar.
Section B X 8 40 Marks)
Answer all Questions
11 Explain with examples the connectives used in the formation of compound statements.
Or
Write a procedure to find a Principle Conjunctive normal form. Give example.
12 Discuss about operations on set with example.
Or
What do you mean by equivalence relation. Explain with an example.
13 Explain Pigeon hole principle with an example.
Or
Explain Inclusion and Exclusion with example.
14 Explain about graph representation with example.
Or
Discuss in detail about Tree traversal.
15 Explain Lagrange's theorem.
Or
Define Grammar. Write its types. Give Example.
Section C X 20 40 Marks)
Answer any TWO Questions
16 Explain in detail the following
Predicates.
ii) Quantifiers.
2
Discuss in detail the following with example
Mathematical Induction.
ii) Strong Induction.
17 Explain the following
Binomial coefficients.
ii) Permutations.
Define minimum spanning tree. Explain with an example the Kruskal's algorithm for finding out the
minimum spanning tree.
18 Discuss in detail the Finite State Machine with output. Give example.
Explain the shortest path problem with an Example.