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.