Reg No.:

Max. Marks: 100

10

b)

a)

b)

B3809 Pages: 2

Name:

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

Course Code: CS201
Course Name: DISCRETE COMPUTATIONAL STRUCTURES (CS, IT)

PART A
Answer all questions, each carries 3 marks

Let X = {1,2,3,4} and R = {| x > y} . Draw the graph of R and also give its
matrix.
Define countable and uncountable set. Prove that set of real numbers are
uncountable.
State Pigeonhole principle. A school has 550 students. Show that at least two of
them were born on the same day of the year.
How many 4-digit numbers can be formed from six digits 1, 2, 3, 5, 7, 8. Also
find how many numbers are less than 4500.

PART B

Answer any two full questions, each carries 9 marks
Let Z be the set of integers and R be the relation called congruence modulo 3
defined by R = {| x and y are elements in Z and (x-y) is divisible by 3}.
Determine the equivalence classes generated by the elements of Z.
Let A be the set of factors of a particular positive integer m and let <= be the
relation divides, ie relation <= be such that x<=y if x divides y. Draw the Hasse
diagrams for m= 30 and m= 45.
Let f(x) = x+2, g(x) = x-2 and h(x) =3x for x is in R, where R is the set of real
numbers. Find gof, fog, (foh)og , hog .
Among 100 students, 32 study mathematics, 20 study physics, 45 study biology,
15 study mathematics and biology, 7 study mathematics and physics, 10 study
physics and biology and 30 do not study any of the three subjects.
i) Find the number of students studying all three subjects.
ii) Find the number of students studying exactly one of three subjects.

Solve the recurrence equation a + 5 81.1 + 6 81-2 =424' where a) = 278 and a,
= 962.
Define Monoid. Show that the algebraic systems are
monoids where m = 6.

PART C

Answer all questions, each carries 3 marks

Define Abelian group. Prove that the algebraic structure is an abelian
group. * defined on Q* bya * b =(ab)/2.
Define Cosets and Lagrange's theorem.
Draw the diagram of lattices forn= 15 and n= 45. Where Sn be the set

Page 1 of 2

Duration: 3 Hours

Marks

(3)

(3)

(3)

(3)

(5)

(4)

(4)

(5)

(4)

(5)

(3)

(3)
(3)