Osmania University (OU) 2007 B.E Computer Science DISCRETE STRUCTURES - Question Paper

Code No. 4210/N FACULTY OF ENGINEERING

B.E. 2/4 (CSE) I Sem. Suppl. Examination May/June - 2008 Subject: Discrete Structures

Time : 3 hours ]    [Max. Marks : 75

	Note : Answer all questions of Part-A.
	Answer five questions from Part-B.
	PART - A (25 marks)
1.	How many circular arrangements are possible, if six people sit about a round
	table ?
2.	Prove that 7R is a valid conclusion from the premises P, P IQ, 7Q > 7R.
3.	LetA = {1, 2,3,4} and f:A-A defined by f = {(1,2), (2,2), (3,1), (4,3)}; find
	f3 and f4.
4.	If A={1, 2, 3, 4}, give an example of relation R on A that is reflexive and
	symmetric, but not transitive.
5.	Obtain the Generating Function of the Series 1,0,1,0,1,0,
6.	Define Recurrence Relations.
7.	Let the permutations of the elements of {1, 2, 3, 4, 5} be given by

	'1	2	3	4	51		(1	2	3	4 5
a =						p =
	,2	3	1	4	V		V1	2	3	5 4y

Solve the equation ax=p.

8.    Define group homomorphism.

9.    What is a Hamiltonian path ? Give an example.

10.    Draw self dual graph on four vertices.

11.    (a) For the following program segment, m and n are integer variables. The

variable A is a two-dimensional array A[l,l], A[l,2],... A[ 10,20], with 10 rows and 20 columns.

for m : = 1 to 10 do

for n : = 1 to 20 do

A[m,n]:=M+3*n

Write the following statements in symbolic form.

(i)    All entries of A are positive.

(ii)    All entries of A are positive and less than or equal to 70.

(m) Some of the entries of A exceed 60.

(iv) The entries in the first three rows of A are distinct.

(b) Agarwal has two unmarked containers, one holds 17 litres and other holds 55 litres . Explain how Agarwal uses these containers to measure exactly one litre.

12.    (a) Show that if 8 people are in a room, at least two of them have birthdays

that occur on same day of the week.

(b)    Let A be the set of factors of positive integer 120 and let < be the relation divides (i.e.) < = {(x,y)| x e A a y e A a (x divides y)}. Draw Masse diagram for < A, < >.

(c)    What is a partial order set ?

13.    (a) Solve Recurrence Relation

^a₊2^{5 a}n_+!+ K = ^{2 n} > ⁰ a₀ = 3, a, = 7

(b) A ship carries 48 flags, 12 each of the colors, red, white, blue and black. Twelve of these flags are placed on vertical pole in order to communicate a signal to other ships. How many of these signals use an even number of blue flags and an odd number of black flags ?

14.    (a) Compute the inverse of each element in Z₇ using fermats theorem.

(b) Prove that A code can detect all combinations of k or fewer errors if the minimum distance between any two code words is at least k + 1.

15. (a) State and prove Eulers theorem.

(b) Determine the chromatic polynomials for the given graphs.

If five colors are available in how many ways can the vertices be colored ?

16.    Devise a single-error correcting group code and associated decoding table when m=3 and n=7.

17.    (a) How many arrangements of letters in MISSISSIPPI have no pairs of

consecutive identical letters ?

(b) For any n eZ⁺, prove that the integers 8n+3 and 5n+2 are relatively prime.

C- 145/500

Attachment: osmania-university--ou--2007-b-e-computer-science-48044-1.pdf

Earning:   Approval pending.