2004-05 MODEL PAPER

MCA 1.1.1

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

1. Answer the following
a) Write the elements of the set P(P(P(φ))) where P(A) denotes the power set of the set A and φ 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 S_k-7S_k-2+6S_k-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
x₁ + x₂ +x₃ + x₄ + x₅ = 20 where x₁ ≥ 3, x₂ ≥ 2, x₃ ≥ 4. x₄ ≥ 6 and x₅ ≥ 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 a_n - 6a_n-1+12a_n-2 - 8a_n-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 { 0ⁿ1ⁿ | n ≥ 1 }