Punjab Technical University 2005-4th Sem B.Tech Computer Science and Engineering DISCRETE STRUCTURES CS 204 2k5 - Question Paper

Note: part A is compulsory. Attempt any 4 ques. from part B and 2 from part C. presume any missing data.

part A Marks two every

1.

a.Find the number of distinct permutations that can be formed from all the letters of the word UNUSUAL.
b.A 2-chromatic graph must be a tree. Is the statement actual or FALSE, justify.
c.What is the difference ranging from walk and paths in graphs?
d.A sample of 80 car owners revealed that 24 owned station wagons and 62 owned cars which are not station wagons. obtain the number k of people who owned both a station wagon and a few other car.
e.Let X ={a, b} and Y={1, 2, 3}. obtain the number n of functions for Y into X.
f.What is a bijective function?
g.What is monoid?
h.Show that (a-1)-1 = a for any element in a Group G.
i.What that {0} is an ideal in any ring R.
j.Consider the character set provided by {a, b, c}. How many four lett4er word are possible where any character can e repeated any number of times.
part B Marks five every

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

3. How many various 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 start with B and end with T?

4. Let S = N x N. Let * be the operation on S described by (a’, b’)=(a+ a’, b + b’)
(a) Show that S is a semigroup.
(b) describe 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 n K is an ideal in R.

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

part C Marks 10 every

7. Let G be a finite graph with n> one vertices. Prove that then the subsequent 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. explain the subsequent with a suitable example:

Ideals
Integral Domain
Fields
Euclidian Domain
Integral Domains.

Earning:   Approval pending.