BSc CS Sem 1 2022 2023 Dec 2023 DISCRETE MATHEMATICS Question Paper - Mumbai University | munotes

Questions asked in this paper

• (ii) Figures to the right indicate marks

1. Q1 Attempt any four of the following: 20 marks
   • a. Given A = {1,2,3,4} and B = {x, y,z}. Let R be the following relation from A to
   • (i) Determine the matrix of relation
   • (ii) Find the inverse relation of R
   • (iii) | Determine domain and range of R
   • b. Let A = {1,2,3,4,5} and R be partial order relation defined as Find Hasse diagram of poset A
   • c. Check whether the function f : R > R s.t. f(x) = 3x — 2 is bijective or not. yes find the inverse of f
   • (i) Find fog and gof
   • (ii) Find fog(5) and gof 7
   • e. Solve the following recurrence relation:
   • f. Formulate and solve Tower of Hanoi problem
2. Q2 Attempt any four of the following: 20 marks
   • a. How many 3 digit numbers can be formed using the digits 0 — 9 if
   • (1) Repetition of digits is allowed
   • (ii) Repetition of digits is not allowed : b. What is the coefficient of a b? c* in the expansion of (a + 2b —
   • c. How many minimum numbers must be selected from the set {1,2,3,4,5,6,7,8} to guarantee that atleast one pair of these numbers sums to 9?
   • d. Among 100 students, 55 students passed in Mathematics, 30 passed in Science and |> passed in both Mathematics and Science. How many students passed in
   • (ii) Only in Mathematics
   • e. Let G be the phase structure grammar where T = {a, b,c}, S is the starting symbol and productions are {S > a Sb,aS > c}. Find L(G)
   • f. State and prove Pascal’s identity
3. Q3 Attempt any four of the following: (20 a, Define binary search tree, complete binary tree and extended binary tree Discrete Mathematics-23 hrs-MARKS-75 \
   • b. Check whether the following 2 graphs are isomorphic or not. \
   • c. (i) What do you mean by chromatic number of a graph?
   • (ii) What is the chromatic number of graph on 5 vertices) and a complete
   • d. For the following graph, find the degree of all the vertices and the degree of graph
   • e. Traverse the following tree using pre order and post order algorithm
   • f. Determine the value of the expression
4. Q4 Attempt any three of the following: 15 marks
   • a. Formulate and solve recurrence relation representing number of regions in which plane is divided by n number of lines where no two lines are parallel and no three lines intersect at a common point
   • b. Let A be the set of lines in a plane. Define the relation R on A by aR bifand only if line a is parallel to line b. Show that R is an equivalence relation
   • c. In how many ways can a committee of 3 men and 2 women be chosen from 7 men
   • d. Consider the following state diagram of finite state automata. Find (a) states (b) input letters Initial State (d) accepting state (e) (f) Find State table
   • e. Define the following with examples (i) Isolated Vertex (i) Simple graph (iii) Regular
   • f. Represent the following expressions using binary tree :

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