Discrete Structure MSc IT 2nd TERM Past paper 2017 UOS
University of Sargodha
M.Sc. 2nd Term Examination 2017
Subject: Information Technology
Paper: Discrete Structure (CMP-2111)
Time Allowed: 2:30 Hours
Maximum Marks: 80
Objective Part (Compulsory)
Q. No.1. Write short answers of the following in 2-3 lines on your answer sheet. (2*16)
- Logically Equivalent
- Pseudocode
- Recursive Algorithm
- Permutation
- Random Variable
- Derangement
- Multi-graph
- Tree Traversal
- Full Adder
- Pascal’s Triangle
- Euler path
- Recurrence Relation
- Leaf
- Greedy Algorithm
- K-map
- Postulate
Subjective part (3*16=48 Marks)
Q. No.2
(a) Show that by using law’s of logic
$ \sim { \sim (p \land q) \lor (\sim p \land \sim q) } \lor (p \land q) \equiv p $
(b) Check the validity of the following argument
$ p \land q \rightarrow r $
$ p \lor q $
$ q \rightarrow p $
$ \therefore r $
Q. No.3
(a) Draw a graph if possible with four vertices of degree 1, 2, 3 & 4
(b) Find inverse function $ H(x) = \frac{x+1}{x-1} $
Q. No.4
(a) For all sets A & B prove that
$ (A^c \cup B^c)^c – A^0 = A $
(b) Suppose B is a Boolean algebra then prove that for all
$ x \in B \quad x \land x = x \text{ and } x \lor x = x $
Q. No.5
(a) Prove by induction method $ 2^n – 1 $ is divisible by 3 for all $ n \geq 1 $.
(b) Use O-notation to prove that
$ 10x^3 + x^2 – 5x + 6 \text{ is } O(x^3) $
Q. No.6
(a) How many integers from 1 through 1000 are multiples of 3 or multiples of 5?
(b) Give a logic gate implementation of
$ (\sim x)(\sim y) + y \cdot (\sim x) $
For more information on discrete structures, visit Coursera.org- Discrete Mathematics