Discrete Structure MSc IT 2nd TERM Past paper 2016 UOS
University of Sargodha
M. Sc. 2nd Term Exam 2016.
Subject: I. T
Paper: Discrete Structures (CMP: 2111)
Time Allowed: 2:30 Hour
Maximum Marks: 80
Objective Part (Compulsory)
Q1. Write short answers to the following in 2-3 lines each. (16*2) i. Verify whether (P ∧ Q) ⇔ (P ∨ Q) is tautology or not.
ii. Let $ Q(x) $ denote the statement “$ x $ = $ x + 1 $!” What is the truth value of the quantification $ 3xQ(x) $, where the domain consists of all real numbers?
iii. Suppose that the domain of the propositional function $ P(x) $ consists of the integers 1, 2, 3, 4, and 5. Express these statements without using quantifiers: $ \neg P(1) \land P(2) \land P(3) \land P(4) \land P(5) $. Write is symbolic form “Some student have no ID cards”.
iv. Write the names of an algorithm properties.
v. What is the decimal expansion of the number with hexadecimal expansion (2AE0B)₁₆?
vi. Define partial ordering with example.
vii. Define the spanning tree of a graph.
viii. Decrypt the message WATCH YOUR STEP by translating the letters into numbers, applying the given encryption function, and then translating the numbers back into letters. $ f(p) = (14p + 21) mod 26 $
ix. How can you produce the terms of a sequence if the first 10 terms are 5, 1, 17, 23, 29, 35, 41, 47, 53, 59?
x. How many permutations of the letters ABCDEFG contain the string CFG?
xi. Find recurrence relation of the sequence $ S_n = 5 $
xii. How many subsets with more than two elements does a set with 100 elements have?
xiii. What are the connected components of a graph?
xiv. What is a bipartite graph?
xv. What is the height of a rooted tree?
Subjective Part
Q2. Prove that if $ m = n $ and $ p = q $ are even integers, where $ m, n, p $ are integers, then $ m – p $ is even. What kind of proof did you use?
[12]
Q3. Find each of these values.
a) $ (992 \ mod \ 32)/(3 \ mod \ 15) $
b) $ (34 \ mod \ 17)/(2 \ mod \ 11) $
c) $ (193 \ mod \ 32)/(2 \ mod \ 31) $
d) $ (893 \ mod \ 9)/(4 \ mod \ 26) $
[12]
Q4. Suppose that a password for a computer system must have at least 8, but no more than 12 characters, where each character in the password is a lowercase English letter, an uppercase English letter, a digit, or one of the six special characters *, >, <, !, and =.
a) How many different passwords are available for this computer system?
b) How many of these passwords contain at least one occurrence of at least one of the six special characters?
[6]
Q5. Find the smallest relation containing the relation $ {1, 2}, {4, (3, 3), (4, 1)} $ that is:
a) Reflexive and transitive.
b) Symmetric and transitive.
[12]
Q6. a) Using alphabetical order, construct a binary search tree for the words in the sentence “The quick brown fox jumps over the lazy dog.”
b) Use Huffman coding to encode these symbols with given frequencies: a: 0.20, b: 0.10, c: 0.15, d: 0.25, e: 0.30. What is the average number of bits required to encode a character?
[12]
Q7. A coin is flipped 10 times where each flip comes up either heads or tails. How many possible outcomes
a) are there in total?
b) contain at most three tails?
c) contain the same number of heads and tails?
[12]