BSc IT Sem I 2022 2023 2023 COMPUTATIONAL LOGIC AND DISCRETE STRUCTURE Question Paper - Mumbai University | munotes

Questions asked in this paper

1. Q1 Attempt any three of the following 15 marks
   • a) If R is equivalance relation in a set A then show that is also an equivalance relation
   • b) Prove by mathematical induction that 3 /(n? — n) for every positive integer
   • c) Find the number of positive integers from 1 to 100 which are not divigible by 2 or 3 or S ?
   • e) Apply Warshall’s algorithm for Transitive closure if A={a,b,c ,d,e}and
   • f) Define — i) Complement of set ii) Cartesian product iii) Power set iv) Proper subset v) Equality of
2. Q2 Attempt any three of the following 15 marks
   • a) Define the following terms — i) Surjective function ii) Injective function iii) Composite function
   • b) Let f : R — [4/5] defined by f(x) . then prove that f is bijective hence find the formula for
   • c) Let f, g and h are function from R to R defined as f(x) = 3x3 —7,g(x) = 2x* and
   • d) The odds are 3:2 against the person aged 60 years for 20 years The odds are 3:4 in favour of another 20 years Find the probability that 20 years hence i) at least one of these persons will be alive , ii) Exactly one will be alive
   • e) If P(A) = — , P(B) == , =2/5 ,Find P(B) , P (AUB) P(AN
   • f) The mean and variance of binomial distribution is 4 and 4/3 respectively, Find p(X 2) also
3. Q3 Attempt any three of the following 15 marks
   • a) State and prove pigeonhole principle also define Extended pigeonhole principle
   • b) How many different ways are there for eight men and five women to stand ina line so that no two women stand next to each other VCD FYIT SEM CLDS 75 MARKS 2% HRS ;
   • c) Suppose that a popular style of running shoe is available for both men and .The women shoe comes in size 6,7,8,9 and man’s shoe comes in size 8,9,10,11,12 . The man’s shoe comes in white and black . While the woman’s shoe comes in white ,red and black .Use a tree diagram to determine the number of different shoes that a store has to stock to have at least one pair of this type of running shoe for all available sizes and colours for both men and women
   • d) Find the number of minimum ways to choose 8 numbers from 1 to 50 so that all the choices have
   • e) Evaluate first seven terms of given recurrence relation = — = = 4
   • f) Solve the recurrence relation = + 5an-2 @, = 2,a2 = 6
4. Q4 Attempt any three of the following (15a)
   • a)Find the shortest path by applying Dijikstras algorithm
   • b) Check given graphs are or not
   • c) Check the following graphs are Eulerian graph, path, circuit and Hamiltonian graph and circuit
   • d) Use the nearest neighbour method to solve the travelling Salesman problem for the given graph VCD SEM -l CLDS 75 MARKS 2% HRS
   • e) Apply BFS and DFS algorithm on following graph
   • f) Define the following terms -i) Complete graph ii) Bipartite graph iii) Regular graph
5. Q5 Attempt any three of the following 15 marks
   • a) Define — i) Binary Tree ii) Sibling iii) Offspring iv) Complete binary tree v) Extended binary tree
   • b) Write the steps to draw sequential representation of binary memory sequential representation of following binary tree
   • c) Write pre order ,post order and inorder of the given algebraic expression
   • d) Define Hasse Diagram of a poset and draw Hasse digram with the help of relation A = {1,2,3,4,5 } Let arelation R On Z* as aR, if f alb then Prove that(Z* ,/) is poset
   • f) Let A = {1,2,------------8} be ordered in given graph Let B = {2,3,6} and C= {1,2,5 } Find Upper and Lower bound of BandC Find LUB (B) , GLB (B) ,GLB (C) also define Distributive lattice and Complemented lattice

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