BIT152 · TU past paper
Discrete Structure 2080.1 question paper
The complete TU 2080.1 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 marksBoolean matrices and operationsHideAnswer
What is Boolean matrix and list its operations?Prove that the sum of first NNN odd integers is N2N^2N2 using mathematical induction.[4+6]
--- A Boolean matrix is a matrix in which each entry is either 0 or 1 (i.e., entries belong to the set {0, 1}). It is also called a zero-one matrix or binary matrix. Example: $$A = \begin{bmatrix} 1 & 0 & 1 \ 0 & 1 & 0 \ 1 & 1 & 0 \end...
- 210 marksGraph isomorphismHideAnswer
Differentiate between graph and tree.Describe about the necessary conditions for graphs to be isomorphic with an example.[2+8]
--- (a) Difference Between Graph and Tree Graph Tree --------------------- A graph is a collection of vertices (nodes) and edges with no restrictions on cycles. A tree is a connected, acyclic (no cycles) undirected graph. A graph may or ...
- 310 marksNumericalSolving recurrence relations with initial HideAnswer
Define randomized algorithm with an example. Solve the recurrence relation $a_n = -4a_{n-1} - 4a_{n-2}$ for $n \ge 2$, with initial condition $a_0 = 0$ and $a_1 = 1$. [3+7]
- Recurrence: $an = -4a{n-1} - 4a{n-2}$ for $n \geq 2$ - Initial conditions: $a0 = 0$, $a1 = 1$ All required data present. --- A randomized algorithm is an algorithm that makes one or more of its decisions based on random numbers generat...
- 45 marksNegation of statementsHideAnswer
List the negations of following statements: (a) He has passed the exam. (b) All dogs are loyal. (c) Some medicine has side effect. (d) If you study then you will pass the exam. (e) Open the door. [5]
Negation: He has not passed the exam. --- Negation: Some dogs are not loyal. Note: The negation of a universal statement ("All A are B") is an existential statement ("Some A are not B").) --- Negation: No medicine has side effect. (i.e.,...
- 55 marksKruskal's algorithmHideAnswer
How does Kruskal algorithm work? Illustrate with an example. [5]
Kruskal's algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, undirected, weighted graph. It builds the MST by always picking the smallest available edge that does not form a cycle. --- 1. Sort al...
- 65 marksNumericalGeneralized pigeonhole principleHideAnswer
State generalized Pigeonhole principle. How many ways can we get the 3 digit integers without repeating the digit? [5]
- Digits available: $0,1,2,3,4,5,6,7,8,9$ (10 digits total) - Form: 3-digit integer, no digit repeated - Implicit constraint: leading digit (hundreds place) $\neq 0$ --- Statement: If $N$ objects are placed into $k$ boxes, then there is ...
- 75 marksDirect proofHideAnswer
Using direct proof show that the sum of square of even number is even. [5]
If $n$ is an even number, then $n^2$ is even. --- - An integer $n$ is even if there exists an integer $k$ such that $n = 2k$. - An integer $m$ is even if there exists an integer $j$ such that $m = 2j$. --- Given: $n$ is an even integer. ...
- 85 marksEquivalence relationsHideAnswer
Define equivalence relation. How do you represent relation? [5]
Equivalence Relation and Representation of Relations
Definition: Equivalence Relation
A relation R on a set A is called an equivalence relation if it satisfies the following three properties simultaneously:
1. Reflexive
For every element $a \in A$: $$a \mathrel{R} a$$ Every element is related to itself.
2. Symmetric
For all $a, b \in A$: $$a \mathrel{R} b \implies b \mathrel{R} a$$
3. Transitive
For all $a, b, c \in A$: $$a \mathrel{R} b \text{ and } b \mathrel{R} c \implies a \mathrel{R} c$$
Example: Let $A = {1, 2, 3}$ and define $R$ as "has the same remainder when divided by 2." Then $R$ is reflexive, symmetric, and transitive, so it is an equivalence relation.
Representation of Relations
A relation can be represented in the following ways:
1. Set of Ordered Pairs (Roster Method)
List all pairs $(a, b)$ such that $a \mathrel{R} b$.
Example: $$R = {(1,1),\ (2,2),\ (1,2),\ (2,1)}$$
2. Matrix Representation (Boolean Matrix)
Given sets $A = {a_1, a_2, \ldots, a_m}$ and $B = {b_1, b_2, \ldots, b_n}$, define matrix $M_R$ where:
$$M_R[i][j] = \begin{cases} 1 & \text{if } (a_i, b_j) \in R \ 0 & \text{if } (a_i, b_j) \notin R \end{cases}$$
Example: For $A = {1, 2, 3}$ and $R = {(1,1),(1,2),(2,3),(3,1)}$:
$$M_R = \begin{pmatrix} 1 & 1 & 0 \ 0 & 0 & 1 \ 1 & 0 & 0 \end{pmatrix}$$
3. Directed Graph (Digraph) Representation
- Each element of the set is represented as a node (vertex).
- A directed edge (arrow) is drawn from node $a$ to node $b$ if $(a, b) \in R$.
Example: For $R = {(1,2),(2,3),(3,1)}$:
$$1 \rightarrow 2 \rightarrow 3 \rightarrow 1$$
4. Arrow Diagram
- Elements of domain set $A$ are listed on the left.
- Elements of codomain set $B$ are listed on the right.
- Arrows are drawn from $a$ to $b$ whenever $(a, b) \in R$.
Summary Table
Method Best Used For Ordered Pairs Small, explicit relations Boolean Matrix Computation and composition Digraph Visualizing properties (reflexive, symmetric, etc.) Arrow Diagram Functions and mappings - 95 marksChinese Remainder TheoremHideAnswer
How do you solve computer arithmetic with large integers using Chinese remainder theorem? Give an example. [5]
Modern computers have a fixed word size (e.g., 32-bit or 64-bit). When performing arithmetic on very large integers, the numbers may exceed the machine's word size, causing overflow. The Chinese Remainder Theorem (CRT) provides an elegan...
- 105 marksDijkstra's algorithm for shortest pathsHideAnswer
Write Dijkstra’s algorithm to find the shortest path from source node to goal node. [5]
Dijkstra's algorithm finds the shortest path from a source node to all other nodes (or a specific goal node) in a weighted graph with non-negative edge weights. --- - dist[] : array storing shortest distance from source to each node - vi...
- 115 marksNumericalFunction plottingHideAnswer
How do you plot graph for function $f(x) = x + 1$? Define ceiling, floor and exponential function. [5]
- Function to plot: $f(x) = x + 1$ - Terms to define: ceiling function, floor function, exponential function --- This is a linear function of the form $f(x) = mx + c$ with slope $m = 1$ and y-intercept $c = 1$. Steps to plot: 1. Identify...
- 125 marksRules of inferenceHideAnswer
List any five rules of inferences. [5]
Rules of Inference
Rules of inference are valid argument forms used to derive conclusions from premises in logical reasoning.
Five Rules of Inference
1. Modus Ponens (Law of Detachment)
$$p$$ $$p \rightarrow q$$ $$\therefore q$$
Meaning: If $p$ is true, and $p \rightarrow q$ is true, then $q$ must be true.
Example: "It is raining. If it rains, the ground is wet. Therefore, the ground is wet."
2. Modus Tollens
$$\neg q$$ $$p \rightarrow q$$ $$\therefore \neg p$$
Meaning: If $q$ is false and $p \rightarrow q$ is true, then $p$ must be false.
3. Hypothetical Syllogism
$$p \rightarrow q$$ $$q \rightarrow r$$ $$\therefore p \rightarrow r$$
Meaning: If $p$ implies $q$, and $q$ implies $r$, then $p$ implies $r$ (chain rule).
4. Disjunctive Syllogism
$$p \lor q$$ $$\neg p$$ $$\therefore q$$
Meaning: If at least one of $p$ or $q$ is true, and $p$ is false, then $q$ must be true.
5. Addition (Disjunction Introduction)
$$p$$ $$\therefore p \lor q$$
Meaning: If $p$ is true, then $p \lor q$ is true for any proposition $q$.
Note: Other common rules include Simplification ($p \land q \therefore p$), Conjunction ($p, q \therefore p \land q$), and Resolution. Each rule represents a tautology of the form: (premises) $\rightarrow$ conclusion.