Discrete Structure, Past Papers

Discrete Structure Past Paper 2015 – MSc IT 2nd Term UOS

Discrete Structure Past Paper 2015 MSc IT 2nd Term UOS – Page 1

University of Sargodha (UOS) M.Sc. IT 2nd term Discrete Structure (CMP-2111) past paper 2015 (both pages), with the full question paper in text form and step-by-step solved answers. All counting and summation answers are checked.

Discrete Structure Past Paper 2015 MSc IT 2nd Term UOS – Page 2
Page 2 of 2

Print / download (A4, high quality): Page 1 · Page 2

Discrete Structure Past Paper 2015 MSc IT (text version)

University of Sargodha – MSc (IT) 2nd Term Final Term 2015, Subject: Information Technology
Course: Discrete Structure (CMP-2111) · Time: 2:30 hours · Maximum marks: 80
Note: Objective part is compulsory. Attempt any four questions from the subjective part.

Objective part (compulsory)

  1. Write the converse of the statement p → q.
  2. If P(x): x > 3, what are the truth values of P(4) and P(2)?
  3. Briefly explain the types of quantifiers.
  4. Using a truth table, determine whether (¬q ∧ (p → q)) → ¬p is a tautology.
  5. Translate into English and determine its truth value: ∃x ∈ ℝ (x² = x).
  6. What are the quotient and remainder when 101 is divided by 11?
  7. What is the gcd of 45 and 60?
  8. Among any group of 367 people, there must be at least two with the same birthday. Why?
  9. Differentiate between permutation and combination with the help of an example.
  10. Differentiate between a function and a relation with an example.
  11. Differentiate between a simple graph and a multigraph with an example.
  12. Differentiate between a path and a circuit in a graph with the help of an example.
  13. Define a bipartite graph with the help of an example.
  14. Is this function onto? (Arrow diagram: domain {a, b, c}, codomain {1, 2, 3, 4}; a → 3, b → 4, c → 1.)
  15. If A = {1, 3, 5} and B = {1, 2, 3}, are A and B disjoint?
  16. Let {tₙ} be a sequence, where tₙ = 7 − 3n. What type of progression is this?

Subjective part (12 × 4)

Q2. (I) Use a proof by contraposition to show that if x + y ≥ 2, where x and y are real numbers, then x ≥ 1 or y ≥ 1. (II) Let T(x, y) mean that student x likes cuisine y, where the domain for x consists of all students at your school and the domain for y consists of all food. Express each of these statements by a simple English sentence: (a) ∀x ∃y ¬T(x, y) (b) ∃x T(x, Korean) ∧ ∀x T(x, Mexican)

Q3. (I) Let A = {a, b, c, d, e} and B = {a, b, c, d, e, f, g, h}. Find (a) B × A (b) A − B. (II) Solve the double summation Σi=02 Σj=03 i² j³.

Q4. (a) List the ordered pairs in the relations R₁ and R₂ from A = {0, 1, 2, 3, 4} to itself, where (a, b) ∈ R if and only if: (I) R₁ = {(a, b) | a > b} and R₂ = {(a, b) | a + b = 4}. (II) Find whether relation R₂ is reflexive, irreflexive, symmetric or anti-symmetric. (b) Let R and S be relations represented by the matrices MR = [0 1 0; 0 0 1; 1 1 0] and MS = [1 1 0; 1 0 1; 1 1 1]. Find the matrix that represents MR².

Q5. (I) Find the union of the given pair of simple graphs. (Graph 1: vertices a, b, c, d with edges a–b, a–c, a–d, b–c, b–d. Graph 2: vertices a, e, f, g, h with edges a–e, a–f, a–h, h–g, f–g.) (II) Construct a complete binary tree of height 3 and a complete 3-ary tree of height 2.

Q6. (I) How many bit strings of length 12 contain (a) exactly three 1s? (b) at most three 1s? (c) at least three 1s? (II) How many license plates can be made using either two letters followed by four digits or two digits followed by four letters?

Q7. (I) How many bit strings of length seven either begin with two 0s or end with three 1s? (II) How many positive integers less than 1000 (a) are not divisible by 7? (b) are divisible by both 7 and 11?

Original paper (scanned copy)

The clean paper above is retyped by Shining Study from this original University of Sargodha question paper. Click a scan to view it full size.

Discrete Structure Past Paper 2015 MSc IT 2nd Term UOS – original scanDiscrete Structure Past Paper 2015 MSc IT 2nd Term UOS – original scan

Solved answers

Objective part

1. Converse of p → q is q → p.

2. P(4): 4 > 3 is true. P(2): 2 > 3 is false.

3. Universal quantifier ∀x P(x): “P(x) is true for every x in the domain”. Existential quantifier ∃x P(x): “there is at least one x for which P(x) is true”. (Uniqueness quantifier ∃!x: exactly one such x.)

4.

pqp→q¬q¬q ∧ (p→q)¬p(¬q ∧ (p→q)) → ¬p
TTTFFFT
TFFTFFT
FTTFFTT
FFTTTTT

The last column is all T, so it is a tautology (this is modus tollens).

5. “There is a real number whose square equals itself.” True – x = 0 or x = 1.

6. 101 = 11 × 9 + 2, so quotient = 9, remainder = 2.

7. 45 = 3² × 5, 60 = 2² × 3 × 5, so gcd(45, 60) = 3 × 5 = 15.

8. By the pigeonhole principle: there are at most 366 possible birthdays (including 29 February). With 367 people (pigeons) and 366 days (holes), at least two people must share a birthday.

9. A permutation is an arrangement where order matters; a combination is a selection where order does not matter. From {A, B, C} choosing 2: permutations P(3,2) = 6 (AB, BA, AC, CA, BC, CB); combinations C(3,2) = 3 ({A,B}, {A,C}, {B,C}).

10. A relation from A to B is any subset of A × B. A function is a special relation in which every element of A is related to exactly one element of B. Example: {(1,a), (1,b), (2,a)} is a relation but not a function (1 has two images); {(1,a), (2,a)} is a function.

11. A simple graph has no loops and at most one edge between any pair of vertices. A multigraph allows multiple (parallel) edges between the same pair of vertices. Example: two cities joined by two different roads form a multigraph.

12. A path is a sequence of edges from one vertex to another (e.g. a–b–c). A circuit is a path that starts and ends at the same vertex (e.g. a–b–c–a). In a simple path/circuit no edge is repeated.

13. A graph is bipartite if its vertices can be split into two disjoint sets V₁ and V₂ so that every edge joins a vertex of V₁ to a vertex of V₂ (no edge inside a set). Example: C₄ with V₁ = {a, c}, V₂ = {b, d}; or K₂,₃.

14. Not onto. The domain has 3 elements and the codomain has 4, so at least one element (here 2) has no pre-image. The function is one-to-one, but not onto.

15. A ∩ B = {1, 3} ≠ ∅, so A and B are not disjoint.

16. t₁ = 4, t₂ = 1, t₃ = −2, … Each term is 3 less than the previous one, so it is an arithmetic progression with first term 4 and common difference −3.

Q2

(I) Proof by contraposition. Let p: x + y ≥ 2 and q: x ≥ 1 or y ≥ 1. We prove ¬q → ¬p. Assume ¬q: x < 1 and y < 1. Adding the two inequalities gives x + y < 1 + 1 = 2, i.e. ¬(x + y ≥ 2). So ¬q → ¬p is true, and therefore the original statement “if x + y ≥ 2 then x ≥ 1 or y ≥ 1” is true. ∎

(II) (a) ∀x ∃y ¬T(x, y): “Every student at your school has some food (cuisine) that he or she does not like.” (b) ∃x T(x, Korean) ∧ ∀x T(x, Mexican): “Some student at your school likes Korean food, and every student likes Mexican food.”

Q3

(I)(a) B × A = {(x, y) | x ∈ B, y ∈ A} has |B| × |A| = 8 × 5 = 40 ordered pairs:
(a,a), (a,b), (a,c), (a,d), (a,e), (b,a), (b,b), (b,c), (b,d), (b,e), (c,a), (c,b), (c,c), (c,d), (c,e), (d,a), (d,b), (d,c), (d,d), (d,e), (e,a), (e,b), (e,c), (e,d), (e,e), (f,a), (f,b), (f,c), (f,d), (f,e), (g,a), (g,b), (g,c), (g,d), (g,e), (h,a), (h,b), (h,c), (h,d), (h,e).

(b) A − B = elements of A not in B. Every element of A is in B, so A − B = ∅.

(II) The terms separate: Σi=02 Σj=03 i²j³ = (Σ i²)(Σ j³) = (0 + 1 + 4)(0 + 1 + 8 + 27) = 5 × 36 = 180.

Q4

(a)(I) R₁ = {(1,0), (2,0), (2,1), (3,0), (3,1), (3,2), (4,0), (4,1), (4,2), (4,3)} – 10 pairs.
R₂ = {(0,4), (1,3), (2,2), (3,1), (4,0)}.

(II) R₂ is not reflexive ((0,0) ∉ R₂); not irreflexive ((2,2) ∈ R₂); symmetric (a + b = 4 ⇒ b + a = 4, so every (a,b) has (b,a)); not anti-symmetric ((0,4) and (4,0) are both in R₂ with 0 ≠ 4).

(b) MR² = MR ⊙ MR (Boolean product: entry = OR of (row AND column)):

[0 1 0]   [0 1 0]   [0 0 1]
M_R^2 = [0 0 1] ⊙ [0 0 1] = [1 1 0]
        [1 1 0]   [1 1 0]   [0 1 1]

For example, row 1 = (0,1,0) picks row 2 of MR = (0,0,1); row 3 = (1,1,0) gives row 1 OR row 2 = (0,1,1). MS is not needed for this part.

Q5

(I) The union G₁ ∪ G₂ has vertex set V₁ ∪ V₂ = {a, b, c, d, e, f, g, h} and edge set E₁ ∪ E₂ = {ab, ac, ad, bc, bd, ae, af, ah, hg, fg} – 8 vertices and 10 edges. Vertex a is common, so the two graphs join at a (deg a = 6).

(II) A complete (full) binary tree of height 3 has every internal node with 2 children and all leaves at level 3: 1 + 2 + 4 + 8 = 15 vertices, 8 leaves. A complete 3-ary tree of height 2 has 1 + 3 + 9 = 13 vertices, 9 leaves.

Complete binary tree, height 3:
                 1
          /             \
        2                 3
      /   \             /   \
     4     5           6     7
    / \   / \         / \   / \
   8   9 10  11      12 13 14  15

Complete 3-ary tree, height 2:
                 1
        /        |        \
       2         3         4
     / | \     / | \     / | \
    5  6  7   8  9 10  11 12 13

Q6

(I)(a) Choose the 3 positions for 1s: C(12,3) = 220.
(b) At most three 1s: C(12,0) + C(12,1) + C(12,2) + C(12,3) = 1 + 12 + 66 + 220 = 299.
(c) At least three 1s = all strings − (zero, one or two 1s) = 2¹² − (1 + 12 + 66) = 4096 − 79 = 4017.

(II) Two letters + four digits: 26² × 10⁴ = 6,760,000. Two digits + four letters: 10² × 26⁴ = 45,697,600. The two forms cannot overlap, so by the sum rule total = 52,457,600 plates.

Q7

(I) Begin with 00: remaining 5 bits free → 2⁵ = 32. End with 111: first 4 bits free → 2⁴ = 16. Both (00 … 111): middle 2 bits free → 2² = 4. By inclusion–exclusion: 32 + 16 − 4 = 44.

(II) Positive integers less than 1000: 1 to 999.
(a) Divisible by 7: ⌊999/7⌋ = 142, so not divisible by 7: 999 − 142 = 857.
(b) Divisible by both 7 and 11 means divisible by lcm = 77: ⌊999/77⌋ = 12.

Answers prepared by Shining Study for revision. Check them against your class notes and teacher’s guidance.

About Saif R

An educator and technology enthusiast passionate about empowering students through quality education and digital learning. Dedicated to making academic resources and opportunities accessible to everyone.