1

GATE CSE 2002

Subjective

+5

-0

Let $$A$$ be a set of $$n\left( { > 0} \right)$$ elements. Let $${N_r}$$ be the number of binary relations on $$A$$ and Let $${N_r}$$ be the number of functions from $$A$$ to $$A$$.

(a) Give the expression for $${N_r}$$ in terms of $$n$$.

(b) Give the expression for $${N_f}$$ in terms of $$n$$.

(c) Which is larger for all possible $$n, $$ $${N_r}$$ or $${N_f}$$?

(a) Give the expression for $${N_r}$$ in terms of $$n$$.

(b) Give the expression for $${N_f}$$ in terms of $$n$$.

(c) Which is larger for all possible $$n, $$ $${N_r}$$ or $${N_f}$$?

2

GATE CSE 2002

Subjective

+5

-0

(a) $$S = \left\{ { < 1,2 > ,\, < 2,1 > } \right\}$$ is binary relation on set $$A = \left\{ {1,2,3} \right\}$$. Is it irreflexive?

Add the minimumnumber of ordered pairs to $$S$$ to make it an $$\,\,\,\,\,$$equivalence relation. Give the modified $$S$$.

Add the minimumnumber of ordered pairs to $$S$$ to make it an $$\,\,\,\,\,$$equivalence relation. Give the modified $$S$$.

(b) Let $$S = \left\{ {a,\,\,b} \right\}\,\,\,\,$$ and let ▢ $$S$$ be the power set of $$S$$. Consider the binary relation $$'\underline \subset $$ (set inclusion)' on ▢ $$S$$. Draw the Hasse diagram corresponding to the lattice (▢$$(S)$$, $$\underline \subset $$)

3

GATE CSE 2000

Subjective

+5

-0

A multiset is an unordered collection of elements where elements may repeat ay number of times. The size of a multiset is the number of elements in it counting repetitions.

(a) what is the number of multisets of size 4 that can be constructed from n distinct elements so that at least one element occurs exactly twice?

(b) How many multisets can be constructed from n distinct elements?

4

GATE CSE 2000

Subjective

+5

-0

Let $$S = \left\{ {0,1,2,3,4,5,6,7} \right\}$$ and $$ \otimes $$ denote multiplication modulo $$8$$, that is, $$x \otimes y = \left( {xy} \right)$$ mod $$8$$

(a) Prove that $$\left( {0,\,1,\, \otimes } \right)$$ is not a group.

(b) Write $$3$$ distinct groups $$\left( {G,\,\, \otimes } \right)$$ where $$G \subset s$$ and $$G$$ has $$2$$ $$\,\,\,\,\,\,$$elements.

Questions Asked from Set Theory & Algebra (Marks 5)

Number in Brackets after Paper Indicates No. of Questions

GATE CSE Subjects

Discrete Mathematics

Programming Languages

Theory of Computation

Operating Systems

Computer Organization

Database Management System

Data Structures

Computer Networks

Algorithms

Compiler Design

Software Engineering

Web Technologies

General Aptitude