Discrete Structure BSIT 2nd TERM Past paper 2017 UOS
University of Sargodha
B.S. 2nd Term Examination 2017
- Subject: Information Technology
- Paper: Discrete Structures (CMP-2111)
- Time Allowed: 2.30 Hours
- Maximum Marks: 80
Objective Part (Compulsory)
Q. No. 1. Write short answers to the following in 2-3 lines on your answer sheet. (2*16)
- Find the conjunction of the propositions p and q where p is the proposition “Today is Friday” and q is the proposition “It is raining today”.
- What are the negations of the statements “All goats are mammals”?
- Define contradiction.
- What is Cartesian product of A = {a, b, c} and B = {1, 2}?
- Define Commutative Law with the help of example.
- Define this function onto or one-to-one. Domain consists of all integers.
- Differentiate between mathematical induction and strong induction?
- How many permutations of the letters ASSASSINATION contain the string SES?
- How many comparisons are needed for a binary search in a set of 64 elements?
- Let P(x) be the statement “x spends more than 5 hours every work day in class.”, where the domain consists of all students. Express each of these quantifications in English: a. b.
- What is a projection and join operator?
- What is a gonoho principle?
- How many bit strings of length eight either start with a 0 or end with the two bits 11?
- Define reflexive closure and symmetric closure.
- Define a relation between tree and graph.
- What is a recursive relation?
Subjective Part (16*3 = 48)
Q. 2 Prove that the following are logically equivalent by developing a series of logically equivalences.
- (ii) ¬(p v (¬p ∧ q)) and ¬p ∧ ¬q
- (iii) ¬p ⇔ q ⇔ (p ⇒ ¬q)
Q. 3 Use the divide and conquer algorithm to put 6, 1, 2, 5, 7, 23, 11, 12, 4, 3 into decreasing order.
Q. 4 Mention whether the following problems are permutation or combination problems.
- i. How many ways can tosses of coin yield 2 heads and 4 tails?
- ii. How many lines can you draw using 3 non-collinear (not in a single line) points A, B, and C on a plane?
- iii. How many triangles can you make using 6 non-collinear points on a plane?
- iv. In a certain country, the car number plate is formed by 4 digits from the digits 1, 2, 3, 4, 5, 6, 7, 8, and 9 followed by 3 letters from the alphabet. How many number plates can be formed if neither the digits nor the letters are repeated?
Q. 5 Find the in-degree and out-degree of the given graph. Also find whether the given graph has Hamiltonian or Euler tour? Show visually. Also represent the graph into adjacency matrix.
Q. 6 Determine whether each of these functions is a bijection from R to R.
- (b) Write down base and recursive case for sum of array elements. Also solve for array of length 5 via tree convention.
For further reading on discrete structures, you can refer to Discrete Mathematics and Its Applications.