Guru Jambheshwar University 2006 M.C.A mathematics2 - Question Paper
Subject Code4274
M.C.A. (Second Year) EXAMINATION
(5 Years Integrated Course)) (Re-appear)
MATHEMATICSG MCA-205 Discrete Mathematical Structures
Time : 3 Hours Maximum Marks : 100
Note : Attempt any Five questions. All questions carry equal marks.
h (a) Give group axioms. Show that the set Z
of all integers ..........., ~ 5, - 4, - 3, - 2,
- 1, 0, 1, 2, 3, 4, 5?.............is a group
with respect to the operation of addition of integers.
(b) Define a Subgroup. Let H be a subgroup of G, then prove that the right cosets Ha form a partition of G.
(c) Explain the following :
(i) Normal subgroup
(ii) Semi-group and Free semi-group.
. (a) Define a grammar and language of a grammar. Discuss also various types of grammars.
(b) Define a finite-state machine. Design a finite-state machine that performs serial addition.
(c) Describe the following :
(i) Finite graph
(ii) Length of path
(iii) Cut points and bridges
(iv) Subgraphs.
. (a) If a simple graph G with n vertices has
1
more than ~ (n - 1) (n -2) edges, then prove that G is connected.
(b) Use adjacency matrix to represent the graph shown in figure :
Draw the graph represented by the incidence matrix :
4. (a)
|
a |
1 |
0 |
0 |
0 |
0 |
1 |
|
b |
0 |
I |
1 |
0 |
1 |
0 |
|
c |
1 |
0 |
0 |
1 |
0 |
0 |
|
d |
0 |
1 |
0 |
1 |
0 |
0 |
|
e |
_ |
0 |
1 |
0 |
1 |
1 |
Describe an efficient algorithm for comparing distances in graphs.
(b)
(c)
Describe Infix, Prefix and Postfix form of an algebraic expression in trees.
Define partially ordered sets. Consider P(s) as the power set, show that the inclusion relation Q is a partial ordering on the powerset P(s).
(b) Explain bounded lattice and Hasse diagram. Draw the Hasse digram of (P(A), c), where :
(i) A = {0, 1}
(ii) A - {0, 1, 2, 3}
6. (a) What do you mean by Boolean Algebra ?
Prove the following for Boolean Algebra :
(i) The zero and unit elements are unique
(ii) The complement of an element is unique.
(b) Prove that :
(i) a 4* {a.b) = a + b and
a.(a + b) = a.b
(ii) (a+b).(b+c) + b.(a+c) ~
a.b + a.c + b
7. (a) Show that (p/\q) - (jpvq) is a tautology.
(b) With the help of truth tables, prove that :
(c) Write a short- note on gate circuits.
8. (a) Explain an integral domain and a finite field.
(b) Show that the set S of all matrices of the
fa
form , L where a,b e R is a field y-b a y
with respect to matrix addition and matrix multiplication.
(c) Let f(t) = t4 - 313 + 311 +31-20. Find all the roots of fit) given that t - (1 + 2i) is a root.
J-4274 5 1,500
|
Attachment: |
| Earning: Approval pending. |
