Discrete Structure MSc IT 1st TERM Past paper 2014 UOS

Posted by Ayesha

University of Sargodha
M. Sc. I. T., First Term Exam 2014
Subject: Information Technology
Paper: Discrete Mathematics (CMP: 501)
Time Allowed: 2:30 Hours
Maximum Marks: 80

Objective Part
Q.1. Write short answers of the following in 2-3 lines each. (2*16)

a) Define Existential quantifier.
b) Define predicate.
c) Define reflexive relation.
d) Define Euler path.
e) Define Euler Circuit.
f) Give an indirect proof to the theorem: “if 3n + 2 is odd, then n is odd”.
g) Cardinality of a Set.
h) Monotonic Functions.
i) Define Transitive Closure.
j) Proof by contradiction with example.
k) Construct truth table for (p ∨ q) ∨ ¬p.
l) What is a bipartite graph?
m) Prove that p → (¬q → r) and (p ∧ ¬r) → ¬q are logically equivalent.
n) What is worst case complexity of bubble sort?
o) What is the space complexity of linear search algorithm?

Subjective Part
Q.2 (a) Define the following with example: (i) One to one function (ii) On to Function (iii) Bijective Function (9)
(b) Determine whether each of these functions is a bijection from R to R. (3)
(i) f(x) = x² + 1 (ii) f(x) = x³

Q.3 (a) It is not sunny this afternoon and it is colder than yesterday. We will go swimming only if it is sunny. If we do not go swimming, then we will take a canoe trip. If we take a canoe trip, then we will be home by sunset. Lead to the conclusion: We will be home by the sunset. (8)
(b) Explain the proof by contradiction with example to prove that √2 is irrational. (4)

Q.4. What are asymptotic notations? Explain Big-O, Big Omega and Big Theta notations. (12)

Q.5. What is mathematical induction? Use mathematical induction to prove that k³ – k is divisible by 3 whenever k is a positive integer. (4 + 8)

Q.6 (a) A CSE senior needs 5 CSE courses to graduate. There are 12 different computer science courses that she can take next semester that would count toward her degree. How many different sets of 5 courses could she take? (3)
(b) Suppose that there are eight runners in a race. Gold, silver and bronze medals are given. How many different ways are there to award these medals, if all possible outcomes of the race can occur? (3)
(c) Which of these is Symmetric, antisymmetric, or reflexive? (6)

For more information on discrete mathematics concepts, you can explore Khan Academy – Discrete Mathematics.