Discrete Maths (DM) - Assignment No. 2

Q. 1: How many friends must you have to guarantee that atleast five of them will have

birthday in the same month.

Q. 2: Solve the recurrence relation

a. a r+2 -a r+1 -6a r =4.

b. a n =6a n-1 +11a n-2 -6a n-3 given a 0 =20, a 1 =5 and a 2 =15.

Q. 3:

a. Consider Group G={1,2,3,4,5,6) under multiplication modulo 7 find

multiplication modulo 7.

b. Let G be the set of rational numbers other than 1. Lets define an operation *

on G by a*b=a+b-ab for all a,b c. Prove that (G,*) is a group.

Q. 4: Let H be a parity check matrix, determine the group code e H : B3->B 6 .

H = 1 0 0

0 1 1

1 1 1

1 0 0

0 1 0

0 0 1

Q. 5: Prove that a connected graph G is an Eulerian graph if and only if all vertices of G are

of even degree.

Q. 6: What is Travelling Salesperson Problem? How is it solved?

Solution for DM assignment 2 is given below.

Engineering Needz