Discrete Structure, Past Papers

Discrete Structure Past Paper 2018 – BSCS 2nd Term UOS

Discrete Structure Past Paper 2018 BSCS 2nd Term UOS

University of Sargodha (UOS) BS Computer Science 2nd term Discrete Structure (CMP-2111) past paper 2018, with the full question paper in text form and step-by-step solved answers, including proofs, the binary search tree and the Venn diagram problem.

Print / download (A4, high quality): Full-size paper

Discrete Structure Past Paper 2018 BSCS (text version)

University of Sargodha – BS 2nd Term Examination 2018, Subject: Computer Science
Paper: Discrete Structure (CMP-2111) · Time: 2:30 Hours · Maximum marks: 80

Objective part – Q1: Write short answers of the following in 2-3 lines each on your answer sheet. (16*2)

  1. Construct a truth table for p ⊕ (p ∨ q).
  2. Define Existential quantifier.
  3. Determine the truth value of following statement if the domain consists of all real numbers ∃x(x4 < x2)
  4. Define Idempotent Law for sets.
  5. Differentiate between proposition and predicate with example.
  6. How many different elements does A × B × C have if A has m elements, B has n elements, and C has p elements?
  7. Determine whether the function f from {a, b, c, d} to {1, 2, 3, 4, 5} with f(a) = 4, f(b) = 5, f(c) = 1, and f(d) = 3 is one-to-one.
  8. Let A = {1,2,3,4}, and R is a relation defined by “a divides b”. Write R as a set of ordered pair, draw directed graph.
  9. Define the term Halting Problem.
  10. How many comparisons are needed for a binary search in a set of 64 elements?
  11. Convert the octal expansion of (1604)8 integers to a binary expansion.
  12. What is pigeonhole principle?
  13. Define reflexive closure and symmetric closure.
  14. What is a recurrence relation?
  15. A bag contains 6 white, 5 black and 4 red balls. Find the probability of getting a white or a black ball in a single draw
  16. What is cyclic graph? Give an example of cyclic graph.

Subjective part (3*16)

Attempt any three questions out of five questions

Q2. Prove that following are logically equivalent by developing a series of logically equivalences.
  i. ¬p → (q → r) and q → (p ∨ r)
  ii. p ↔ q and ¬p ↔ ¬q

Q3. Describe an algorithm based on the linear search for determining the correct position in which to insert a new element in an already sorted list.

Q4. (a) Show that the premises “It is not sunny this afternoon and it is colder than yesterday,” “We will go swimming only if it is sunny,” “If we do not go swimming, then we will take a canoe trip,” and “If we take a canoe trip, then we will be home by sunset” lead to the conclusion “We will be home by sunset.”
(b) Define f: R → R by the rule f(x) = 4x − 1 for all x ∈ R. Is f onto? Prove or give a counter example.

Q5. Draw a binary search tree by inserting the following numbers from left to right.

11, 6, 8, 19, 4, 10, 5, 17, 43, 49, 31
Determine the order, in which the vertices of the following binary trees will be visited under
  i. Preorder traversal.      ii. Inorder traversal.      iii. Postorder traversal.

Q6. In a school, 100 students have access to three software packages, A, B and C. 28 did not use any software, 8 used only packages A, 26 used only packages B, 7 used only packages C, 10 used all three packages, 13 used both A and B.
  i. Draw a Venn diagram with all sets enumerated as for as possible. Label the two subsets which cannot be enumerated as x and y, in any order.
  ii. If twice as many students used package B as package A, write down a pair of simultaneous equations in x and y.
  iii. Solve these equations to find x and y.
  iv. How many students used package C?

Original paper (scanned copy)

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

Discrete Structure Past Paper 2018 BSCS 2nd Term UOS – original scan

Solved answers

Q1 – Short questions

(i)

pqp ∨ qp ⊕ (p ∨ q)
TTTF
TFTF
FTTT
FFFF

(The result is true only when p is false and q is true, i.e. it equals ¬p ∧ q.)

(ii) Existential quantifier: ∃x P(x) means “there exists at least one element x in the domain for which P(x) is true”. It is false only if P(x) is false for every x.

(iii) True. For x = 1/2: x⁴ = 1/16 and x² = 1/4, so x⁴ < x². (Any x with 0 < |x| < 1 works.)

(iv) Idempotent laws: A ∪ A = A and A ∩ A = A.

(v) A proposition is a declarative sentence that is either true or false, e.g. “7 is a prime number” (true). A predicate is a statement with variables whose truth depends on their values, e.g. P(x): “x > 3”; it becomes a proposition when x is given a value or quantified (P(5) is true).

(vi) |A × B × C| = m · n · p (product rule).

(vii) Yes, f is one-to-one: the images 4, 5, 1, 3 are all different, so no two elements of the domain map to the same value. (It is not onto since 2 has no pre-image.)

(viii) R = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}. Directed graph: vertices 1, 2, 3, 4; a loop at each vertex; arrows 1→2, 1→3, 1→4 and 2→4.

(ix) Halting problem: the problem of deciding, for any program and input, whether the program will eventually stop or run forever. Alan Turing proved (1936) that no algorithm can solve it for all programs – it is undecidable.

(x) Binary search halves the list each time: 64 → 32 → 16 → 8 → 4 → 2 → 1, which is log₂64 = 6 halvings, plus a final comparison = 7 comparisons in the worst case. (Rosen’s version, which uses two comparisons per step, needs 2 log₂n + 2 = 14.)

(xi) Replace each octal digit by 3 bits: 1 = 001, 6 = 110, 0 = 000, 4 = 100, so (1604)₈ = (1110000100)₂.

(xii) Pigeonhole principle: if k + 1 or more objects are placed into k boxes, at least one box contains two or more objects. Generalized: N objects in k boxes → some box has at least ⌈N/k⌉ objects.

(xiii) The reflexive closure of R on A is the smallest reflexive relation containing R: R ∪ {(a,a) | a ∈ A}. The symmetric closure is the smallest symmetric relation containing R: R ∪ R⁻¹, where R⁻¹ = {(b,a) | (a,b) ∈ R}.

(xiv) Recurrence relation: an equation that defines each term of a sequence using previous terms, with initial conditions, e.g. Fibonacci fₙ = fₙ₋₁ + fₙ₋₂, f₀ = 0, f₁ = 1.

(xv) Total balls = 15; white or black = 6 + 5 = 11. P = 11/15.

(xvi) Cyclic graph: a graph that contains at least one cycle (a path that starts and ends at the same vertex without repeating edges), e.g. the triangle a–b–c–a, or Cₙ. A graph with no cycle is acyclic (a tree/forest).

Q2 – Logical equivalences

(i)  ¬p → (q → r)
   ≡ ¬(¬p) ∨ (q → r)        implication law (a → b ≡ ¬a ∨ b)
   ≡ p ∨ (¬q ∨ r)           double negation, implication law
   ≡ ¬q ∨ (p ∨ r)           commutative and associative laws
   ≡ q → (p ∨ r)            implication law                        ∎

(ii) p ↔ q
   ≡ (p → q) ∧ (q → p)      biconditional law
   ≡ (¬q → ¬p) ∧ (¬p → ¬q)  contrapositive of each implication
   ≡ (¬p → ¬q) ∧ (¬q → ¬p)  commutative law
   ≡ ¬p ↔ ¬q                biconditional law                      ∎

Q3 – Linear search to find the insertion position in a sorted list

Idea: scan the sorted list a₁ ≤ a₂ ≤ … ≤ aₙ from the left until we find the first element that is not smaller than the new element x; x must be inserted just before it. If no such element exists, x goes at the end.

procedure insertion_position(x; a1, a2, ..., an : sorted integers)
    i := 1
    while (i <= n and x > ai)
        i := i + 1
    return i          { x should be placed at position i;
                        i = n + 1 means x goes after the last element }

procedure insert(x; a1, ..., an)
    i := insertion_position(x; a1, ..., an)
    for j := n downto i
        a(j+1) := aj     { shift larger elements one place right }
    ai := x
    n := n + 1

Example: list 2, 5, 8, 12 and x = 7: 7 > 2, 7 > 5, 7 ≤ 8 → position 3; result 2, 5, 7, 8, 12. Worst case: n comparisons, so O(n).

Q4

(a) Let p: “It is sunny this afternoon”, q: “It is colder than yesterday”, r: “We will go swimming”, s: “We will take a canoe trip”, t: “We will be home by sunset”. Premises: ¬p ∧ q, r → p, ¬r → s, s → t. Conclusion: t.

Step                      Reason
1. ¬p ∧ q                  Premise
2. ¬p                      Simplification using (1)
3. r → p                   Premise
4. ¬r                      Modus tollens using (2) and (3)
5. ¬r → s                  Premise
6. s                       Modus ponens using (4) and (5)
7. s → t                   Premise
8. t                       Modus ponens using (6) and (7)

Hence “We will be home by sunset.”

(b) Yes, f is onto. Take any y ∈ R. We need x with 4x − 1 = y, i.e. x = (y + 1)/4, which is a real number. Then f((y + 1)/4) = 4·(y + 1)/4 − 1 = y. So every real y has a pre-image and f is onto. (It is also one-to-one, so f is a bijection.)

Q5 – Binary search tree and traversals

11
              /      \
            6          19
          /   \       /   \
         4     8     17    43
          \     \          /  \
           5     10       31   49

Preorder (root, left, right): 11, 6, 4, 5, 8, 10, 19, 17, 43, 31, 49

Inorder (left, root, right): 4, 5, 6, 8, 10, 11, 17, 19, 31, 43, 49 (sorted order, as expected for a BST)

Postorder (left, right, root): 5, 4, 10, 8, 6, 17, 31, 49, 43, 19, 11

Q6 – Venn diagram problem

Students who used at least one package = 100 − 28 = 72. Used A and B but not C = 13 − 10 = 3. Let x = A and C only, y = B and C only.

Regions of the Venn diagram (U = 100):
  only A = 8        only B = 26       only C = 7
  A∩B only = 3      A∩C only = x      B∩C only = y
  A∩B∩C = 10        none = 28

(ii) Total in the three sets: 8 + 26 + 7 + 3 + 10 + x + y = 72 ⇒ x + y = 18.
n(A) = 8 + 3 + 10 + x = 21 + x and n(B) = 26 + 3 + 10 + y = 39 + y. Since n(B) = 2·n(A): 39 + y = 2(21 + x) ⇒ y = 2x + 3 (or 2x − y = −3).

(iii) x + (2x + 3) = 18 ⇒ 3x = 15 ⇒ x = 5, y = 13.

(iv) n(C) = 7 + x + y + 10 = 7 + 5 + 13 + 10 = 35 students.

Check: n(A) = 26, n(B) = 52 = 2 × 26 ✓; 8+26+7+3+5+13+10+28 = 100 ✓.

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.