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

DiscRETE STRUCTURES CS 204 fourth Sem. May 2k5

Max Marks 60

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.

1. obtain 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 actual or FALSE, justify.
3. What is the difference ranging from 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. obtain the number k of people who owned both a station wagon and a few other car.
5. Let X ={a, b} and Y={1, 2, 3}. obtain 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 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:

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

Earning:   Approval pending.