Blog
Discrete Structure BSCS 2nd TERM Past paper 2017 UOS
University of Sargodha
BS 2nd Term Examination 2017
Subject: Compute Science
Paper: Discrete Structure (CMP:2211)
Time Allowed: 2:30 Hours
Maximum Marks: 80
Objective Part (Compulsory)
Q.1 Write short answers of the following in 2-3 lines each. (2*16)
i. How many rows appear in a truth table for each of these compound propositions?
(p→r)∨(¬s→¬t)∨(u→v).
ii. What are Absorption laws for sets?
iii. Let P(x) be the statement “x spends more than five hours every weekday in class,” where the domain for x consists of all students. Express the quantifications in English.
∃x ¬P(x).
iv. Differentiate between mathematical induction and strong induction?
v. Determine the truth value of following statements if the domain for all variables consists of all integers.
∀n(n² ≥ n)
vi. Define Greedy algorithm with example.
vii. Define the term counterexample.
viii. What is the Cartesian product A × B × C, where A = {0, 1}, B = {1, 2}, and C = {0, 1, 2}?
ix. Let f be the function from {a, b, c, d} to {1, 2, 3, 4} with f(a) = 4, f(b) = 2, f(c) = 1, f(d) = 3. Is f a bijection?
x. What is the difference between Best Case and Worst Case Complexity of algorithm?
xi. Convert the hexadecimal expansion of (80)₁₆ integers to a binary expansion.
xii. What are the two ways for the representation of Graph?
xiii. What is the probability of getting a number greater than 4 when a dice is tossed?
xiv. Define the term Halting Problem.
xv. Define Binary Search Tree.
xvi. How the Height of a tree is calculated.
Subjective Part
Attempt any three questions out of five questions (3*16)
Q.2 Prove that the following are logically equivalent by developing a series of logically equivalences.
i. (p ∨ q) ∧ (¬p ∨ r) → (q ∨ r) is a tautology.
ii. (¬p → q) → (r → s) and (p → r) → (q → s).
Q.3
(a) Show that the premises “A student in this class has not read the book,” and “Everyone in this class passed the first exam” imply the conclusion “Someone who passed the first exam has not read the book.”
(b) Use mathematical induction to prove that 1 + 3 + 5 + … + (2n – 1) = n² for all integers n ≥ 1.
Q.4 Use the Insertion sort to sort 3, 1, 5, 7, 4, in decreasing order showing the lists obtained at each step.
Q.5
(a) Find a counterexample, if possible, to these universally quantified statements, where the domain for all variables consists of all integers.
i. ∀x∀y(x² = y² → x = y)
ii. ∀x∃y(x² = y)
iii. ∀x∀y(xy ≤ x)
(b) Let f: ℝ → ℝ be defined by the rule f(x) = x³. Show that f is a bijective.
Q.6 Draw a binary search tree by inserting the following numbers from left to right: 19, 10, 8, 17, 4, 10, 6, 13, 43, 47, 33.
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.
For more information on discrete structures, you can visit Coursera – Discrete Mathematics.
Solved answers – Discrete Structure 2017
Short questions
- The propositions contain 6 variables (p, r, s, t, u, v), so the truth table has 2⁶ = 64 rows.
- Absorption laws: A ∪ (A ∩ B) = A and A ∩ (A ∪ B) = A.
- ∃x ¬P(x): “There is a student who does not spend more than five hours every weekday in class.”
- Ordinary induction assumes only P(k) to prove P(k + 1). Strong induction assumes P(1), P(2), …, P(k) all hold to prove P(k + 1); it is useful when P(k + 1) depends on earlier cases (e.g. prime factorization).
- True. For n ≤ 0, n² ≥ 0 ≥ n; for n ≥ 1, n² = n·n ≥ n.
- Greedy algorithm: makes the locally best choice at each step hoping for a global optimum. Example: making change for 67 with coins 25, 10, 5, 1 – take 25, 25, 10, 5, 1, 1.
- Counterexample: a single case that makes a universally quantified statement false, e.g. x = 2 disproves ∀x(x² = x), since 4 ≠ 2.
- A × B × C = {(0,1,0), (0,1,1), (0,1,2), (0,2,0), (0,2,1), (0,2,2), (1,1,0), (1,1,1), (1,1,2), (1,2,0), (1,2,1), (1,2,2)} – 2 × 2 × 3 = 12 triples.
- Yes. Every element maps to a different value (one-to-one) and all of 1, 2, 3, 4 are hit (onto), so f is a bijection.
- Best case is the minimum number of operations over all inputs of size n (e.g. linear search finds the key first: O(1)); worst case is the maximum (key absent: O(n)).
- 8 = 1000, 0 = 0000, so (80)₁₆ = (1000 0000)₂.
- Adjacency matrix and adjacency list (the incidence matrix is a third option).
- Favourable outcomes {5, 6}: P = 2/6 = 1/3.
- Halting problem: deciding, for any program and input, whether the program will eventually stop. Turing proved no algorithm can solve it for all cases – it is undecidable.
- Binary search tree: a binary tree in which every node’s key is greater than all keys in its left subtree and smaller than all keys in its right subtree.
- Height of a tree: the length of the longest path from the root to a leaf; recursively, height = 1 + max(height(left), height(right)), with an empty tree having height −1 (a single node has height 0).
Subjective questions
Q.2(i) [(p ∨ q) ∧ (¬p ∨ r)] → (q ∨ r)
≡ ¬[(p ∨ q) ∧ (¬p ∨ r)] ∨ (q ∨ r) (implication law)
≡ (¬p ∧ ¬q) ∨ (p ∧ ¬r) ∨ q ∨ r (De Morgan)
≡ [(¬p ∧ ¬q) ∨ q] ∨ [(p ∧ ¬r) ∨ r] (associative, commutative)
≡ [(¬p ∨ q) ∧ (¬q ∨ q)] ∨ [(p ∨ r) ∧ (¬r ∨ r)] (distributive)
≡ (¬p ∨ q) ∨ (p ∨ r) (negation and identity laws)
≡ (¬p ∨ p) ∨ q ∨ r ≡ T ∨ q ∨ r ≡ T. Hence it is a tautology.
Q.2(ii) These two are not logically equivalent. Take p = T, q = F, r = T, s = F: (¬p → q) = (F → F) = T and (r → s) = F, so the first statement is T → F = F. But (p → r) = T and (q → s) = (F → F) = T, so the second is T → T = T. One assignment giving different values is enough to show non-equivalence.
Q.3(a) Let C(x): x is in this class, B(x): x has read the book, P(x): x passed the first exam. Premises: ∃x(C(x) ∧ ¬B(x)) and ∀x(C(x) → P(x)). Conclusion: ∃x(P(x) ∧ ¬B(x)).
- ∃x(C(x) ∧ ¬B(x)) – premise
- C(a) ∧ ¬B(a) – existential instantiation
- C(a) – simplification (2)
- ∀x(C(x) → P(x)) – premise
- C(a) → P(a) – universal instantiation
- P(a) – modus ponens (3, 5)
- ¬B(a) – simplification (2)
- P(a) ∧ ¬B(a) – conjunction (6, 7)
- ∃x(P(x) ∧ ¬B(x)) – existential generalization
Q.3(b) Basis: n = 1: left side 1, right side 1² = 1. ✓ Inductive step: assume 1 + 3 + … + (2k − 1) = k². Then 1 + 3 + … + (2k − 1) + (2k + 1) = k² + 2k + 1 = (k + 1)². So P(k) ⇒ P(k + 1), and by induction the formula holds for all n ≥ 1.
Q.4 Insertion sort (decreasing):
- Start: 3 | 1, 5, 7, 4
- Insert 1: 3, 1, 5, 7, 4 (1 < 3, stays)
- Insert 5: 5, 3, 1, 7, 4
- Insert 7: 7, 5, 3, 1, 4
- Insert 4: 7, 5, 4, 3, 1 – sorted.
Q.5(a) (i) x = 1, y = −1: x² = y² = 1 but x ≠ y – counterexample. (ii) No counterexample: for every integer x, y = x² is an integer, so the statement is true. (iii) x = 1, y = 2: xy = 2 > 1 – counterexample.
Q.5(b) One-to-one: if a³ = b³ then a³ − b³ = (a − b)(a² + ab + b²) = 0. The second factor is positive unless a = b = 0, so a = b. Onto: for any real y, x = ∛y is real and f(x) = y. Hence f(x) = x³ is a bijection.
Q.6 Inserting 19, 10, 8, 17, 4, 10, 6, 13, 43, 47, 33 (the duplicate 10 is ignored, since BST keys are distinct):
19
/ \
10 43
/ \ / \
8 17 33 47
/ /
4 13
\
6- Preorder (root, left, right): 19, 10, 8, 4, 6, 17, 13, 43, 33, 47
- Inorder (left, root, right): 4, 6, 8, 10, 13, 17, 19, 33, 43, 47
- Postorder (left, right, root): 6, 4, 8, 13, 17, 10, 33, 47, 43, 19
Answers prepared by Shining Study for revision. Check them against your class notes and teacher’s guidance.
