Discrete Structure BSCS/IT/SE 2nd TERM Past paper 2016 UOS
University of Sargodha
BS 2nd Term Examination 2016
Subject: Computer Sc./I.T/Software Engineering
Paper: Discrete Structure (COMP:2111)
Time Allowed: 2:30 Hours
Maximum Marks: 80
Objective Part (Compulsory)
Q.1. Write short answers of the following in two lines each. (2*16)
i. What is a compound proposition? Give an example.
ii. Give an indirect proof to the theorem: “If $ 3n + 2 $ is odd, then $ n $ is odd.”
iii. What are the contrapositive, the converse, and the inverse of the conditional statement? “The home team wins whenever it is raining.”
iv. What is bi-implication? State with an example.
v. Show that $ \neg (P \vee Q) $ and $ \neg P \wedge \neg Q $ are logically equivalent.
vi. How many edges are there in a graph with ten vertices each of degree six?
vii. What is a bipartite graph?
viii. What is the cardinality of each of these sets? $ {a}, {a}, {a} $
ix. Height of tree is 7. Find sum of the height.
x. What is the difference between geometric progression and arithmetic progression?
xi. Let $ f $ be the function from $ {a, b, c} $ to $ {1, 2, 3} $ defined by $ f(a) = 3, f(b) = 2, f(c) = 1, $ and $ f(d) = 3 $. Is $ f $ an onto function?
xii. State division algorithm.
xiii. Define the chromatic number of a graph.
xiv. What is meant by Euler path and Euler circuit?
xv. What is the height of a rooted tree?
Subjective Part
Q.2.
a) Use rules of inference to show that the hypotheses “Randy works hard,” “If Randy works hard, then he is a dull boy,” and “If Randy is a dull boy, then he will not get the job” imply the conclusion “Randy will not get the job.” [6]
b) What is wrong with this argument? Let $ H(x) $ be “x is happy.” Given the premise $ \exists xH(x) $, we conclude that $ H(John) $. Therefore, John is happy. [6]
Q.3. Encrypt the message UPLOAD using the RSA system with $ n = 53 \cdot 61 $ and $ e = 17 $ [12]
Q.4. What is proof by mathematical induction? Use mathematical induction to prove that $ 13 – k $ is divisible by 3 whenever $ k $ is a positive integer. [4 + 8]
Q.5. Find the smallest relation containing the relation $ {(1, 2), (1, 4), (3, 3), (4, 1)} $ that is
a) Reflexive and transitive.
b) Symmetric and transitive. [12]
Q.6.
a) Using alphabetical order, construct a binary search tree for the words in the sentence “The quick brown fox jumps over the lazy dog.” [6]
b) Use Huffman coding to encode these symbols with given frequencies: 0.20, 0.10, 0.15, 0.25, 0.30. What is the average number of bits required to encode a character? [6]
Q.7. How many different spanning trees does each of these simple graphs have?
a) K3
b) K4
c) K2,2
d) C5 [12]
For more information on discrete structures, visit Coursera – Discrete Mathematics.