**(Time: 2 ½ Hours)**

**[Total Marks: 75]**

**N.B. 1) All questions are compulsory.**

**2) Figures to the right indicate marks.**

**3) Illustrations, in-depth answers, and diagrams will be appreciated.**

**4) Mixing of sub-questions is not allowed.**

____________________________________________________________________________________________________________________________

Q. 1) Answer the following questions. **(15M)**

A) Choose the best choice for the following questions.

i) If f_{1} and f_{2} are two functions from R to R such that f_{1}(x) = x^{2} and f_{2}(x) = x – x^{2}, then (f_{1}.f_{2}) (x) is given by

a) x^{3} + x^{4} b) x^{3} – x^{4}

c) x^{4} + x^{3} d) None of these

ii) Which of the following is true about the post (Z^{+},1)?

a) Zero is the least element b) one is the least element

c) There is no least element d) None of these

iii) A class contains 10 students with 6 men and 4 women. Number of ways to select a 4-members committee with 2 men and 2 women is given by

a) 60 b) 70 c) 80 d) 90

iv) Suppose a bookcase self has 5 History texts, 3 Sociology texts, 6 Anthropology texts, and 4 Psychology texts. Number of ways a student can choose one next of each type is given by

a) 300 b) 460 c) 560 d) 660

v) A loop is an edge connecting

a) a vertex with itself b) two distinct vertices

c) no vertices d) three distinct vertices.

B) Fill in the blanks for the following questions:

i) A function f is said to be strictly __________ if f(x) > f(y) for any x and y in the domain of f.

ii) A relation R on a set A is called _________ if (a, a) ∈ R for every element a ∈ A.

iii) The Gödel number of a word w =a_{3}a_{2}a_{1}a_{3}a_{4} is ___________

iv) Suppose that a procedure can be broken down into two tasks. If there are n_{1} ways to do the first task and n_{2} ways to do the second task after the first task has been done, then there are ________ ways to do the procedure.

v) Let G be a directed graph and v be a vertex of G. The number fo edges beginning at v) is called ____________.

C) Answer the following questions:

i) Why is f, defined by f (x) = 1/ (x+1), not a function from R to R?

ii) Let {an} be a sequence that satisfies the recurrence relation a_{n} = a_{n-1} + 2 for n = 1, 2, 3, ………… and suppose that a_{0} = 2. What are a_{1} and a_{2}?

iii) State inclusion-exclusion principle.

iv) Define a regular grammar.

v) Define a directed graph.

Q. 2) Answer any three of the following. **(15M)**

a) Find the domain and range of the following functions.

i) the function that assigns to each nonnegative integer it last digit.

ii) the function that assigns to a bit string the number fo bits the string.

b) Determine whether the function f from R to R defined by f (x) = x – 2 is bijective.

c) Suppose that R is the relation on the set of strings fo English letters such that aRb if and only if l(a) = l (b), where l(x) is the length of the string x. Is R an equivalence relation? Justify your answer.

d) Define Lattice. Determine whether that posets { 1, 2, 3, 4, 5 } and { 1, 2, 4, 8, 16} are lattices.

e) Solve the recurrence relations a_{n} = 5a_{n-1} – 6a_{n-2} for n ≥ 2, a_{0} = 1, a_{1} = 0

f) Define Fibonacci numbers. Formulate a recurrency relation for Fibonacci numbers.

Q. 3) Answer any three of the following. **(15M)**

a) How many ways are there for eight men and five women to stand in a line so that no two women stand next to each other?

b) State and prove Vandemonde’s identity.

c) State Pigeonhole principle. Form any set of 13 ntegers, prove that there will be at least one pair which leaves the same remainder when divisible by 12.

d) How many integers between 1 and 600 ( both inclusive ) are not divisible by both 3 and 5?

e) Define a language L over ran alphabet A. Let A = { a, b, c}. Find L* where language L ={ {b^{2}}

f) determine whether or not the automation M in the following figure accepts the words: w_{1} = ababba: w_{2}= baab; w_{3} = λ the empty word.

Q. 4) Answer any three of the following. **(15M)**

a) Consider the graph *G* in the following. Find

i) diam*(G)*, the diameter of* G*,

ii) *d(A, F)*, the distance from *A* to *F*.

b) Consider the graph *G* in the following figure (where the vertices are ordered alphabetically).

i) Find the adjacency structure of *G*

ii) find the order in which the vertices of G are processed using a depth-first search algorithm beginning at vertex *A.*

c) Draw the graph g corresponding to each adjacency matrix.

\begin{bmatrix}1&3&0&0\\3&0&1&1\\0&1&2&2\\0&1&2&0\end{bmatrix}

d) Consider the binary tree T in the following figure.

i) Find the depth d to T.

ii) Traverse T suing the post-order algorithm.

e) suppose a graph G contains two distinct paths from a vertex u to a vertex v. Show that G has a cycle.

f) Consider the binary tree T in the following figure. Describe the tree T after

i) the node M and

ii) the node D are deleted.

Q. 5) Answer any three of the following. **(15M)**

a) Draw the Hasse diagram for divisibility on the set { 1, 2, 3, 5, 7, 11, 13}.

b) How many solutions does the equation x+y+z= 11 have, where x, y, and z are non-negative integers with x ≤ 3, y ≤ 4, and z ≤ 6?

c) Draw all possible non-similar binary trees T with four external nodes.

d) Show that a_{n} = n.2^{n} is a solution fo the non-homogeneous linear recurrence relation a_{n} = 2a_{n-1} + 2^{n.}

e) what is the language generated by phase structure grammar G?

Login

Accessing this course requires a login. Please enter your credentials below!