UNIT-4
1. Solve the recurrence relation using generating function a n-6an-1=0
for n≥1 wherea0=1
2. Solve the recurrence relation of Fibonacci series
3. Solve the following recurrence relation using characteristic roots
an +6an-1 + 8an-2 = 0 and a0 = 2, a1 = -7
4. Solve the recurrence relation an – 9a n-1 + 20an-2 = 0 with a0 = -
3,a1 = -10 using generating functions
5. Solve the following recurrence relation using generating functions
an -7an-1+10an-2=0, n ≥ 2 , a0 =10, a1 = 41
6. Solve the recurrence relation an-7an-1+12an-2 =0 for n≥2 where
a0=1, a1=2
7. Find the general expression for a solution to the recurrence relation
an-5an-1+6an-2 =n(n-1) for n≥2
8. Find the solution for the Fibonacci series an=an-1+an-2, n>2 and
a0=1, a1=1.
9. Solve the recurrence relation an - 7an-1 + 16an-2 - 12an-3 = 0 for n 3
with the initial conditions a0=1, a1=4, and a2=8.
10. Find the solution for an - 3an-1 - 4an-2 = 0 for n 2 and, a0 =
a1= 1
11. How many bit strings of length 10 contain: i) At most four 1‟s
ii) At least four 1‟s iii) Exactly four 1‟s.
12.There are 40 computer programmers for a job. 25 know Java, 28
know Oracle and 7 know neither language. Using principle of inclusion
exclusion find how many know both languages.
13.How many bit strings of length 10 contain: i) At most four 1‟s ii) At
least four 1‟s iii) Exactly four 1‟s. b) There are 40 computer programmers
for a job. 25 know Java, 28 know Oracle and 7 know neither language.
Using principle of inclusion exclusion find how many know both
languages.
14. Solve the recurrence relation 𝑎𝑛 − 𝑎𝑛−1 − 12𝑎𝑛−2= 0, 𝑎0=0, 𝑎1 = 1.
Unit-5
1. Define Cycle?Apply DFS algorithm to form the spanning tree by
taking own graph.
2. Explain the following
a. Isomorphism and sub graphs
b. Hamilton Paths
c. Planar Graphs
3. Write Kruskal’s Algorithm and explain it with an example. (
4. Prove that complete graph of 5 vertices is non planar.
5. Find the Chromatic number of the following graphs
(a) Complete Graph (K3)
(b) Complete Bipartite Graph (K2,3)
(c ) Regular Graphs (K3)
6.Find the chromatic number of the following i) Cn ii) Kn iii) Km,n
7.State and prove Euler’s formula for a plane connected graph.
8. Find the degree of each region in the following planar graph 2.
9. Show that the complete bi-partite graph K3, 3 is not planar graph.
10.Define spanning tree. Apply Prim’s algorithm to find minimum
spanning tree on the following weighted graph 4
11.State and prove fundamental theorem of graph theory.
12. Prove that a complete graph 𝐾𝑛 is planar if and only if 𝑛 ≤ 4.
UNIT-3
1. Prove by Mathematical induction that 6𝑛+2 + 72𝑛+1 is divisible by43
for each positive integer n.
2.
