BSc.-Discrete Mathematics-Mumbai-April 2019
MUMBAI UNIVERSITY
Subjects: Discrete Mathematics
Semester: 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) Attempt All ( Each of 5 Marks ) (15M)
a) Select the correct answer from the following.
1) A relation R on a set A is said to be ____________ if aRb, bRc and aRc for all a, b, c, ∈ A.
a) Reflexive b) Symmetric c) Transitive d) Antisymmetric
2) The value of P(3,3)= __________
a) 6 b) 9 c) 8 d) 5
3) Two vertices V1 and V2 in a graph G are said to be ___________ to each other if they are the end vertices of the same edge e.
a) Adjacent b) Parallel c) loops d) None
4) In ___________ ways 8 different beads can be arranged to form a necklace.
a) 8! b) 7! c) 9! d) None
5) Diagrammatic representation of relation R defined on a set is called __________
a) Diagraph b) Multigraph c) Hasse diagram d) None
B) Fill in the blanks.
( Indegree, 45, 21, 35, increase, Lattice, POSET, Injective, Surjective )
1) A Set together with a partial order relation is called ___________
2) An onto function is called as _____________ function.
3) The number of incoming edges on a vertex v is called ___________ of a vertex.
4) The value of C ( 10, 8 )= __________
5) In __________ ways 4 questions can be selected form 7 questions.
C) Define the following.
1) Equivalence Relation
2) Recyrrebce relation
3) Simple graph
4) Pigeonhole principle
5) Pascal identity
Q. 2) Attempt the following (Any THREE) (15M)
a) IF f: R → R is defined by f\left(x\right)=\frac{\left(2x-3\right)}7, for all x∈R, then show that f is a bijective function.
b) Define composition function . If f and g are two functions from the set of integers to the set of integers defined by f(x)= x +3 smf g(x) = x2 then find fog(x) and gof(x).
c) Define equivalence relation and let R= {(1,1), (1,3),(2,2),(2,4),(3,3),(3,1),(4,4),(4,2) be the relation defined on A= { 1,2,3,4 }. Show that R is an equivalence relation.
d) Descirbe the order pairs in the relation determined by the Hasse diagram of a poset (A, ≤) on the set A = { 1,2,3,4 }
e) Solve the recurrence relation an = an+1+2an-2, n≥ 2 with initial conditions ao=1, a1=1 using characteristic root method.
f) Explain Tower of Hanoi and solve the puzzle.
Q. 3) Attempt the following (Any THREE) (15M)
a) Prove that
i) C(n,0)=1 ii) C(n,1)=n iii) C(n, n)=1 iv) C(n, r)=C(n, n-r)
b) How many distinguishable permutations of the letters in the world SCIENCE are there?
c) Draw a tree diagram to find how many bit strings of length four do not have two consecutive I s.
d) A class is composed of 2 brothers and 6 other boys. In how many ways can all boys be seated at a round table so that the two brothers are not seated together?
e) Let L= { a, ab, a2 } and M= {b2, aba } be languages over A = { a, b } Find i) LM ii) MM
f) Find the language L(G) over {a, b, c} generated by the grammar G with productions S-→ aSb, aS→Aa, Aab→ c.
Q. 4) Attempt the following ( Any THREE ) (15M)
a) Define adjacency matrix and Draw the undirected graph G corresponding to given adjacency matrix.
A=\begin{bmatrix}\;1&2&0&0\\3&0&1&1\\0&1&2&2\\0&1&1&0\end{bmatrix}b) What is a planar graph? Draw a planar graph representation of the given graph.
c) Explain the operations on graph also find union and intersection of the given graphs.
d) Use Depth-first search algorithm to find a spanning tree for the given graph.
e) What is tree traversal and Find preorder, postorder and inorder search for the given tree.
f) Determine the value of the expression represented in a binary tree.
Q. 5) Attempt the following (Any THREE) (15M)
a) If A= {1,2,3} and R be relation on A defined by xRy such that x≤y. Find R and draw its digraph.
b) Using generating function solve the recurrence relation an=3 an-1 +2 with initial condition a0=1
c) What is the probability that a randomly selected number that is between 100 and 999 (both inclusive) will not contain the digit 7?
d) What is a Complete graph. Draw a regular graph with 5 vertices
e) Consider the language L+{ ab, c } over A= {a, b, c}, Find : a) L3, b) L-2