DISCRETE MATHEMATICAL STRUCTURES MCA 1.1.1

2005 Andhra University M.C.A DISCRETE MATHEMATICAL STRUCTURES :::: 

First Question is Compulsory                                                            Time: 3 Hrs.Max.

Answer any four from the remaining                                                    Marks: 100

Answer all parts of any Question at one place.                



1. Answer the following

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 1

b) 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 1

7. 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 }











2002 DISCRETE MATHEMATICAL STRUCTURES 

Time: Three hours

Maximum: 75 marks

Answer any FIVE questions.

First Questions is compulsory.

It comprises of seven sub-questions.

Each of the remaining questions carries 15 marks.



1.

a. Define ordered pairs. Give examples for a relation which is reflexive and transitive but not symmetric.

b. What is tautology? What is absurding?

c. Define a lattice and give examples.

d. How many integers between 1 and 1000 have sum of digits equal to 7.

e. Define bipartite graph.

f. What is Dual graph and Chromatic number of a path graph.

g. Define a finite state machine.



2. a. Show that if (A B) C = (A C) (B C)

b. For the poset (I15:/) draw a poset diagram and determine all maximal and minimal elements and greatest and least elements, if exists.



3. Show that in Boolean Algebra

i. (a+b)' = a' + b'

b. (a.b) + [(a+b)' . b ]' = 1



4.

a. Obtain the principal disjunctive and conjunctive normal forms of ( P -> (Q R )) [ ~ P -> (~Q R ))

b. Show that: [(p q) ~ (~p (~q ~r))) (~p ~q) (~p ~r) is a tautology.



5.

a. In how many ways can 30 distinguishable books be distributed among 3 people A,B and C so that

i. A and B together receive exactly twice as many books as C

ii. c receives at least 2 books; B receive at least twice as many books as C and A receive at least 3 times as many books as B.

b. Solve the recurrence relation: an - 7an-1 + 10an-2 = 0 for n => 2



6.

a. Show that the following graphs are isomorphic:

b. Differentiate between Eulerian path, Hamiltonian Path and Spanning tree.



7.

a. Find the minimal spanning tree of the following graph

b. Prove that a tree with n vertices has exactly (n-1) edges.



8.

a. Write the differences between Mealey and Moore machines.

b. Define a sequential machine. Let s be any state in a sequential machine and x and y be any words, then prove that (s,xy) = (s,x), y) and (s,xy) = ( (s,x),y)









2001 DISCRETE MATHEMATICAL STRUCTURES 

Time: Three hours

Maximum: 75 marks



Answer any FIVE questions.

First Questions is compulsory.

It comprises of seven sub-questions.

Each of the remaining questions carries 15 marks.



1.

a. In a complemented distributive lattice show that (a*b)' = a' b'

b. Show that ((P Q) ( P ( Q R))) ( P Q) ( P R) is a tautology

c. How many proper subsets of {1,2,3,4,5} contain the numbers 1 and 5?

d. Write the characteristic equation of the recurrence relation D(k) - 8D(k-1) + 16D(k-z) = 0 where D(2) = 16, D(3) = 80

e. Show that in any graph the sum of the degrees of all the vertices is always even.

f. Define a cut point of a graph and illustrate with an example.

g. Show that every finite semigroup has an idempotent.



2.

a. Show that in a lattice if a < = b and c < = d then a*c < = b*d

b. In any Boolean algebra, show that a < = b = > a + bc = b(a+c)



3.

a. Obtain the sum of the products canonical from of the Boolean Expression (x1 x2)' (x1' * x3)

b. Prove that (A B) (A ~B) = A and A (~A B) = A B where A,B are any two sets.



4.

a. Let T = {1,2,3,4,5}. How many subsets of T have less than 4 elements?

b. Show that ( x) M (x) follows logically from the premises (x)(H(x) -> M(x)) and ( x) H (x)



5.

a. List all possible functions from X = {a,b,c} to Y = {0,1} and indicate in each case whether the function is one-to-one, is onto and is one-to-one onto.

b. Obtain simplified Boolean expression for the equivalent expression m0 + m1 + m2 + m3 where 'mj's are the minterms in the variables x1, x2, x3 and x4.



6. Design a parity-check machine which is to read a sequence of 0's and 1's from an input tape. The machine is to output a 1 if the input tape contains an even number of 1's or 0 otherwise.



7.

a. Prove that there is a unique path between any pair of vertices in a tree and coverage.

b. Prove that in any tree there are at least two pendant vertices



8.

a. Prove that every circuit has an even number edges on common with any cut-set.

b. Explain Dijkstra's algorithm for finding the shortest path between any pair of vertices in a graph.