1
LOYOLA COLLEGE (AUTONOMOUS), CHENNAI 600 034
M.C.A. DEGREE EXAMINATION COMPUTER APPLICATIONS
FIRST SEMESTER NOVEMBER 2017
17/16PCA1MC01 DISCRETE STRUCTURES
Date: 02-11-2017 Dept. No. Max. 100 Marks
Time: 01:00-04:00
Section A
Answer all Questions (10 X 2 20 Marks)
1. Define proposition. Give example.
2. What is conjunctive normal form? Write example.
3. What do you mean by relation?
4. What is partially ordered relation? Give example.
5. Define Sum Rule.
6. Define permutation.
7. What is weighted connected graph? Give example.
8. Define Hamiltonian path.
9. What is monoid?
10. Define a Grammar.
Section B
Answer all Questions X 8 40 Marks)
11 Explain with examples the connectives used in the formation of compound statements.
Or
Obtain the Disjunctive normal form for the following
P p → q
ii) p V → q V q →
12 Discuss about Equivalence relation with example.
Or
What do you mean by Mathematical Induction? Prove that
1 2 3 . . . n 2 if is a positive integer.
2
13 Define counting. Discuss its types with example.
Or
A total of 1232 students have taken a course in Spanish, 879 have taken a course in French, and
114 have taken a course in Russian. Further, 103 have taken courses in both Spanish and French,
23 have taken courses both in Spanish and Russian, and 14 have taken courses in both French and
Russian. If 2092 students have taken at least one of Spanish, French and Russian, how many
students have taken a course in all three languages.
14 How Graph are represented? Explain with example.
Or
Discuss the traveling sales man problem with an example.
15 Explain Homomorphism and Isomorphism with example.
Or
Define Grammar. Write its types. Give Example.
Section C
Answer any TWO Questions X 20 40 Marks)
16 Prove the following proposition without truth table
V p p
ii) → → p q → r
Discuss in detail the following with example
Recursive Induction.
ii) Strong Induction.
17 Explain the following
Sum and Product Rule.
ii) Linear Recurrence Relation.
Define minimum spanning tree. Explain with an example the Prim's algorithm for finding out the
minimum spanning tree.
18 Discuss in detail the Finite State Machine with output. Give example.
b)Explain the Tree Traversal with an Example.