BSc.-Discrete Mathematics-Mumbai-April 2017
MUMBAI UNIVERSITY
Subject: Database Systems
Semesters: 1
(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 f1 and f2 are two functions from R to R such that f1(x) = x2 and f2(x) = x – x2, then (f1.f2) (x) is given by
a) x3 + x4 b) x3 – x4
c) x4 + x3 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 =a3a2a1a3a4 is ___________
iv) Suppose that a procedure can be broken down into two tasks. If there are n1 ways to do the first task and n2 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 an = an-1 + 2 for n = 1, 2, 3, ………… and suppose that a0 = 2. What are a1 and a2?
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 an = 5an-1 – 6an-2 for n ≥ 2, a0 = 1, a1 = 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 ={ {b2}
f) determine whether or not the automation M in the following figure accepts the words: w1 = ababba: w2= baab; w3 = λ 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 an = n.2n is a solution fo the non-homogeneous linear recurrence relation an = 2an-1 + 2n.
e) what is the language generated by phase structure grammar G?