Centre for Development of Advanced Computing(C-DAC) 2005 M.C.A Computer Aplications 107 Front Discrete Structures - - Question Paper
(Please Write your Exam Roll No. immediately) Roll No.
FIRST SEMESTER [MCA] - DECEMBER 2005
Paper Code: MCA-107 Subject: Front Discrete Structures
Time: 3 Hours (Batch 2004, 2005) Maximum Marks: 60
Note: Attempt five question in all including Q. 1 which is compulsory. Selecting any one question from each unit. Q. 1 carries 20 marks and remaining question carry 10 marks
each
Q. 1. Compulsory Question:-
(a) Let A = {1, 2, 3, 4}. Give an example of a relation on A which is both an equivalence relation and a partial order relation.
(b) Find the generating function for the numeric function an =2n+3, n > 0.
(c) Show that
|
n + 1 |
= |
S' "N n |
+ |
s' ~\ n |
|
r V J |
r v J |
r -1 J |
(d) Let D30 be the set of all positive divisors of 30. Draw Hasse diagram of lattice D30.
(e) Let a, b, and c be any elements in a Boolean Algebra (B, v, A, /, O, I). Show that a v (a a b) = a.
(f) Let p and q be proportions. Show that p q = ~p v q.
(g) Let f :G H be a group homomorphism. If x e G, show that
(f (x)) -1 = f (x -1)
(h) Find the adjacency matrix of the graph shown below :-
(i) Define a finite state machine. What are its limitations?
(j) What do you mean by a context free grammar? In what manner it differs from context-sensitive grammar?
Q. 2. (a) State Pigeonhole Principle. How many people among 2, 00,000 people are born at the same time (hour, minute, seconds)?
(b) Let A = {1, 2, 3, 4} and R = {(1,2), (2,3), (3,4), (2,1)}. Find the transitive closure of R.
Q. 3. (a) Find explicit formula for the sequence defined by ai =1, an = 3an_i + 1, n > 2.
(b) Find the corresponding generic function for the generating function z
Q. 4. (a) A software engineer makes the following observations in a computer programming :-
Q. 6. (a) Giving graphical representation discuss Seven Bridges Problem. Was it possible for a citizen to make a tour of the city and cross each bridge exactly twice? Give reasons.
(b) Define a cyclic group. Show that any two cyclic groups of the same order are isomorphic.
Q. 7. (a) Write Dijkstras Shortest Path Algorithm and grow a Dijkstra tree from s to t in the graph given below :-
|
3 |
 |
|
1 |
(b) (i) Are the following graphs isomorphic? Give reasons.
y
 |
z n |
 |
e |
(ii) Is there a non-empty simple graph with twice as many edges as vertices? Give arguments.
(iii) Give an example of a graph that has an Hamiltonian circuit but nit an Euler circuit.
(iv) What are the generators of additive group of integers?
(v) Define even and odd punctuations. What is the order of the set An of all even permutations in symmetric group Sn ?
|
Q. 8. (a) Find the language accepted by the automation M shown in the transition diagram below:-a |
 |
(b) Determine whether the string abbaa accepted by the finite state automation having transition diagram given below :-
 |
b |
Q. 9. (a) Find a context-free grammar G which generates the language
L = {anbn : n > 0}
(b) State and prove Pumping Lemma
|
FIRST SEMESTER [MCA] - DECEMBER 2004 | ||||||
| ||||||
Q. 1. Answer the following: 20
(a) Let A = {1, 2, 3} and {2, 3, 5. Which of the following are relations from A to B?
(i){(1,3),(2,2), (3,5),(1,5)}
(ii) {(2,2),(2,1), (2,3),(2,5)}
(b) Prove that n! (n+2) = n! + (n+1)!.
(c) Verify the equality 2C(7,4) = C(8,4)
(d) If the inverse if a is a-1 , then the inverse of a-1 is a i.e. (a-1) -1 =a.
(e) Let A{1, 7, 11, 13, 77, 91, 143, 1001} be ordered by the relation x divides y. Draw its diagram.
(f) Find the duals of the following parts :-
(i) ({10, 1, 2, 3}, <)
(ii) (N, 1)
(g) How many edges are there in a graph with 12 vertices each of degree 6?
(h) Suppose that a graph has 7 vertices. Each of degree 6. Into how many regions in the plane divided by planar representation of this graph?
2 2
(i) Let K = {a, ab, a } and L { b , ab, a} be a language over A={a, b}. Find
(i) KL (ii) LL
(j) Consider the Language L= {ab, C} over A = {a, b, c} find
(i) L0 (ii) L3
Q. 2. (a) For any relation R in a set A, prove that
(i) R is symmetric if and only if R-1 is symmetric.
(ii) R is reflexive if and only if R-1 is reflexive.
(b) Use mathematical induction to show that 5 divides n5 -n whenever n is a non negative integer. 5
Q. 3. (a) If C(n,a): C(n, r + 1)=1:2 and C(n, r + 2) = 2:3 determine values of n and r.
(b) For the post of 5 teachers, there are 23 applications, 2 posts are reserved for SC candidates and there are 7 SC candidates among the applicants in how many ways the section is made. 3
(c) A gentleman invites a party of (m+n) friends to a dinner and place m at one table and the remaining n at another, the tables being round. Prove that the number of ways in which he can arrange them among themselves is (m+n)!/mn. 4
Q. 4. (a) Obtain the equivalent conjutive normal formal or product of sum canonical form of Boolean expression in three variable xi, x2, x3
(i) x1, x2
(ii) xi . (X21. X31) 5
(b) A detective has interviewed four witnesses to a crime from the stories of the witness the detective has concluded that if the butler is telling the truth then so is the cook, the cook and the gardener cannot both be telling the truth ; the gardener and the handyman are not both lying ; and if the handyman is telling the truth then the cook is lying. For each of the four witnesses, can the detective determine whether that person is telling the truth or lying? Explain in your reasoning. 5
Q. 5. (a) Use Dijkstras Algorithm to find the length of the shortest path between
the vertices a and t in the weighted graph in fig: 5
4
 |
t |
|
(b) Let A = {1, 2, 3, 4, 5, 6}. Let R be the relation in A defined by xRy if x |
 |
(i) Write R as a set of ordered pairs.
(ii) Draw a diagram of the directed graph which corresponds to R.
Q. 6. (a) Let A = {a, b}. Describe verbally the following language over A 3
(i) L1 = {a . b)m : m> 0}
(ii) L2 = {ar b as b at: r, s, t > 0}
(iii) L3 = {a2 bma3: m >0}
(b) Suppose a = a (W) for some input W and suppose a a. Can M recognize W? 3
(c) Let A= {a, b}. Find a Turing machine M which recognizes the Language L = {abn : n > 0}, that is, where L consists of all the words W beginning with one a and followed by one or more bs. 4
(b) Design a three-input-minimal AND-OR circuit with the following truth table:-
T = [A, B, C, L] = [00001111, 00110011, 01010101, 11001101]
|
Attachment: |
| Earning: Approval pending. |
