Discrete Structures Question Paper of 3rd Semester CSE74 Download Previous Years Question Paper 2

December-2003

CS-203/204

DISCRETE STRUCTURES

B.Tech. 3^rd Semester-2123

Note: Section –A is compulsory. Attempt any four question from section-B.A attempt any two questions from section –C.

Section –A

1.       

a.     Differentiate between a directed and undirected graph.

b.     Define a simple path and a trail in a graph.

c.      What is a trivial graph?

d.     Define isomorphic graph.

e.      Explain the fundamental principle of counting.

f.       State inclusion and Exclusion principle.

g.     What is a ring?

h.     What are cosets? Explain langrage’s theorem.

i.       What is meant by tautology?

j.       What is a power set?

Section –B

2.     Consider four vowels and eight consonants. Find the number m of five letter words containing two different vowels  and three different consonants that can be formed from the given letters.

3.     Let A,B,C be arbitrary sets, prove that A-(B-C)=A-(B U C)

4.     If an undirected graph which is connected and has zero or exactly 2 vertices of odd degree. Show that it has an Euler path.

5.     Let S be a semi group with an identity element e and suppose b and b’ are inverse of an element a in S, show that b =b

6.     What are rings, integral domains and fields? State each o them with an example

Section –C

7.     Prove that if A,B,C,D are arbitrary sets, then

8.     What is an Eulerian circuit? Prove that an undirected graph G possesses an Eulerian circuit if and only if it is connected and its vertices are all of even degree.

9.     Let E = xy+ xyz +x’yz. Prove that xz’ + E=E