Scribd
Upload
14 views2 pages

DM Assignment-II

The document outlines an assignment for a Discrete Mathematics class for B. Tech. I Year II Sem. A.Y:2024-25, consisting of various problems related to arrangements of letters, recurrence relations, graph theory, and algorithms. It includes tasks such as counting arrangements with restrictions, solving specific recurrence relations, and analyzing graph properties like isomorphism and spanning trees.

Uploaded by

Siddhartha Kolluri
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
14 views2 pages

DM Assignment-II

The document outlines an assignment for a Discrete Mathematics class for B. Tech. I Year II Sem. A.Y:2024-25, consisting of various problems related to arrangements of letters, recurrence relations, graph theory, and algorithms. It includes tasks such as counting arrangements with restrictions, solving specific recurrence relations, and analyzing graph properties like isomorphism and spanning trees.

Uploaded by

Siddhartha Kolluri
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

Subject: Discrete Mathematics Class: B. Tech. I Year II Sem. A.

Y:2024-25

Assignment –II

1 a. How many arrangements are there of MISSISSIPPI with no pair of consecutive letters the
same?
CO3, BTL4

b. Use the principle of inclusion exclusion to count the number of primes between 41 and 100
inclusive.
CO3, BTL4

c. How many arrangements of the 26 letters of the alphabet are there which contain none of the
patterns LEFT, TURN, SIGN, or CAR?
CO3, BTL4

2. a. Solve the recurrence relation an + an-1-16an-2+20a =0 for n ≥ 3 and a0=0, a1=1 and a2 = -1
n-3
using the Characteristic roots. CO3, BTL3
b. Solve the recurrence relation an – 3an-1 -10an-2 = 5n + 3. CO3, BTL3
c. Solve the recurrence relation an – 7an-1 +10an-2 = 7. 3n + 4n. CO3, BTL3

3. a. Suppose that A is the 2 X 2 matrix [ 30 −12 ]. For each integer n ≥ 1, find an expression for A n

using Recurrence relations. In particular give the numerical entries of A50. CO3, BTL4

b. √ an -√ an −1 - 2√ an −2 = 0 where a0 = a1 = 1. CO3, BTL4

c. Solve the following divide – and –conquer relation using a change of variable

an = 5an/2 + 4 where a1 = 0 and n = 2k for k ≥ 0. CO3, BTL4

4. a. Which of the following pairs of graphs are isomorphic?


i) ii)

CO4, BTL4
b. Give the Breadth First Search (BFS) and Depth First Search (DFS) spanning for the
following graphs

CO4, BTL3
c. Find the minimal spanning tree for the following graphs using Kruskal’s and Prim’s
algorithms.

CO4, BTL3
5. a. Which of the following graphs have Euler path, Euler circuit or neither?

CO4, BTL3
b. Find whether the following graphs have Hamiltonian cycles

CO4, BTL4
c. Determine the Chromatic number of each of the following graphs (Give a careful
argument to show that fewer colors will not suffice)

CO4, BTL4

You might also like