Course Title: Discrete Structures for Computer Science $($BSDCBZC$222)$

Assignment II:

Instruction: All answers must be in your own handwriting.

Total marks: $10$

Q$1.$ Find the generating function of the sequence $\{a_n\},$ where $a_n$ satisfies the recurrence relation $a_n-8a_{n-1}-5=0,n1,a_0=5.$ Hence obtain the solution of the recurrence relation.

$(2$ marks$)$

Q$2.$ Solve the recurrence relation $F_n=20F_{n-1}-25F_{n-2}$ with initial condition $F_0=4$ and $F_1=14.$

$(2$ marks$)$

Q$3.$ Test whether the following graph is bipartite. If it is bipartite, then find the bipartition.

$(2$ marks$)$

Q$4.$ Examine whether the following graphs are isomorphic. If they are isomorphic, then find the isomorphism between them.

$(2$ marks$)$

$1$

Q$5.$ Find the adjacency matrix $M$ of the following graph. Find $M^3$ and hence deduce the number of different paths of length $3$ between the vertices $v2$ and $v3$ of the following graph:

$(2$ marks$)$