BSc Mathematics SEM I 2019 20 Nov 2019-20 MATHS DISCRETE MATHEMATICS Question Paper - Mumbai University | munotes

Questions asked in this paper

• ii) Figures to the right indicate marks,

1. Q1 Attempt all (each of 5 marks) 15 marks
   • a) Choose the best choice for the following questions :
   • 1) Which of the following are defined if f is a function from A to B and g is a function
   • a) fog but not gof b) both gof and fog gof but not fog d) neither fog nor gof
   • ii) Let {an} be a Sequence such that for ay = 2. What are a; &
   • a)Sand8 respectively b) 3 and 5 respectively
   • C) 5 respectively d) 5 and 3 respectively
   • iii) The value of P (10, 2 ) is
   • a) 180 b) 45 c) 90 d) none of these
   • iv) Which of the following types of grammar has no restrictions on its productions?
   • v) A graph with multiple edges but no loose is called a
   • b) Fill in the blanks . Use following pool to answer the questions, 5
   • i) A one one function is
   • ii) Coefficient of x2 y’ in the expansion of (x+y) 4 is
   • iii) A graph in which degree of every vertex is same is called graph
   • iv) A relation which is reflexive , antsymmetric & transitive is called the number of different license plates that can be formed if each plate a sequence of 2 capital letter followed by sequence of 2 digits
   • c) Define the following: 5
   • 1. Pendant vertex
   • 5. Regular grammar Attempt the following (any 3) (15)
   • a) Consider the relation R = { (1,1) (2,1), (2,3), (3, 4), on A {1,2,3,4}. Draw its directed graph and find matrix of R
   • b) Show that a function f : R-R defined by lijective . Hence, find r: Solve the recurrence relation a, 2a n-2 for all n > 2, whether
   • d) Determine whether the relation of R = (4,2 ) } on set A~{1 , symmetric and transitive . Justify Define composition of 2 functions. If f and g are two functions from set of integers to set of integers defined by & (x) then find fog (x) and gof (x)
   • f) Describe Tower of Hanoi puzzle. Formulate and solve the recurrence relation for it Attempt the following (any 3) (15)
   • a) State and prove Pascal’s identity
   • b) How many words can be formed using all the letter of the word MATHEMATICS 9
   • c) State pigeonhole principal. Show that if any six numbers from the set } are chosen , Then two of them will add upto 11
   • d) Among 100 Students, 55 students got distinction in first year , 30 got distinction in second year , 15 got distinction in both years. Then, how Many students got distinction in
   • 1. at least one year 2. Only first year only second year Construct a derivation tree for following sentence ‘A scared mouse runs quickly’
   • f) Let G be a grammar where V = {s,o, 1} T={0,1}, starting symbol S and set of production
2. Q4 Attempt the following (any 3 ) 15 marks
   • a) Define adjacency matrix. Draw the undirected graph G corresponding to given adjacency
   • b) Find in degree and out degree of each vertex in the given graph What is a complete graph ? Draw 4 complete graph with 5 vertices . Give an example of a graph which is regular but not complete,
   • d) Consider the binary tree T in the following figure. Traverse Tin a) preorder b) inorder Represent the following using binary tree
   • f) Use depth first Search algorithm to find a spanning tree for the given graph
3. Q5 Attempt the following (any 3) 15 marks
   • a) Describe the ordered pairs in the relation R determined by the Hasse diagram of poset (A , < ) on the set A={1,2,3,4,5}
   • b) Solve the recurrence relation a, with initial condition a = 2 , using
   • c) Draw all possible non similar binary tree T with 3 nodes
   • d) There are 6 men and 7 women ina group. How many different committee should have 2 men Let M bé the finite state machine with state table as given below
   • 1) Find input set A , the state set S, the output set Z, the initial state
   • 2) Draw the state diagram of M

Read from the scan above, so a character or two may differ. The scan is the original.