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

Questions asked in this paper

1. Q2 All questions carry equal marks
2. Q1 Attempt the following (Any four) (20 M)
   • a. Prove that the function f: IR > R given by = a is a bijective. Hence find its
   • b. Let f(x) = g(x) = x —5 are the functions Find i) fog and gof
   • ii) fog(—2) and gof(4) i
   • c. = {1,2,3}, B = C = Consider the following relations R and S from A to B and B to C respectively
   • d. Let R be the relation on the set A = {2,4,8,16,32} where R = {(a,b):a | b} Draw the Hasse diagram
   • e. Solve the following linear homogeneous recurrence relation Show that i) az . ii) a3 =
3. Q2 Attempt the following (Any four) (20 M)
   • a. How many 4-digit codes can be formed using the digits 0 — 9 if
   • i) repetition of digit is not allowed
   • ii) repetition of digit is allowed
   • b. How many positive integers not exceeding 100 are divisible either by 4 or by 6? urn contains 15 balls out of which 8 are white and 7 are black. In how many ways can 5 balls be selected so that atmost 3 are black?
   • d. Prove that = + What is the coefficient of in the expansion (x + y +
   • f. Let M be the FSM defined by the following state table: Find i) states ii) input letters iii) Output letters initial state
   • v) f vi) draw the state diagram
4. Q3 Attempt the following (Any four) (20 M)
   • a. the adjacency structure for the following graph: VCD/ FYCS SEM I Discrete Mathematics 75 MARKS
   • b. Construct the tree from the algebraic expression:
   • c. Perform preorder, postorder and inorder search for the following tree:
   • d. Define path, cycle, trail witha suitable example
   • e. For the following graph apply BFS taking S as starting vertex Define terms related to graph
   • i) adjacent vertex ii) degree of a vertex pendent vertex
5. Q4 Attempt the following (Any five) (15 M)
   • a. Define partial order set and transitive
   • b. Show that a, = 1 is not a solution the of the recurrence relation dn = 8a,_, —
   • c. Define sum and product rule
   • d. In how many arrangement of the word LETTER contains the two T’s together?
   • e. Forma binary search tree for the following: The, hungry, rabbit, eats, quickly
   • f. Consider the FSA defined by the state diagram. Find its state table

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