DISCRETE STRUCTURES previous paper 2

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 CS 204 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. Find the number of distinct permutations that can be formed from all the letters of the word UNUSUAL.
2. A 2-chromatic graph must be a tree. Is the statement TRUE or FALSE, justify.
3. What is the difference between walk and paths in graphs?
4. A sample of 80 car owners revealed that 24 owned station wagons and 62 owned cars which are not station wagons. Find the number k of people who owned both a station wagon and some other car.
5. Let X ={a, b} and Y={1, 2, 3}. Find the number n of functions for Y into X.
6. What is a bijective function?
7. What is monoid?
8. Show that (a-1)-1 = a for any element in a Group G.
9. What that {0} is an ideal in any ring R.
10. Consider the character set given by {a, b, c}. How many 4 lett4er word are possible where any character can e repeated any number of times.

Section B Marks 5 each

2. The students in a hostel were asked whether they had a dictionary (D) or a thesaurus (T) in their rooms. The results showed that 650 students had a dictionary, 150 did not have a dictionary. 175 had thesaurus and 50 neither a dictionary nor a thesaurus. Find the number k of students who:
(a) Live in the Hostel.
(b) Have both dictionary and a thesaurus.

3. How many different words can be formed with the letters of the word “BHARAT” ? In how may of these B and H are never together. How many of these words begin with B and end with T?

4. Let S = N x N. Let * be the operation on S defined by (a’, b’)=(a+ a’, b + b’)
(a) Show that S is a semigroup.
(b) Define f: (S,*)→(Z,+) by f(a, ) =a-b.
Show that f is a homomorphism.

5. Suppose J and K are ideals in a ring R. Prove hat J ∩ K is an ideal in R.

6. Prove that a graph G with n vertices, n-1 edges and no circuits is connected.

Section C Marks 10 each

7. Let G be a finite graph with n> 1 vertices. Prove that then the following statements are equivalent.
(a) G is a tree
(b) G is cycle-free and has n-1 edges.
(c) G is connected and has n-1 edges.

8. Let E = xy’ = xyz’ + r’yz’, prove that
(a) xz’ + E = E
(b) x+ E ≠E
(c) z’ + E ≠E

9. Discuss the following with a suitable example:

1. Ideals
2. Integral Domain
3. Fields
4. Euclidian Domain
5. Integral Domains.