DISCRETE STRUCTURES previous paper 1

Download FREE Computer Science Engineering (CSE Engg. Branch) Previous 5 Years solved Regular and Reappear Question Papers B.tech PTU (2007, 2006, 2005, 2004, 2003) and related Placement HR - Technical Interview Questions for subject DISCRETE STRUCTURES

DISCRETE STRUCTURES (New) CS 203/204 3rd / 4th Sem. May 2k5

Max Marks 60

Note: Section A is compulsory. Attempt any Four questions from Section B and two from Section C. Assume any missing data.

Section A Marks 2 each

1.

1. What is a subgraph?
2. What is a cycle in a graph?
3. What is the in degree of a graph?
4. Describe {3,5,7,9,……77,79} in a set builder notation.
5. Let A = {+,-} and B = {00, 01, 10, 11}. Find A x B.
6. How many subsets of {1, …; 10} contain at least 7 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.

Section B Marks 5 each

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

1. Prove that f is bijection.
2. On the basis of a, describe 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? Explain with example.
5. Find the generating function for the Fibonacci sequence.

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

Section C Marks 10 each

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? Explain with example.
(b) Solve the following recurrence relation:
s(k) – 10 s (k-1) +9 s (k-2) =0.
where s(0) = 3 and s(1) = 11.

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