BSc CS Sem 1 BSc CS Semester 1 (ATKT) 2017-18 ATKT Discrete Mathematics Question Paper - Mumbai University | munotes

Questions asked in this paper

• 2) Figures to the right indicate marks

1. Q3 Illustrations, in-depth answers and diagrams will be appreciated
2. Q4 Mixing of sub-questions is not allowed
3. Q1 Attempt the following questions (15M)
   • (a) Choose the best choice for the following questions (5M)
   • i) Let f: A > B be a function. Fis called function, if f(a) = f(b)
   • a) Bijective b) onto c) Injective d) None of these
   • ii) In how many ways 2 students can be chosen from the class of 20
   • iii) Let f and g be the function from the set of integers to itself, defined by f(x) = 2x + 1. and g(x) = 3x Then the composition of g is:
   • iv) A graph without loops and parallel edges is called as:
   • c) Multigraph d) None of these
   • v) A relation R on set X is such that (x, y) (y, z) R which implies (x, z) R then R is called
   • a) Reflexive b) Symmetric
   • (b) Fill in the blanks for the following questions (5M)
   • i) Let f: A> Band g: B> C be functions, f are said to be equal to each other if and only if
   • ii) Let R be a relation defined on set A. Ris Partial order Relation if and only if Ris Reflexive, Anti symmetric and
   • iii) Ifal, a2, be a sequence, then relation that relates ar to one or more previous terms of sequence is called
   • iv) If two.or more edges have same terminal vertices then these edges are
   • v) graph without any cycle is called a
   • (c) Answer the following questions (5M)
   • i) Let A= {1, 2,3}, the relation R A, is R transitive? Justify
   • ii) Defined the term Partial order Relations
   • iii) Find degree of Recurrence relation 2a, + = 5r+3
   • iv) circle centered (1, 1) and having radius 3 units. Is it a graph?
   • v) What is the degree of complete graph with 3 vertices
   • Q. P. Code: 30391
4. Q2 Attempt the following (Any THREE)(Each of 5Marks) (15M)
   • (a) Let f, be such that f(x) = x?- 2, = x + 4, h(x) = 5x,
   • (b) Let R be a relation on Z defined by xRy if and only if 5x + 6y is divisible by 11 for x, y Z. Show that R is an equivalence relation
   • (c) Let A = {1, 2, 3, 4, 12}. Let R be a partial order relation defined on A as aRb if and only of a/b. Draw the Hasse diagram of partial order relation R
   • (d) Find the solution of the recurrence relation an = 3 an-1 + 4 an-2; and
   • (e) Mr Sharma invests Rs 1,00,000/- to purchase land. Land cost increases 20% per year. What will be land cost after n years. Form recurrence
   • (f) If the function f: R — R defined as f(x) = (2x -3)/7 for every x R, then show stat f is bijective. Hence find
5. Q3 Attempt the following (Any THREE) (Each of 5Marks) (15M)
   • (a) How many different strings can be made by reordering the letters of the word
   • (b) Explain Addition and Multiplication principle of Counting
   • (c) 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 at least one year?
   • (d) Show that at a party of 20 people, there are two people who have same no of
   • (e) How many 3 digit numbers can be formed by using the 6 numbers 2, 3,
   • i) Repetition not allowed
   • ii) The number must contain the digit 5 and repetition allowed
   • (f) Let M be the finite state machine with the state table given the following
   • i) Find the input set A, the state set S, the output set Z, and the initial state of M
   • ii) Draw the state diagram D = D(M) of M
   • iii) Find the output word v if input is the word w =
   • Q. P. Code: 30391
6. Q4 Attempt the following (Any THREE) (Each of 5Marks) (15M)
   • (a) What is the value of the prefix expression 7234
   • (b) Define the terms related to graph
   • i) Adjacency
   • ii) Incidence
   • iv) Degree of Vertex
   • v) Pendant vertex
   • (c) Explain with example inserting and searching in Binary Search Tree
   • (d) Draw all possible simple graphs with 3 vertices
   • (e) Explain with the example In order, Pre Order, Post order Traversal of Tree
   • (f) Draw the graph represented by adjacency Matrix
7. Q5 Attempt the following (Any THREE) (Each of 5Marks) (15M)
   • (a) Let A = {1, 2, 3, 4}. Write an equivalence relation on A and write matrix of relation. Also draw the diagraph
   • (b) What is the coefficient of in the expansion (x + y)30?
   • (c) Consider the binary tree T
   • (d) Solve the non-homogeneous recurrence relation a; = 3 ar1 + 3 with ao = 1
   • (e) State and prove Pascal’s identity
   • (f) If 10 points are choosen within the equilateral triangle of side length3 . Prove that the selection includes at least 1 unit farthest apart from each other

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