B R3912 Pages: 2

Reg No.: Name:

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
THIRD SEMESTER B.TECH DEGREE EXAMINATION, DECEMBER 2018

Course Code: CS201
Course Name: DISCRETE COMPUTATIONAL STRUCTURES
Max. Marks: 100 Duration: 3 Hours
PART A
Answer all questions, each carries 3 marks. Marks
1 What non zero entries are there in the relation matrix of intersection of R and its (3)
converse if R is an anti-symmetric relation?
2 Define a recurrence relation. Give an example (3)
3 Show that the set of idempotent elements of any commutative monoid forms 2 (3)
submonoid.
4 Let ۶ R — र be given by f(x) = + - 2, where R is the set of real numbers. Find ۶" (3)
PART B

Answer any two full questions, each carries 9 marks.

5 ച Draw the Hasse diagram for the following sets under the partial ordering relation (5)
“Divides”, and indicates those which are totally ordered.
{2,6,24}, {1,2,3,6,12}, {2,4,8,16}, (3,9,27,54)
b) Prove that every equivalence relation on a set generates a unique partition of the (4)
set with the blocks as R-equivalence classes.

6 9) Solve the recurrence relation T(k) — 7 T(k-1) + 10 T(k-2) = 6 + 8k with 100) = 1 (5)
and T(1) = 2.

b) What is the minimum number of students required in anEnglish class to be (4)
surethat at least six will receive the same grade, ifthere are five possible grades?

7 93) From a group of 7 men and 6 women, 5 people are to be selected to forma (4)
committee, such that at least 3 men are there in the committee. In how many
ways can the committee be formed?

b) Let f: -> Rand ‏نع‎ R > रे, where R is the set of real numbers. Find f° gandg°f, (5)
where f(x) = x’ ಎ 2 and g(x) = x + 4. State whether these functions are injective,
surjective, and bijective.

PART C
Answer all questions, each carries 3 marks.
8 How many proper subgroups will be there for a group of order 11? Justify your (3)
answer.

9 Show that every chain is a distributive lattice. (3)
10 What conditions to be satisfied if an algebraic system (A, +, .) is called a ring? (3)
11 Define a complemented lattice. Give an example (3)

PART D

Answer any two full questions, each carries 9 marks.

12 a) Foracyclic group of order n generated by an element a, show that n is the least (5)

Page 1 of 2