Discrete Mathematical Structures — DU B.Sc. (Hons) Computer Science Previous Year Question Papers

Parts of a question must be answered together. (e) For the directed graph given below: 5 (i) Determine the outdegree of every vertex. (il) Give the incidence matrix representation. (d) Prove by contraposition that if n is an integer and 3n + 2 is odd, then n is odd. 5 (e) A drawer contains a dozen black socks and a dozen white socks, all unmatched. A man 5 takes socks out at random in the dark. (1) How many socks must he take out to be sure that he has at least two socks of the same color? (ii) How many socks must he take out to be sure that he has two black socks? (1) Let a be a numeric function such that 5 Determine S°a and 5-2a. 2. (a) Let A = (1,2,3, 4, 6, 8, 12, 24) and let R be the divisibility relation on A. 7 (i) Show that (A, R) is a POSET. (il) Draw the Hasse diagram. (iii) Find the maximal and minimal elements. (b) Show that the following argument is valid: 8 "If Priya attends the meeting, then she presents the report. If she presents the report, then the committee will be satisfied. If the committee is satisfied, then the project will be approved. Therefore, if Priya attends the meeting, the project will be approved." Using mathematical induction, prove that for every non-negative integer n: 7 (b) Let f: X → Y where X = (1,2, 3, 4, 5) and Y = (a, b, c, d, e] be defined by: 8 (i) Show that f is a bijection. (ii) Find f- and write it as a set of ordered pairs. (11l) Determine the image of the subset S = (1, 3, 5) under f. 4. (a) (i) Define planar graphs. Is Q3 planar? Justify. (11) Suppose that a connected planar graph has four vertices of degree 3, two vertices of degree 4, and five vertices of degree 2. Into how many regions does this representation divide the plane? (b) In a college, 300 students ate enrolled. Out of these, 90 have enrolled in Java, 150 in 8 Python and 70 in Ctt. Further, 40 have enrolled in both Java and Python, 30 in both Python and Ct+, and 25 in both Java and C++. There are 230 students that have enrolled in at least one of these three subjects. (i) How many students have enrolled in a course in all three subjects? (ii) How many students have not enrolled in any of the three subjects ? (iii) How many students opted for Python but not for Java? 5.. (a) . In how many ways can 20 different books be distributed among seven students so that: 7 (i) Five students would have 2 books each and the other two students would have 5 books each. (ii) Three particular students would get exactly 1 book each. (lili) One particular student does not get any book. (b) Evaluate 32ª mod 191 using the Fast Modular Exponentiation algorithm. 8 (a) Prove that a tree with n vertices has exactly n - 1 edges. 7 (b) (i) Show that p is tautologically implied by (pA),qV r, F using equivalence rules. (ii) State the converse, contrapositive, and inverse of the following statement: "If it snows today, I will ski tomorrow" 7. (a) Given the numeric functions a, and br 7 Determine the closed form of: