Rajasthan Technical University 2011-3rd Sem B.Tech Computer Science and Engineering (Back, Old Scheme) Computer science & engineering, Discrete Mathematical Structure - Question Paper
Rajasthan tech. University
B.Tech three sem (Back, Old Scheme) Computer science & engineering,Feb 2011
3CP4 Discrete Mathematical Structure
H
Instructions to Candidates:
Attempt any five questions, selecting one question from each unit. All questions carry equal marks. (Schematic diagrams must be shown wherever necessary. Any data you feel missing may suitably be assumed and stated clearly. Units of quantities used/calculated must be stated clearly).
1. a) Prove that the following implications are tautologies : (8)
i) p a. q > pv q
ii) ~p-+(p>q)
b) Prove the following equivalences: (8)
ii) (p-+r)/\(q>r) = (pvq)-+ r
2. a) Prove p
pAq-r a s :.s
(8)
b) Test the validity of the following argument:
If 5 is a prime number, then it will not be divisible by 5. (8)
Unit - II
3. a) Prove that if n be an integer then if n2 is odd then n is also odd, by indirect
method. (8)
b) Use mathematical induction to prove that n3 - n is divisible by 3, whenever n
is a positive integer. (8)
3E1464/20H (1) [Contd....
4. a) Solve the recurrence relation a +a -6ci = 0 ; given that
J n n - I n - 2 ?
b) Solve the recurrence relation
w 0 + u , + u = n2 + n + 1 (8)
n + 2 n + 1 n v /
Unit - III
5. a) Prove that the number of odd degree vertices in a graph G is always even. (8)
b) Find the number of ways in which 11 persons may sit at a round table so that every person has different neighbours in those arrangements. (8)
6. Consider 3 coloring of the configurations of the vertices of a square. If the three colors are red, white and blue, how many non-equivalent configurations have exactly two blue vertices? (16)
7. a) In a Survey of 60 people it was found that 25 read News Week, 26 read Time
and 26 read the magazine Fortune. Also, 9 read both News Week and Fortune, 11 read News Week and Time, and 8 read Time and Fortune. If 8 read none of the three magazines, determine the number of people who read exactly one of the three magazines. (8)
b) Find the Discrete Fourier Transform of the sequence <dk> = {1,2, 3,4}. (8)
8. a) Show that the mapping f . A> A, defined by / (x) = 2x +1 is a bijection, find
b) Find the Discrete Fourier Transform of < dk > = {l,-1, 0}; k = 0,1, 2. (8)
Unit - V
9. a) Define the following: (8)
i) Monoid ii) Cyclic group
iii) Subgroup iv) Normal Subgroup
b) Show that intersection of two subgroups H and K of group G is also a subgroup of G. (8)
10. a) Let N be a normal subgroup of a group G, and let R be following relation on
G : a R b iff ab e N, then prove R is a congaience relation on G. (8)
b) Write down a short note on Parity check equations. (8)
3E1464 (2)
|
Attachment: |
| Earning: Approval pending. |
