Andhra University 2005 M.C.A DISCRETE MATHEMATICAL STRUCTURES - Question Paper

2005 Andhra University M.C.A Computer Applications DiscRETE MATHEMATICAL STRUCTURES ques. paper

DiscRETE MATHEMATICAL STRUCTURES

First ques. is Compulsory

ans any 4 from the remaining

ans all parts of any ques. at 1 place.

Time: three Hrs.
Max. Marks: 100

1. ans the subsequent
a) Write the elements of the set P(P(P(f))) where P(A) denotes the power set of the set A and f denotes the empty set.
b) provide an example of a relation that is reflexive and transitive but not symmetric.
c) How many ways can 12 people have their birthdays in various calendar months?
d) obtain the number of divisors of 400.
e) Write the characteristic formula of Sk-7Sk-2+6Sk-3=0.
f) Write the adjacency matrix of the subsequent digraph.
-----DIAGRAM-----
g) Draw all possible binary trees with 3 nodes.

2. a) Check whether ((P? Q)? R)?((P? Q)?(P? R)) is a tautology.

b) How many positive integers less than 1,000,000 have sum of their digits equal to 19?

3. a) obtain the number of integer solutions to the formula
x1 + x2 +x3 + x4 + x5 = 20 where x1 = 3, x2 = 2, x3 = 4. x4 = six and x5 = 0.

b) A simple code is made by permuting the letters of the alphabet of 26 letters with every letter being changed by a distinct letter. How many various codes can be made in this way?

4. a) obtain the number of ways of placing 20 similar balls into six numbered boxes so that the 1st box contains any number of balls ranging from one and five inclusive and the other five boxes must contain two or more balls every.

b) Solve an - 6an-1+12an-2 - 8an-3 - 0 by generating functions for n = 3.

5. a) obtain the transitive closure of the digraph whose adjacency matrix is

0 one 0 0
0
0 0 one 0
0
1 0 0 1b) Build a binary search tree for the words : banana, peach, apple, pear, coconut, mango, papaya, orange, strawberry, pineapple, guava, pomegranate and grape using alphabetical order.

6. a) Write Kruskal's algorithm for finding the minimum spanning tree of a graph

b) obtain the minimum spanning tree of the graph provided by the adjacency matrix

0 one 0 0
0
1 0 one 0
0
0 one 0 17. a) define the steps involved in simplifying a logical expression that is in sum of products form using Quine -McCluskey method.

b) Use the Quine-McClusley method to simplify the sum-of-products expansion:
wxyz'+ wx'yz + wx'yz'+ w'xyz + w'x'yz + w'xy'z + w'x'y'z

8. a) Construct a finite state machine that determines whether the input string has a one in the last position and a 0 in the 3rd to the last position learn so far.

b) Construct a Turing Machine that recognizes the set { 0n1n | n = one }

Earning:   Approval pending.