BSc CS Sem 1 BSc CS Semester 1 (2017 2018) 2018 Descrete Maths 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 Answer the following questions (15M)
   • (a) Choose the best choice for the following questions: (5M)
   • (i) A function f from R to R which satisfies f(a) = f(b) implies a=b for every a and b in R is said to be
   • (a) One-to-one function (b) onto function
   • (c) Either one-to-one or onto function None of these Gi) R on a set such that whenever (x, y) R, (y, x) R, then R
   • (a) Reflexive (b) Symmetric
   • (c) Transitive (d) None of these
   • (iii) What is the coefficient of x? in the expansion of (x +y)*:
   • (a) 4 (b) 6 (d) None of these
   • (iv) Suppose a bookcase shelf has 5 Physics texts, 3 Chemistry texts, 6 Biology texts, and 4 Mathematics texts. Number of ways a student can choose one text of each type is given by
   • (a) 660 (b) 560 (c) 460 (d) None of these
   • (v) Anundirected graph with no multiple edges or loops is called
   • (b) Fillin the blanks for the following questions: (5M) function f such that f(x) = x for any x in the domain of f is said to be a
   • (iii) number of a word w = is
   • (iv) number of different license plates that can be made if each plate contains a sequence of three uppercase English letters followed by three digits is given by
   • (v) Let G be a directed graph and v be a vertex of G. The number of edges ending at v is called
   • Q.P.Code: 12212
   • (c) Answer the following questions: (5M)
   • (i) the domain of the function f(x) = x+1 is R, what will be its co-domain?
   • (ii) Let S be a set. Determine whether there is a greatest element and a least element in the poset (P(S), S)
   • (iii) How many ways are there to select a first-prize winner, a second-prize winner, and a third-prize winner from 100 different people who have entered
   • (iv) Define a regular grammar
   • (v) What is the degree of a vertex of n undirected graph? Answer any three of the following: (15M)
   • (a) Determine whether the function f: R-> R given by f(x) = -3x + 4 bijection
   • (b) Find the domain and range of following functions:
   • (i) The function that assigns to each positive integer the number of the digits 0,1,2,3,4,5,6, that do not appear as decimal digits of the integer
   • (ii) The function that assigns to a~ bit the numerical value 0 to a bit string consisting of all Os
   • (c) Draw the Hasse diagram representing the partial ordering {(a,b) divides b} on
   • (d) Which of these relations on {0, are partial orderings?
   • (e) Find a recurrence relation and give initial conditions for the number of bit strings of length n that do not have two consecutive 0
   • (f) Find the solution of the recurrence relation an = with ao =2 and =7 Answer any three of the following: (15M)
   • (a) _How many permutations of the letters ABCDEFG contain:
   • (i) The string BCD?
   • (ii) The string CFGA?
   • (ii) The strings BA and GF?
   • (iv) The strings ABC and DE?
   • (v) The strings ABC and CDE?
   • (b) State and prove Pascal identity
   • (c) State Pigeonhole principle. A chess player has 77 days to prepare for an important tournament. He decides to practice by playing at least one game per day and a total of 132 games. Show that there is a succession of days during which he must have
   • (d) Suppose that there are nine students in a discrete mathematics class at a small
   • (i) Show that the class must have at least five male students or at least five female
   • (ii) Show that the class must have at least three male students or at least seven
   • Q.P.Code: 12212
   • (e) Construct a derivation tree for the following derivation: the hungry rabbit eats quickly
   • (f) Find the output string generated by the finite-state machine given below if the input string is 101011
3. Q4 Answer any three of the following: (15M)
   • (a) Find the degree and neighborhood of each of the vertex of the graph given below:
   • (b) Suppose a graph G contains two distinct paths from a vertex u to a vertex v. Show that G has a cycle
   • (c) Draw the graph corresponding to the following adjacency matrix:
   • (d) Represent the following expressions using binary tree:
   • (e) Draw all possible non similar binary trees T with four external nodes
   • (f) Determine the order in which a preorder traversal visits the vertices of the following ordered rooted tree:
   • Q.P.Code: 12212
4. Q5 Answer any three of the following: (15M)
   • (a) Let R be the relation on the set of all people who have visited a particular Web page such that xRy if and only if person x and person y have followed the same set of links starting at a particular Web page. Show that R is an equivalence relation
   • (b) Find the solution of the recurrence relation an = 9an — 2 with initial conditions ao =1 and a; =6
   • (c) What is the coefficient of in the expansion using binomial theorem
   • (d) Define a language L over an alphabet A. Let A= {a, b, c}. Find L* where language
   • (e) Find the in-degree and out-degree of each vertex in the graph shown:
   • (f) Consider the graph G in the following figure (where the vertices are ordered alphabetically). (i) Find the adjacency structure of G. (ii) Find the order in which the vertices of G are processed using a Breadth-first search algorithm beginning at

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