2005 Andhra University MCA DISCRETE MATHEMATICAL STRUCTURES Question paper for exam preparation. Question paper for 2005 Andhra University MCA DISCRETE MATHEMATICAL STRUCTURES Question paper, 2005 Andhra University MCA DISCRETE MATHEMATICAL STRUCTURES Question paper. SiteMap

## Exam Preparation

 • AIPMT Exam Preparation • Civil Services Exam Preparation • IIT JEE Exam Preparation • Class 12th Standard Exam Preparation • Class 11th Standard Exam Preparation • Class 10th Standard Exam Preparation • Class 9th Standard Exam Preparation • Class 8th Standard Exam Preparation

## Question Papers

 • Class 9th Standard Question Paper • Class 10th Standard Question Paper • Class 11th Standard Question Paper • Class 12th Standard Question Paper • BA Question Paper • BBM Question Paper • BCA Question Paper • BCom Question Paper • BE Question Paper • BSc Question Paper • BTech Question Paper • LLB Question Paper • LLM Question Paper • MA Question Paper • MBA Question Paper • MCA Question Paper • MCom Question Paper • MSc Question Paper • MTech Question Paper

# 2005 Andhra University MCA DISCRETE MATHEMATICAL STRUCTURES Question paper

University Question Papers
2005 Andhra University MCA DISCRETE MATHEMATICAL STRUCTURES Question paper

DISCRETE MATHEMATICAL STRUCTURES

First Question is Compulsory

Answer any four from the remaining

Answer all parts of any Question at one place.

Time: 3 Hrs.
Max. Marks: 100

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) Give an example of a relation that is reflexive and transitive but not symmetric.
c) How many ways can 12 people have their birthdays in different calendar months?
d) Find the number of divisors of 400.
e) Write the characteristic equation of Sk-7Sk-2+6Sk-3=0.
f) Write the adjacency matrix of the following digraph.
-----DIAGRAM-----
g) Draw all possible binary trees with three 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) Find the number of integer solutions to the equation
x1 + x2 +x3 + x4 + x5 = 20 where x1 = 3, x2 = 2, x3 = 4. x4 = 6 and x5 = 0.

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

4. a) Find the number of ways of placing 20 similar balls into 6 numbered boxes so that the first box contains any number of balls between 1 and 5 inclusive and the other 5 boxes must contain 2 or more balls each.

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

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

0 1 0 0
0
0 0 1 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) Find the minimum spanning tree of the graph given by the adjacency matrix

0 1 0 0
0
1 0 1 0
0
0 1 0 17. a) Describe 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 1 in the last position and a 0 in the third to the last position read so far.

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