Acharya Nagarjuna University (ANU) 2006 B.Sc Information Technology Part II - , I : DISCRETE MATHEMATICS - - Question Paper
B.Sc. DEGREE EXAMINATION, MAY 2006
(Examination at the end of 1st Year)
Part II - info Technology
Paper I : DiscRETE MATHEMATICS
5
(DSDM 11)B.Sc. DEGREE EXAMINATION, MAY2006 {Examination at the end of First Year)
Part II - Information Technology Paper I : DISCRETE MATHEMATICS
Time : Three hours Maximum : 100 marks
Answer any FIVE questions.
All questions carry equal marks.
1. (a) Using mathematical induction prove that for all positive integers n.
6174-3 + 7:*-] js divisible by 43.
(b) Prove that proposition P that the sum of first n positive integers is w(>r +1): that is
P{)i) = 1 + 2 + 3 +... + n = w(jr +1)
2. (a) Let R and S be the following relations on *4 = {l,2,3}; R = {(U)(L2)(2J)(3,l)(3,3)};
S={(l,2)(l,3)(2rl)(3,i)}- Find <i) (ii) RoS =
(b) Consider the set Z of integers. Designa Rbby b={ir for some positive integers. . Show that R is a partial order on Z7 that is, show that R is (i) Reflexive (ii) Antisymmetric (iii) Transitive.
3. (a) Prove that any planar graph is 4-colorable.
(b) Draw the the graph G corresponding to given adjacency matrix.
|
0 |
1 |
0 |
1 |
0 |
|
1 |
0 |
0 |
1 |
1 |
|
0 |
0 |
0 |
1 |
1 |
|
1 |
1 |
1 |
0 |
1 |
|
0 |
1 |
1 |
1 |
0 |
B
 |
D |
B
|
4. {a) Find the adjacency matrix A of each graph. ' B | |
 |
D |
r\
D
(b) (i) Find the number of connected graphs with four vertices and draw them.
{ii} Draw all trees with five or fewer vertices.
5. Draw all possible non similar trees T where
(a) T is a binary tree with three nodes.
(b) T is a 2-tree with four external nodes.
6. (a) Prove each of the following statements.
(i) Any integer a is of the form +1,3+ 2 .
(ii) One of three consecutive integers in a multiple of 3.
(b) Write the dual of each Boolean equation.
(i] (fl*l)*(04fl')=0
{ii) a-\-a'b=a + b
7. Find the prime implicants and a minimal sum-of-pro ducts form for each of the following complete sum-of-products Boolean expressions.
(a) ] = .Tyz + jn.'z'-i-jr' yz '+j' y' z
(b) E2 = xyz + xyz'+xy'z+Jt'yz + x'y'z
(c) E, = xyz + ivt'-i-j:1 vi'-kv1 v'r'-t-x1 j1z
0. (a) State and prove Eulers formula for planar g raphs.
(b) Write a short notes on fuzzy sets and possibility theory.
9. Co n stru ct a bina ry t ree fo r th e fo llowi ng exp re ssi on.
CiJ + 5)*V[(3i> + c) + 2)]
10. (a) Prove that a binary tree with n nodes has exactly (n+1} null branches (b) Formulate an algorithm for the inorder traversal of a binary tree.
|
Attachment: |
| Earning: Approval pending. |
