BSc IT Sem I 2018 19 2018-19 DISCRETE MATHEMATICS Question Paper - Mumbai University | munotes

Questions asked in this paper

1. Q1 Attempt any three of the following: 15 marks
   • a. Define Universal Existential Statement Universal Statement. Give examples of each
   • b. Define Cartesian product. Let R denote the set of all real numbers. Describe R
   • c. Find the number of integers between | and 250 that are divisible by 2 or 3 or 5 or 7 Prove that (A N (AN B)' = U (B— A)
   • e. Write the negation of each of the following statements as simply as possible:
   • i. works, she will earn money
   • ii. He swims if and only if the water is warm ui. If it snows, then they do not drive the car
   • iv. John is 6 feet tall and he weighs at least 120 Kg
   • v. The train was late or Amol’s watch was slow
   • f. Define the following:
   • i. Argument, Premises
   • ii. Syllogism
2. Q2 Attempt any three of the following: 15 marks
   • a. Let Q(n) be “n is a factor of 8,” R(n) be “n is.a factor of 4,” and suppose the domain of n is Z+, the set of positive integers. Use the > and symbols to indicate true relationships among Q(n), R(n), and S(n)
   • b. Define necessary and sufficient conditions and only ifas applied to universal conditional statements. Rewrite the following statements as formal and informal quantified conditional statements. Do not use the word necessary or sufficient
3. Q1 Squareness is a sufficient condition for rectangularity li. Being at least 35 years old is a necessary condition for being President of the United States Cc. A college cafeteria line has four stations: salads, main courses, desserts, and beverages The salad station choice of green salad or fruit salad; the main course station offers spaghetti or fish; the dessert station offers pie or cake; and the beverage station offers milk, soda, or coffee. Three students, Uta, Tim, and Yuen, go through the line and make the following choices: Write each of following statements informally and find its truth value
   • i. J an item I such that V students S, S chose I
   • ii. J astudent S such that V items I, S chose I
   • iii. J a student S such that V stations Z, 4 an item I in Z such that S chose I
   • iv. V students S and V stations Z, an item I in Z such that S chose I
   • d. Define a prime number and composite number. Give symbolic definitions of the same Disprove the following by giving two counter examples:
   • i. For all real numbers a and b, ifa <b’ li. For all integers n, if n is odd then odd
   • iii. all integers mand n, if 2m +n is odd then mand n are both odd Define divisibility. Hence prove that for all integers a,b, and c, b c then
   • f. Use the quotient-remainder theorem with d = 3 to prove that the product of any three consecutive integers is divisible by 3. Use the mod notation to rewrite the result
4. Q3 Attempt any three of the following: 15 marks
   • a. i. Write the following as a single summation: li. Write the following as a single product:
   • iii. + = 2
   • v. Prove that for all nonnegative integers n and r withr + 1 <n, Prove that 72" + is divisible by 25 Vn N Determine the sequence whose recurrence relation is = + with
   • ii. Let F and G be functions from the set of all real numbers to itself. Define the product functions F-G: R R and F: R R as follows: For R,
   • i. Define Floor: R > Z by the formula Floor(x) = forall real numbers x e Is Floor one-to-one? Prove or give a counterexample e Is Floor onto? Prove or give a counterexample
   • ii. Let S be the set of all strings of 0’s and 1’s, and define 1(s) = the length of s, for all strings s in S e Is one-to-one? Prove or give a counterexample e Prove or give a counterexample Let {a, c, b}, Y= {x, y, z}, and Z = {u, v,w}. Define f: X Yand Zb the arrow diagrams below How (g and are related?
5. Q4 Attempt any three of the following: a Draw the directed graph for the following relations: 15 marks
   • ii. LetA= 6,7, 8} and define a relation R on A as follows: b Determine whether the following relations are reflexive, symmetric, transitive or none of these. Justify your answer the “greater than or equal to” relation on the set of real numbers: ui. Dis the relation defined on R as follows: Let R be the set of all real numbers and define a relation Ron R x R as follows: For all Is R a partial order relation? Prove or give a counterexample d Imagine that the diagram shown below is a map with countries labeled a—g. Is it possible to color the map with only three colors so that no two adjacent countries have the same color? To answer this question, draw and analyze a graph in which each country is represented by a vertex and two vertices are connected by an edge if, and only if, the e i. Find the adjacency matrix of the following graph: directed graphs that have the following adjacency matrix: f For the following either draw the graph as per the specifications or explain why no such
   • iv. Graph, connected, six vertices, five edges, has a nontrivial circuit
   • v. two vertices, one edge, not a tree
6. Q5 Attempt any three of the following: 15 marks
   • a. There are four bus lines between A and B and three bus lines between B and C. In how many ways can a man travel
   • i. by bus from A to C by way of B?
   • ii. — round-trip by bus from A to C by way of B? round-trip by bus from A to C by way of B if he does not want to use a bus line more than once?
   • b. 1. How many ways.can the letters of the word ALGORITHM be arranged in a How many ways can the letters of the word ALGORITHM be arranged in a row if L must remain together (in order) as a unit? many ways can three of the letters of the word ALGORITHM be selected and written in arow?
   • iv. How many ways can six of the letters of the word ALGORITHM be selected and written in a row if the first letter must be A? How many ways can the letters of the word ALGORITHM be arranged in a row if the letters GOR must remain together (in order) as a unit?
   • i. are selected from a standard 52-card deck, must 2 be of the same suit? Why? ll. If 5 cards are selected from a standard 52-card deck, must at least 2 be of the same suit? Why? ili. A small town has only 500 residents. Must there be 2 residents who have the same birthday? Why?
   • iv. Given any set of four integers, must there be two that have the same remainder when divided by 3? Why?
   • v. Given any set of three integers, must there be two that have the same remainder when divided by 3? Why?
   • d. i. How many distinguishable ways can the letters of the word HULLABALOO be arranged in order?
   • ii. How many distinguishable orderings of the letters of HULLABALOO begin with U and end with L?
   • iii. How many distinguishable orderings of the letters of HULLABALOO contain the two letters HU next to each other in order?
   • e. A bakery produces six different kinds of pastry, one of which is eclairs. Assume there are at least 20 pastries of each kind
   • i. How many different selections of twenty pastries are there?
   • ii. How many different selections of twenty pastries are there if at least three must ili. How many different selections of twenty pastries contain at most two eclairs?
   • f. A drug-screening test is used large population of people of whom 4% actually use drugs. Suppose that the false positive rate is 3% and the false negative rate is 2%. Thus a person who uses drugs tests positive for them 98% of the time, and a person who does not use drugs tests negative for them 97% of the time
   • i. What is the probability that.a randomly chosen person who tests positive for
   • ii. is the probability randomly chosen person who tests negative for drugs does not use drugs?

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