Course Title : Advanced Discrete Mathematics
Assignment Number : MCA(3)/033/Assign/2014-15
Maximum Marks : 100
Weightage : 25%
Last Dates for Submission : 15th October, 2014 (For July 2014 Session)
15th April, 2015 (For January 2015 Session)
DOWNLOAD SOLVED ASSIGNMENT
Q.1. Define each of the following concepts from graph theory and give one suitable example for the concept:
i) Complete graph ii) Path
iii) Cycle iv) Subgraph
v) Complement of a graph
vi) Connected components of
a graph
vii) Bipartite viii) Spanning
ix) Vertex cut-set x) Eulerian curcit
xi) Eulerian graph xii) Hamiltonian graph
xiii) Open trail xiv) Edge traceable graph
xv) Biapartite graph
Q.2. A person deposits Rs. 250, 000/-in a bank in a saving bank account at a rate of 8 % per annum. Let Pn be the amount payable after n years, set up a recurrence relation to model the problem. Also using the recurrence relation, find amount payable after 9 years.
Q.3. For each of the following recurrences, find its order and degree and
also tell whether it is homogeneous or non-homogeneous
i) an = an-1 + an-2 + … + a0
ii) an = nan-2 + 2n
iii) an = √an –1 + (a n –2)29
iv) an = (an–1)
2+ an-2 an-3 an-4
v) an = sin an-1 + cos an-2 + sin an-3 + …+ an
vi) bn = bn – 1 + (n + 3)
vii) an = an –1 a1 + an – 2 a2 + ……+ a1 an – 1 (for n 2)
Q.4. The following recurrence equation represents the Tower of Hanoi
problem:
Cn = 2 Cn– 1 + 1 (for n 2) and C1 =1
Verify, using Principle of Mathematical Induction that Cn = 2n– 1.
Q.5. Find generating function for each of the following sequences:
i) (4, 12,36, 108, 384,…….)
ii) (1, 5 k(k+1)/2, 25 k(k+1)(k+2)/6, 125k(k+1)(k+2) (k+3)/24, …… )
Q.6. Find the sequence with each of the following functions as its
exponential generating function:
i) f (x) = 5x3x
ii) f (x) = (2 – x ) + e 3x
Q.7. What is the solution of the recurrence relation an = 2an – 1 + 3an–2 with a0 = 5 and a1 = 8?
Q.8. Find all solutions of the recurrence relation an = 5 an – 1 + 3n. What is the solution with a1 = 9?
Q.9. Find all solutions of the recurrence relation
an = 5an– 1 – 6an –2 + 7
Author Name
Author Description!
Get Free Email Updates to your Inbox!
