Blog
Discrete Structures Past Paper 2018 – BS IT 2nd Term UOS
University of Sargodha (UOS) BS IT 2nd term Discrete Structures (CMP-2111) past paper 2018, with the full question paper in text form and step-by-step solved answers, including logical equivalences, rules of inference, the pigeonhole principle and a spanning tree.

Discrete Structures Past Paper 2018 BS IT (text version)
University of Sargodha – BS 2nd Term Examination 2018, Subject: Information Technology
Paper: Discrete Structures (CMP-2111) · Time: 2:30 Hours · Maximum marks: 80
Note: Objective part is compulsory. Attempt any three questions from subjective part.
Objective part – Q1: Write short answers of the following in 2-3 lines each on your answer sheet. (16*2)
- Find the conjunction of the propositions p and q where p is the proposition “Today is Sunday” and q is the proposition “University will be off.”
- Define modus ponen rule of inference.
- Differentiate b/w Predicate and Quantifiers
- 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 quantification in English
a. ∀x ¬P(x) b. ∃x P(x) - Use DE Morgan Law to find the negation of each of the following statement?
a. Carlos will bicycle or run tomorrow. b. Ibrahim is smart and hardworking. - Translate the statement “The sum of two positive integers is always positive” into a logical expression.
- Differentiate between mathematical induction and strong induction?
- What are the different ways to describe the complexity of algorithms?
- Define this function f(x) = (x+1)/(x2+2) onto or one-to-one. Domain consist of all integers.
- What are the symmetric matrix?
- Draw Venn diagram for the symmetric difference of Set A = {1, 3, 5} and B = {1, 2, 3}.
- Different between projection and join operator?
- What is the difference between an r-combination and an r-permutation of a set with n elements?
- Define the recurrence relation of the sum of first 5 integers.
- What is pigeonhole principle?
- Difference between tree and graph.
Subjective part (3*16)
Q2. Prove that following are logically equivalent by developing a series of logically equivalences.
i. ¬p ↔ q ⇔ p ↔ ¬q
ii. (p∧q) → p is a tautology
Q3. Using rule of inference Show that the hypotheses “If you send me an e-mail message, then I will finish writing the program,” “If you do not send me an e-mail message, then I will go to sleep early,” and “If I go to sleep early, then I will wake up feeling refreshed” lead to the conclusion “If I do not finish writing the program, then I will wake up feeling refreshed.”
Q4. Solved the following statements by using pigeonhole principle.
ii. Explain how the pigeonhole principle can be used to show that among any 11 integers, at least two must have the same last digit.
iii. N+1 integers are chosen at random from a set of 2N consecutive integers. Prove that at least 2 chosen integers are consecutive.
Q5. [figure: see the paper image](a) There are 32 microcomputers in a computer center. Each microcomputer has 24 ports. How many different ports to a microcomputer in the center are there?
(b) The diagrams below represent the activities chosen by youth club members. They can choose to play tennis (T), badminton (B) or squash (S). Shading the diagram which represents.
• those who play all three sports
• those who play tennis and badminton, but not squash
• those who play only tennis
Q6. (i) Draw a tree for following and run inorder tree traversal 1, 9, 8, 3, 12, 20, 15, 2
(ii) Make a spanning tree of following graph. With all steps mentioned.[figure: see the paper image]
Original paper (scanned copy)
The clean paper above is retyped by Shining Study from this original University of Sargodha question paper. Click the scan to view it full size.
Solved answers
Q1 – Short questions
(i) p ∧ q: “Today is Sunday and the university will be off.” It is true only when both parts are true.
(ii) Modus ponens: from p and p → q we can conclude q. In symbols: [p ∧ (p → q)] → q. Example: “If it rains, the ground is wet. It rains. Therefore, the ground is wet.”
(iii) A predicate is a statement containing variables, P(x), that becomes true or false when values are given (e.g. P(x): x > 3). A quantifier specifies for how many elements of the domain the predicate is true: universal ∀x (for all) and existential ∃x (there exists). Quantifiers turn a predicate into a proposition.
(iv) (a) ∀x ¬P(x): “No student spends more than 5 hours every work day in class.” (b) ∃x P(x): “There is a student who spends more than 5 hours every work day in class.”
(v) (a) ¬(p ∨ q) ≡ ¬p ∧ ¬q: “Carlos will not bicycle tomorrow and he will not run tomorrow.” (b) ¬(p ∧ q) ≡ ¬p ∨ ¬q: “Ibrahim is not smart or he is not hardworking.”
(vi) ∀x ∀y ((x > 0) ∧ (y > 0) → (x + y > 0)), where the domain is all integers.
(vii) Mathematical (weak) induction: prove P(1), then show P(k) → P(k + 1). Strong induction: prove P(1), then show [P(1) ∧ P(2) ∧ … ∧ P(k)] → P(k + 1), i.e. we may assume the statement for all smaller values. Strong induction is convenient when P(k + 1) depends on earlier cases (e.g. every integer > 1 is a product of primes).
(viii) By time complexity (number of basic operations as a function of input size n) and space complexity (memory used), in the worst, average and best case, expressed with asymptotic notation: Big-O (upper bound), Big-Ω (lower bound), Big-Θ (tight bound), e.g. O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ).
(ix) f(x) = (x + 1)/(x² + 2) on the integers is not one-to-one: f(0) = 1/2 and f(2) = 3/6 = 1/2. It is not onto the integers (or reals): for example f(x) = 1 would need x + 1 = x² + 2, i.e. x² − x + 1 = 0, which has no real root; most values are never reached.
(x) Symmetric matrix: a square matrix equal to its transpose, A = Aᵀ, i.e. aᵢⱼ = aⱼᵢ for all i, j. Example [[1, 2], [2, 5]].
(xi) A ⊕ B = (A − B) ∪ (B − A) = {5} ∪ {2} = {2, 5}. Venn diagram: two overlapping circles A and B; 1 and 3 in the overlap (not shaded), 5 in A only and 2 in B only – the two outer parts are shaded.
(xii) For n-ary relations (database tables): the projection Pᵢ₁,ᵢ₂,…,ᵢₘ keeps only the chosen columns (fields) of a relation and removes the rest. The join Jₚ combines two relations into one by matching records that agree on p common fields.
(xiii) An r-permutation is an ordered arrangement of r elements: P(n, r) = n!/(n − r)!. An r-combination is an unordered selection of r elements: C(n, r) = n!/[r!(n − r)!]. Example n = 3, r = 2: P = 6, C = 3.
(xiv) Let S(n) be the sum of the first n integers: S(n) = S(n − 1) + n for n ≥ 2, with S(1) = 1. Then S(5) = 15.
(xv) Pigeonhole principle: if k + 1 or more objects are put into k boxes, then at least one box has two or more objects.
(xvi) A tree is a connected graph with no cycles; it has exactly n − 1 edges for n vertices and there is a unique path between any two vertices. A general graph may have cycles, may be disconnected, and has any number of edges.
Q2
(i) ¬p ↔ q
≡ (¬p → q) ∧ (q → ¬p) biconditional law
≡ (p ∨ q) ∧ (¬q ∨ ¬p) implication law, double negation
≡ (¬¬q ∨ p) ∧ (¬p ∨ ¬q) double negation, commutative
≡ (¬q → p) ∧ (p → ¬q) implication law
≡ (p → ¬q) ∧ (¬q → p) commutative law
≡ p ↔ ¬q biconditional law ∎
(ii) (p ∧ q) → p
≡ ¬(p ∧ q) ∨ p implication law
≡ (¬p ∨ ¬q) ∨ p De Morgan's law
≡ (¬p ∨ p) ∨ ¬q commutative and associative laws
≡ T ∨ ¬q negation law
≡ T domination law → tautology ∎Q3 – Rules of inference
Let p: “You send me an e-mail message”, q: “I will finish writing the program”, r: “I will go to sleep early”, s: “I will wake up feeling refreshed”. Premises: p → q, ¬p → r, r → s. Conclusion: ¬q → s.
Step Reason
1. p → q Premise
2. ¬q → ¬p Contrapositive of (1)
3. ¬p → r Premise
4. ¬q → r Hypothetical syllogism using (2) and (3)
5. r → s Premise
6. ¬q → s Hypothetical syllogism using (4) and (5)Hence: “If I do not finish writing the program, then I will wake up feeling refreshed.” ∎
Q4 – Pigeonhole principle
(ii) The last digit of any integer is one of the 10 digits 0, 1, …, 9 (10 boxes). Among 11 integers (11 pigeons) placed in boxes by their last digit, since 11 > 10, at least one box gets two integers – so at least two of them have the same last digit.
(iii) Let the 2N consecutive integers be a+1, a+2, …, a+2N. Divide them into N pairs of consecutive integers: {a+1, a+2}, {a+3, a+4}, …, {a+2N−1, a+2N}. These N pairs are the boxes. Choosing N + 1 integers (pigeons) means two of them must fall in the same pair, and the two numbers in a pair are consecutive. ∎
Q5
(a) By the product rule: 32 × 24 = 768 different ports.
(b) In the diagram T, B and S are three overlapping circles:
- All three sports: shade only the central region where all three circles overlap – T ∩ B ∩ S.
- Tennis and badminton, but not squash: shade the part of the T–B overlap that is outside circle S – (T ∩ B) − S.
- Only tennis: shade the part of circle T that does not overlap B or S – T − (B ∪ S).
Q6
(i) Inserting 1, 9, 8, 3, 12, 20, 15, 2 into a binary search tree (smaller to the left, larger to the right):
1
\
9
/ \
8 12
/ \
3 20
/ /
2 15Inorder traversal (left, root, right): 1, 2, 3, 8, 9, 12, 15, 20 – the numbers in sorted order.
(ii) Spanning tree (graph has 7 vertices and 13 edges: F–A, F–C, F–G, A–B, A–E, A–C, B–E, B–D, B–G, E–C, E–D, C–D, D–G). A spanning tree must contain all 7 vertices and exactly 7 − 1 = 6 edges with no cycle. Using breadth-first search from A:
- Start at A; visit its neighbours F, B, E, C → add edges A–F, A–B, A–E, A–C.
- From F: neighbour G is new → add F–G (C is already visited).
- From B: neighbour D is new → add B–D (E, G already visited).
- All 7 vertices are visited; stop. Remaining edges are not added because each would form a cycle.
Spanning tree edges: A–F, A–B, A–E, A–C, F–G, B–D (6 edges). Other valid spanning trees also exist (e.g. by removing edges that form cycles one by one until 6 remain).
Answers prepared by Shining Study for revision. Check them against your class notes and teacher’s guidance.

