Gujarat University
MCA Semester I
DMS
Date: 23rd March, 1988 Marks:50
Instructions:
Attempt any three questions from each section, they carry equal marks.
Section I
Q-1 a) Describe the partition of Z induced by the congruence relation a * b (mod 10).
b) Compute n * r and n.r for
n = ((
Q-2 a) Explain the terms:
1. weighted graph
2. hamiltonion path
3. adjacency matrix
b) Explain the broadcasting algorithm for finding the shortest path between any two vertices.
Q-3 a) Let A = (1,2,3,4,5) and define relation R on A by’ xRy iff x + 1 =y.
Give matrix or graphical representation of R, RR, RRR.
b) Let A = (0,1,2,3) and Let R = ((0,0), (1,1), (2,2), (3,3), (1,2), (2,1), (3,2), (2,3), (3,1),(1,3)). Show that R is an
equivalence relation.
Find equivalence class of each of the elements of A. Show the partition induced by R.
Q-4 a) How many different reflexive and symmetric relations are there on a set with three elements?
b) What is Pigeon-hole principle? Illustrate one of its applications.
c) Let A = B = {1,2,3,4,5}. Define function f: Aà B (if possible) such that
f is one-to-one and onto;
f is neither one-to-one nor onto;
f is one-to-one but not onto;
f is onto but one-to-one.
Q-5 a) Prove DeMorgan’s Law in Boolean algebra.
b) Consider the connected graph G
A B C
D E F
i) Find all simple paths from node A to node F.
ii) Find distance between A and F
iii) Find the diameter of G (the diameter of G is the maximum distance between two of its nodes.)
Section II
Q-6 a) Let M be matrix of diagraph D. Prove that ij the entry of the matrix M x M x M……x M ( n times) gives the
number of walks of length n from vertex V(i) and V(j).
b) Draw the transition diagrams for the machines corresponding to the following monoid:
[Z4, +4] [z2, +2], where symbols have usual meanings.
Q-7 A ”rook-matrix” is one having only 0s and 1s elements and there is exactly one 1 in each of the rows and
columns.
Let R(n) be a set of n x n rook-matrices. Write down the six matrices of R(3), includeing:
I = 1 0 0
0 1 0
0 0 1
a) Write down the matrix multiplication table for R(3), R(3) is a group under matrix multiplication. Is it Abelian?
b) Write down the set R(2) and prepare the multiplication table as above. Is R(2) abelian?
c) How many elements are there in R(n)?
Q-8 a) What is a complete graph? Draw complete graphs with n = 1,2,3,…n vertices.
b) Let G be a graph with n vertices. Prove that the following are equivalent:
i) G is a tree
ii) G is cycle-free and has (n-1) edges;
iii) G is connected and has (n-1) edges.
Q-9 a) Show that (1,2,3,4,5) is a group under operation *, where * is multiplication mod 5.
b) Let j be n-1 and * be multiplication operation. Write down the table for G = [<1, -1, j, -j>, *], show that g is
isomorphic to [Z4, +4] where Z4 is set (1,2,3,4) and +4 is addition mod 4.
Q-10 a) Let L = [L,È,Ç] be a lattice and a, b, c Î L show that:
A È b >= a; a Ç b >= b
b) What set of strings are defined by the following grammar? Terminal symbols: 0, 0, 1 where 0 is null
symbol;
non-terminal symbols: S and E;
Starting symbol: S
Production rules: Sà 080, Sà 181, Sà E, Eàf , Eà 0, Eà 1.
