BIT152 · TU past paper
Discrete Structure 2080 question paper
The complete TU 2080 exam paper for Discrete Structure (BIT152), all 12 questions with solved model answers written to the mark scheme.
Tap a question to open its answer.
- 110 marksVenn diagramsHideAnswer
Explain how set operations can be represented using venn diagram with example.Convert the following sentences using quantifier: a.) Not all good peoples are heroes. b.) Every peoples in our country are loyal. c.) Some people hate good people.[10]
--- A Venn Diagram is a pictorial/graphical representation of sets and their relationships within a universal set U. Sets are represented as circles inside a rectangle (universal set). --- Definition: The union of sets A and B contains a...
- 25 marksCeiling and floor functionsHideAnswer
State ceiling function and floor function with examples. How mathematical induction can be used to prove the correctness of recursive algorithm? Illustrate with an example.[5]
--- Definition: The floor function of a real number $x$, denoted $\lfloor x \rfloor$, is the greatest integer less than or equal to $x$. $$\lfloor x \rfloor = \max{n \in \mathbb{Z} \mid n \leq x}$$ Examples: - $\lfloor 4.7 \rfloor = 4$...
- 310 marksNumericalConnectivity in graphsHideAnswer
What does connectivity in graphs mean? Differentiate between permutation and combination. Solve the recurrence relation $a_n = 7a_{n-1} - 10a_{n-2}$ with initial conditions $a_0 = 2$ and $a_1 = 3$. [4+6]
- Recurrence: $an = 7a{n-1} - 10a{n-2}$ - Initial conditions: $a0 = 2$, $a1 = 3$ - Conceptual parts: connectivity in graphs; permutation vs combination. All data present. --- Connectivity describes the extent to which vertices of a graph...
- 45 marksTree traversal methodsHideAnswer
Describe pre-order, postorder and inorder traversal of a tree with an example. [5]
Tree traversal means visiting every node of a tree exactly once in a systematic way. The three standard depth-first traversal methods differ in when the root (parent) node is visited relative to its subtrees. --- --- Algorithm: 1. Visit ...
- 55 marksOne-to-one and onto functionsHideAnswer
Explain one-to-one and onto function with example. What is identity function? [5]
A function f: A → B is called one-to-one (injective) if every element of the domain maps to a distinct element in the codomain. Formal Definition: f is one-to-one if f(x₁) = f(x₂) implies x₁ = x₂, for all x₁, x₂ ∈ A. In other words, no t...
- 65 marksRelation matricesHideAnswer
How can you represent relations using matrices? Explain with suitable example. [5]
A relation R from set A to set B can be represented using a zero-one matrix (also called a Boolean matrix or relation matrix), denoted MR. --- Let: - Set A = {a₁, a₂, ..., aₘ} with m elements (rows) - Set B = {b₁, b₂, ..., bₙ} with n ele...
- 75 marksProof by contradictionHideAnswer
Prove that $2\sqrt{2}$ is irrational number. [5]
- A rational number is any number that can be expressed as $\frac{p}{q}$, where $p, q \in \mathbb{Z}$ and $q \neq 0$, with $\gcd(p, q) = 1$. - An irrational number is a number that cannot be expressed in such a form. --- Assume, for the ...
- 85 marksNumericalChinese Remainder TheoremHideAnswer
Solve the system of following congruences using Chinese Remainder theorem: x = 2 (mod 3), x = 3 (mod 5), x = 2 (mod 7) [5]
$$x \equiv 2 \pmod{3}, \quad x \equiv 3 \pmod{5}, \quad x \equiv 2 \pmod{7}$$ Remainders: $a1 = 2,\ a2 = 3,\ a3 = 2$ Moduli: $m1 = 3,\ m2 = 5,\ m3 = 7$ The moduli are pairwise coprime, so CRT guarantees a unique solution modulo their pro...
- 95 marksPigeonhole principleHideAnswer
What is the pigeonhole principle? Show that binomn+1k=binomnk−1+binomnk\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}binomn+1k=binomnk−1+binomnk where nnn and kkk are positive integers with n≥kn \geq kn≥k . [5]
--- Definition: If n + 1 or more objects (pigeons) are placed into n containers (pigeonholes), then at least one container must contain two or more objects. Formal Statement: If a function $f: A \to B$ where $A B$, then $f$ is not inject...
- 105 marksNumericalPermutationsHideAnswer
What is permutation? What is the next permutation in lexicographic order after 362541? [5]
Permutation and Next Permutation in Lexicographic Order
Given Data
- Current permutation: 362541 (digits: 3, 6, 2, 5, 4, 1)
- Task: find the next permutation in lexicographic (dictionary) order.
What is a Permutation?
A permutation of a set of elements is an arrangement of those elements in a definite order. For a set of $n$ distinct elements, the total number of permutations is:
$$n! = n \times (n-1) \times (n-2) \times \cdots \times 1$$
Example: For ${1, 2, 3}$, the $3! = 6$ permutations are: $$123,\ 132,\ 213,\ 231,\ 312,\ 321$$
In lexicographic order, permutations are ordered like words in a dictionary, comparing element by element from left to right.
Next Permutation Algorithm
Step 1: Find the largest index $i$ such that $a[i] < a[i+1]$ (the pivot). Step 2: Find the largest index $j > i$ such that $a[j] > a[i]$. Step 3: Swap $a[i]$ and $a[j]$. Step 4: Reverse the suffix starting at $a[i+1]$.
Applying to 362541
Index the digits (0-based):
Index 0 1 2 3 4 5 Digit 3 6 2 5 4 1 Step 1: Find pivot (scan right to left):
- $a[4]=4 > a[5]=1$ → no
- $a[3]=5 > a[4]=4$ → no
- $a[2]=2 < a[3]=5$ → pivot found, $i = 2$, value $= 2$
Step 2: Find successor $a[j] > 2$ (scan right to left):
- $a[5]=1 < 2$ → skip
- $a[4]=4 > 2$ → found, $j = 4$
Step 3: Swap $a[2]$ and $a[4]$:
Before: $3,\ 6,\ \mathbf{2},\ 5,\ \mathbf{4},\ 1$ After: $3,\ 6,\ \mathbf{4},\ 5,\ \mathbf{2},\ 1$
Step 4: Reverse suffix from index 3 to end:
Suffix $5, 2, 1 \Rightarrow 1, 2, 5$
Result: $3,\ 6,\ 4,\ 1,\ 2,\ 5$
Result
The next permutation in lexicographic order after 362541 is $\boxed{364125}$.
Verification: $364125 > 362541$ and it is the smallest such permutation (the change occurs at the rightmost possible position with the smallest valid increase), confirming correctness.
- 115 marksGraph representation using incidence matriHideAnswer
Explain incidence matrix representation of a graph with example. [5]
An incidence matrix is a 2D matrix used to represent a graph where: - Rows represent the vertices of the graph - Columns represent the edges of the graph For a graph G = (V, E) with n vertices and m edges, the incidence matrix is an n × ...
- 125 marksPre-order traversalHideAnswer
Define tree traversal. Explain pre-order traversal with example. [5]
Tree traversal is the process of visiting each node in a tree data structure exactly once in a systematic and well-defined order. It is used to process, search, or display all the nodes of a tree. Unlike linear data structures (arrays, l...