SMU MCA Assignments

July 2011 Master of Computer Application (MCA) Semester 1 MC0063 Discrete Mathematics 4 Credits (Book ID: B0676 and
and B0677) Assignment Set 2 (60 Marks)

Answer all Questions Q.1) Check whether the following set of vectors is LD or LI (a){(1, 0, 0), (2 , 0, 0), (0, 0, 1)}, (b) {(1, 0, 1) , (1, 1, 0), (1, 1, -1)} Ans: Each question carries TEN marks
Q.2)
(a) Identity e = 3, a-1 =
9 . a
(b) Identity e = 2 and the inverse of a i.e., a-1 = Ans:
4 . a
Q.3)
For any a and b in a Boolean algebra
ab=ab
ab=ab
Answer: We show that (a b) is the complement of a b.
(by distributivity of over )
(by associative and commutative)
=1 Also,
=00 =0 Therefore By the principle of duality,
Page 1 of 3
Roll No. 521126647
July 2011 Master of Computer Application (MCA) Semester 1 MC0063 Discrete Mathematics 4 Credits (Book ID: B0676 and B0677) Assignment Set 2 (60 Marks) Q.4) Prove that a connected graph G is an Euler graph if and only ifit can be decomposed into circuits.
Answer: Suppose graph G can be decomposed into circuits; that is, G is a union of edge-disjoint circuits. Since the degree of every vertex in a circuit is two the degree of every vertex in G is even. Hence G is an Euler graph. Conversely, let G be an Euler graph. Consider a vertex v1. There are at least two edges incident at v1. Let one of these edges be between v1 and v2. Since vertex v2 is also of even degree, it must have at least another edge, say between v2 and v3. Proceeding in this fashion, we eventually arrive at a vertex that has previously been traversed, thus forming a circuit. Let us remove from G. All vertices in the remaining graph (not necessarily connected) must also be of even degree. From the remaining graph remove another circuit in exactly the same way as we removed from G. Continue this process until no edges are left. Hence the theorem. Arbitrarily Traceable Graphs: Consider the graph in Fig. 1 which is an Euler graph. Suppose that we start from vertex a and trace the path a b c.
Fig. 1: Arbitrarily traceable graph from c Now at c we have the choice of going to a, d or e. If we took the first choice, we would only trace the circuit a b c a, which is not an Euler line. Thus, starting from a, we cannot trace the entire Euler line simply by moving along any edge that has not already been traversed. Such a graph is called an arbitrarily traceable graph from vertex v. For instance, the Euler graph in Fig. 1 is an arbitrarily traceable graph from vertex C, but not from any other vertex. An Euler graph G is arbitrarily traceable from vertex v in G if and only if every circuit in G contains v. Q.5) Prove the theorem as given below If a binary n-tuple (x1, x2, ,xn) is transmitted across a binary symmetric channel with probability p that no error will occur in each coordinate, then the probability that there are errors in exactly k coordinates is
n k n k q p k
Answer: Fix k different coordinates. We first compute the probability that an error has occurred in this fixed set of coordinates. The probability of an error occurring in a particular one of these k coordinates is q; the probability that an error will not occur in any of the remaining n-k coordinates is p. The probability of each of these n independent events is qkpn-k. The number of possible error patterns with exactly k errors occurring is equal to
, the number of combinations of n things taken k at a time. Each of these error patterns has
probability qkpn-k of occurring; hence the probability of all these error patterns is
Page 2 of 3
Roll No. 521126647
July 2011 Master of Computer Application (MCA) Semester 1 MC0063 Discrete Mathematics 4 Credits (Book ID: B0676 and B0677) Assignment Set 2 (60 Marks)
Q.6) Prove that a non-empty subset H of a group G is a subgroup of G if and only if a) a, b H ab H b) a H a 1 H Answer: Suppose that H is a subgroup of G itself is a group under the product in G. Therefore (a), (b) holds. Converse: Suppose H satisfies (a) and (b). By (a), H satisfies the closure property. For any a, b, c H, we have that a, b, c G implies that a(bc) = (ab)c. Therefore (H, .) is a subgroup of (G, .).
Page 3 of 3
Roll No. 521126647

SMU MCA Assignments

Uploaded by

Copyright:

Available Formats

SMU MCA Assignments

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

SMU MCA Assignments

Uploaded by

Copyright:

Available Formats

July 2011 Master of Computer Application (MCA) Semester 1 MC0063 Discrete Mathematics 4 Credits (Book ID: B0676 and

and B0677) Assignment Set 2 (60 Marks)

(a) Identity e = 3, a-1 =

(b) Identity e = 2 and the inverse of a i.e., a-1 = Ans:

For any a and b in a Boolean algebra

(by distributivity of over )

(by associative and commutative)

=00 =0 Therefore By the principle of duality,

Roll No. 521126647

Roll No. 521126647

Roll No. 521126647

You might also like