Punjab Technical University 2005-4th Sem B.Tech Computer Science and Engineering DISCRETE STRUCTURES (New) CS 203/204 3rd / 2k5 - exam paper

1.

1. What is a subgraph?
2. What is a cycle in a graph?
3. What is the in degree of a graph?
4. define {3,5,7,9,……77,79} in a set builder notation.
5. Let A = {+,-} and B = {00, 01, 10, 11}. obtain A x B.
6. How many subsets of {1, …; 10} contain at lowest seven elements?
7. What is a Coset?
8. What is a Ring?
9. If a, b, c are elements of a graph G and a*b=c*a, then b=c.

part B Marks five every

2. Let {G,*} be a group and a be an element of G. describe f:G?G by f(x) =a*x:

1. Prove that f is bijection.
2. On the basis of a, define a set of Bijecion on set of integers.

3. If {G,*} is cyclic, then it is abelian.

4. How Boolean Algebra is applicable in Logic Circuit? discuss with example.
5. obtain the generating function for the Fibonacci sequence.

6. Let A,B and C be sets, then:
A x (B n C) = (A x B) n (A x C).

part C Marks 10 every

7. Let A = {1, 2, 3, 4} and let r be he relation < on A. Draw the diagraph and Hasse diagram f r.

8. (a) What is a Quotient ring? discuss with example.
(b) Solve the subsequent recurrence relation:
s(k) – 10 s (k-1) +9 s (k-2) =0.
where s(0) = three and s(1) = 11.

9. (a) What is a congruence relation on semigroup? discuss.
(b) How many various reflexive, symmetric elations are there on a set with 3 elements?

Earning:   Approval pending.