Answers

1) Define the following with an example

a) Composite number (Even and Odd)

Composite Numbers: A composite number has more than two factors, which means apart from getting divided by the number 1 and itself, it can also be divided by at least one integer or number. We don't consider '1' as a composite number.

Example (from lecture idea): 12 is composite because it can be divided by 1, 2, 3, 4, 6 and 12 → more than two factors.

• Even composite example: 12 (even and composite)
• Odd composite example: 15 (factors: 1, 3, 5, 15 → composite and odd)

b) Perfect number

Perfect Numbers: A Perfect Number N is defined as any positive integer where the sum of its divisors minus the number itself equals the number.

Formula: Sum of proper divisors (excluding N) = N.

That means: Sum of proper divisors (divisors excluding itself) = the number.

Example: 6 → divisors: 1, 2, 3, 6 Proper divisors: 1, 2, 3 1+2+3 = 6 ✅ so 6 is perfect.

c) Lucas number

Lucas numbers: Lucas numbers are similar to Fibonacci numbers. Lucas numbers are also defined as the sum of its two immediately previous terms. But here the first two terms are 2 and 1 whereas in Fibonacci numbers the first two terms are 0 and 1 respectively.

Formula: $L_n = L_{n-1} + L_{n-2}$ (with $L_0 = 2$, $L_1 = 1$).

Lucas sequence: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123…

d) Fibonacci number

Fibonacci Sequence: The Fibonacci sequence is the series of numbers where each number is the sum of the two preceding numbers.

The Rule is:

$$F_n = F_{n-1} + F_{n-2}$$

(where $n \ge 2$)

Example sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…

e) Deficient number

Deficient Number: The sum of the factors (excluding itself) is less than the number.

Formula: $\text{sum of proper divisors} < N$.

Example (lecture style): Find out 8 is deficient number or not. Factors of 8 are 1, 2, 4 So, 1+2+4 = 7 Here 7 is less than 8 → ✅ deficient.

f) Abundant number

Abundant: The sum of the factors (excluding itself) is greater than the number.

Formula: $\text{sum of proper divisors} > N$.

Example (lecture style): 18 → factors excluding itself: 1, 2, 3, 6, 9 Sum = 1+2+3+6+9 = 21 21 is greater than 18 → ✅ abundant.

g) Prime number

Prime Numbers: A prime number is one that has exactly two factors, which means it can be divided by only "1" and itself. But "1" is not a prime number.

Example: 3 is prime because it can be divided by only 1 and 3.

---

2) Find the Lucas number between 10 and 100

Formula: $L_n = L_{n-1} + L_{n-2}$ with $L_0 = 2$, $L_1 = 1$.

Lucas numbers: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123…

Between 10 and 100 are:

• ✅ 11, 18, 29, 47, 76

---

3) Find the Fibonacci number between 10 and 100

Formula: $F_n = F_{n-1} + F_{n-2}$ (with $F_0 = 0$, $F_1 = 1$).

Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144…

Between 10 and 100 are:

• ✅ 13, 21, 34, 55, 89

---

4) Find all the perfect numbers from 1 to 1000

Formula: A number $N$ is perfect if sum of proper divisors = $N$ (i.e. $\sigma(N) - N = N$).

From the lecture list: first perfect numbers are 6, 28, 496, 8128… Up to 1000 are:

• ✅ 6, 28, 496

---

5) Check whether numbers are perfect or not (if not, give category)

Formulas:

• Perfect: $\text{sum(proper divisors)} = N$
• Deficient: $\text{sum(proper divisors)} < N$
• Abundant: $\text{sum(proper divisors)} > N$

a) 496

496 is a known perfect number from the lecture list. ✅ Perfect

b) 520

520 has many factors (so sum of factors excluding itself becomes greater than the number). ✅ Abundant

c) 320

320 has many factors (sum of factors excluding itself > number). ✅ Abundant

d) 630

630 has many factors (sum of factors excluding itself > number). ✅ Abundant

---

6) Explain the Quotient Remainder Theorem with an example

Formula: $a = bq + r$, where $0 \le r < b$ ($q$ = quotient, $r$ = remainder).

(From number theory idea used in lectures)

Statement: For integers $a$ and $b > 0$, there exist unique integers $q$ and $r$ such that:

$$a = bq + r,\quad 0 \le r < b$$

Example: Let $a = 29$, $b = 5$. 29 ÷ 5 = 5 remainder 4 So:

$$29 = 5(5) + 4,\quad 0 \le 4 < 5$$

✅ $q = 5$, $r = 4$

---

7) Caesar cipher: Encrypt and Decrypt "SCHOLARS", key (shift) = 3

Formulas: $E_n(x) = (x + n) \bmod 26$ (encrypt); $D_n(x) = (x_i - n) \bmod 26$ (decrypt). Letters A=0, B=1, …, Z=25.

Lecture formulas:

• Encryption Formula: $E_n(x) = (x + n) \bmod 26$
• Decryption Formula: $D_n(x) = (x_i - n) \bmod 26$

Encryption (n = 3)

Lecture mapping style (A=00, B=01, …, Z=25):

S → 18 $(18+3) \bmod 26 = 21 \Rightarrow V$

Do all letters (same as lecture table method):

• S → V
• C → F
• H → K
• O → R
• L → O
• A → D
• R → U
• S → V

✅ Ciphertext = VFKRODUV

Decryption (n = 3)

Now apply:

$$D_n(x) = (x_i - 3) \bmod 26$$

Example first letter:

V → 21

$$(21-3) \bmod 26 = 18 \Rightarrow S$$

Doing all returns: ✅ SCHOLARS

---

8) Caesar cipher: Encrypt and Decrypt "ASSIGNMENT", key = 4

Formulas: $E_n(x) = (x+n) \bmod 26$ (encrypt); $D_n(x) = (x_i - n) \bmod 26$ (decrypt).

Encryption (n = 4)

Apply $E_n(x) = (x+4) \bmod 26$

A→E, S→W, S→W, I→M, G→K, N→R, M→Q, E→I, N→R, T→X

✅ Ciphertext = EWWMKRQIRX

Decryption (n = 4)

Apply $D_n(x) = (x_i-4) \bmod 26$

EWWMKRQIRX → ✅ ASSIGNMENT

---

9) Handshaking Lemma (20 edges)

Formula: $\sum \deg(v) = 2E$ (sum of all vertex degrees = twice the number of edges).

Lecture definition:

Handshaking Lemma: The sum of degree of all the vertices for a graph will be double the number of edges.

So:

$$\sum \deg(v) = 2E = 2 \times 20 = 40$$

Given:

• 3 vertices degree 5 → sum = 3×5 = 15
• 7 vertices degree 3 → sum = 7×3 = 21 Current sum = 15+21 = 36

Let remaining vertices be $x$, each has degree 2:

$$36 + 2x = 40 \Rightarrow 2x = 4 \Rightarrow x = 2$$

Total vertices:

$$3 + 7 + 2 = 12$$

✅ Total vertices = 12

---

10) Handshaking Lemma (22 edges)

Formula: $\sum \deg(v) = 2E$.

$$\sum \deg(v) = 2E = 2 \times 22 = 44$$

Given:

• 6 vertices degree 5 → 6×5 = 30
• 4 vertices degree 3 → 4×3 = 12 Sum = 42

Remaining vertices degree 3: let count = $x$

$$42 + 3x = 44 \Rightarrow 3x = 2$$

But $x$ must be an integer (number of vertices). 2/3 is not an integer.

✅ So, this is NOT possible (no such graph exists with this data).

---

11) Find GCD & LCM of 33 and 12 using the formula

Formula: $LCM(A,B) = \dfrac{A \times B}{GCD(A,B)}$ (find GCD by Euclidean algorithm first).

Lecture formula:

$$LCM(A,B) = \frac{A \times B}{GCD(A,B)}$$

First find GCD(33, 12) using the lecture "Procedure" (Euclidean method style):

• 33 = 12×2 + 9
• 12 = 9×1 + 3
• 9 = 3×3 + 0 So, ✅ GCD = 3

Now:

$$LCM(33,12) = \frac{33 \times 12}{3} = 132$$

✅ GCD = 3, LCM = 132

---

12) Find GCD & LCM of 95 and 496 using the formula

Formula: $LCM(A,B) = \dfrac{A \times B}{GCD(A,B)}$; if no common factor then $GCD = 1$.

Check common factor:

• 95 = 5×19
• 496 = 2⁴×31 No common factor → ✅ GCD = 1

$$LCM(95,496) = \frac{95 \times 496}{1} = 47120$$

✅ GCD = 1, LCM = 47120

---

13) MST using Prim's and Kruskal's (Start = 1) and check equal or not

Formulas: MST has exactly $|V|-1$ edges. Kruskal: sort edges by weight, add smallest edge that does not form a cycle. Prim's: start at given vertex, repeatedly add minimum-weight edge to a new vertex.

Kruskal (lecture procedure)

Step 1: Sort all edges in increasing order of their edge weights. Sorted: 10, 12, 14, 16, 18, 22, 24, 25, 28

Step 2: Pick the smallest edge. Pick (1–6)=10 ✅

Step 3: Check cycle (if cycle, discard). Continue picking smallest non-cycle edges:

• (3–4)=12 ✅
• (2–7)=14 ✅
• (2–3)=16 ✅
• (7–4)=18 ❌ (cycle formed) discard
• (4–5)=22 ✅
• (5–6)=25 ✅

Now we have $|V|-1 = 6$ edges.

✅ MST edges (Kruskal): (1–6), (3–4), (2–7), (2–3), (4–5), (5–6) Total weight = 10+12+14+16+22+25 = ✅ 99

Prim's method (start at 1) — lecture "step style"

Step 1: Start from vertex 1, choose least cost edge from 1. From 1: (1–6)=10, (1–2)=28 → pick (1–6)=10 Now visited:

Step 2: From current tree, choose least cost edge that connects a new vertex. Candidate edges: (6–5)=25, (1–2)=28 → pick (6–5)=25 Visited:

Step 3: Candidates: (5–4)=22, (5–7)=24, (1–2)=28 → pick (5–4)=22 Visited:

Step 4: Candidates: (4–3)=12, (4–7)=18, (1–2)=28 → pick (4–3)=12 Visited:

Step 5: Candidates: (3–2)=16, (4–7)=18, (1–2)=28 → pick (3–2)=16 Visited:

Step 6: Candidates: (2–7)=14, (4–7)=18, (5–7)=24 → pick (2–7)=14 Visited: all nodes

Total weight = 10+25+22+12+16+14 = ✅ 99

✅ Result: Prim's MST cost = 99 and Kruskal MST cost = 99 → equal

---

14) MST using Prim's and Kruskal's (Start = a) and check equal or not

Formulas: Same as Q13 — Kruskal: sort edges, pick smallest non-cycle; Prim's: start at given vertex, add min-cost edge to new vertex. MST has $|V|-1$ edges.

Note: in your picture, the rightmost vertex is labeled "e" again. To avoid confusion, I will call it g (rightmost vertex).

Edges with weights: a–b(1), a–c(5), b–c(4), b–d(8), c–d(6), b–e(7), d–e(11), d–f(9), c–f(2), e–f(3), e–g(10), f–g(12)

Kruskal (lecture procedure)

Sort edges by weight: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12

Pick smallest non-cycle:

• a–b(1) ✅
• c–f(2) ✅
• e–f(3) ✅
• b–c(4) ✅
• a–c(5) ❌ (cycle) discard
• c–d(6) ✅
• b–e(7) ❌ (cycle) discard
• e–g(10) ✅

Now we have 6 edges (for 7 vertices).

Total = 1+2+3+4+6+10 = ✅ 26

Prim (start at a) — step style

Start at a:

• Pick a–b(1) Now
• From {a, b} smallest to new: b–c(4) (better than a–c(5)) Now
• Next smallest to new: c–f(2) Now
• Next smallest to new: f–e(3) Now
• Next smallest to new: c–d(6) Now
• Remaining new vertex g: smallest is e–g(10)

Total = 1+4+2+3+6+10 = ✅ 26

✅ Result: Prim's = 26 and Kruskal = 26 → equal

---

15) Differentiate between Bipartite & Complete Bipartite Graph

Formula (Complete Bipartite): Number of edges = $|V_1| \cdot |V_2| = m \cdot n$.

Bipartite Graph:If the vertex-set of a graph G can be split into two disjoint sets, $V_1$ and $V_2$, in such a way that each edge in the graph joins a vertex in $V_1$ to a vertex in $V_2$, and there are no edges in G that connect two vertices in $V_1$ or two vertices in $V_2$, then the graph G is called a bipartite graph.

Complete Bipartite Graph:A graph $G=(V,E)$ is called a complete bipartite graph if its vertices V can be partitioned into two subsets $V_1$ and $V_2$ such that each vertex of $V_1$ is connected to each vertex of $V_2$. Also from lecture: number of edges = m·n

---

16) Differentiate between Cyclic & Acyclic & Directed Acyclic Graph

• Cyclic graph: a graph that contains a cycle.
• Acyclic graph: a graph that does not contain any cycle.
• Directed Acyclic Graph (DAG): a directed graph that does not contain any cycles.

---

17) Differentiate between Planar & Non-Planar Graph

Planar Graphs: A planar graph is a graph that can be embedded in the plane such that no edges intersect except at their endpoints. (meaning: draw without edge crossing)

Non-Planar Graph: A graph is said to be non planar if it cannot be drawn in a plane so that no edge cross.

---

18) Searching (show all steps)

Formulas:

• Linear search: Compare key with each element from index 0 until match or end.
• Binary search: $\text{mid} = \lfloor (\text{low} + \text{high}) / 2 \rfloor$; if key < value go left, else go right. (Array must be sorted.)

Array: 10 20 30 40 50 60 70 80 90

a) Linear Search for 40 (lecture steps)

Step 1: Start from the 0'th index, compare key with array[0]. 40 vs 10 → not match

Step 2: Compare key with next element. 40 vs 20 → not match

Step 3: Compare key with next element. 40 vs 30 → not match

Step 4: Compare key with next element. 40 vs 40 → match found ✅

✅ So, 40 is found at index 3 (0-based) or position 4 (1-based).

b) Binary Search for 30 (lecture procedure)

(Works only on sorted list — it is sorted.)

Array indices (0-based): 0..8 Values: 10..90

Step 1: Select middle item and compare with key. low=0, high=8 → mid=(0+8)//2=4 → value=50 30 < 50 → go to left sub-array (lecture Step 3)

Step 2: Left sub-array low=0, high=3 mid=(0+3)//2=1 → value=20 30 > 20 → go to right sub-array

Step 3: low=2, high=3 mid=(2+3)//2=2 → value=30 Match ✅ return position.

✅ 30 found at index 2 (0-based) or position 3 (1-based).

---

19) Sorting: 14 33 27 35 10

Formulas:

• Bubble sort: Compare adjacent pairs; swap if out of order; repeat until no swaps.
• Merge sort: Divide into halves until single elements → Conquer (merge sorted halves) → Combine.

a) Bubble Sort (lecture steps idea: swap adjacent if needed)

Start: [14, 33, 27, 35, 10]

Pass 1 (compare adjacent):

• (14, 33) ok → [14, 33, 27, 35, 10]
• (33, 27) swap → [14, 27, 33, 35, 10]
• (33, 35) ok → [14, 27, 33, 35, 10]
• (35, 10) swap → [14, 27, 33, 10, 35]

Pass 2:

• (14, 27) ok
• (27, 33) ok
• (33, 10) swap → [14, 27, 10, 33, 35]

Pass 3:

• (14, 27) ok
• (27, 10) swap → [14, 10, 27, 33, 35]

Pass 4:

• (14, 10) swap → ✅ [10, 14, 27, 33, 35]

b) Merge Sort (lecture: Divide – Conquer – Combine)

Array: [14, 33, 27, 35, 10]

Divide:

• Left: [14, 33, 27]
• Right: [35, 10]

Divide left:

• [14] and [33, 27]
• [33] and [27]

Conquer (sort small parts):

• merge([33], [27]) → [27, 33]
• merge([14], [27, 33]) → [14, 27, 33] Right side:
• merge([35], [10]) → [10, 35]

Combine (final merge): merge([14, 27, 33], [10, 35]) → ✅ [10, 14, 27, 33, 35]

---

20) Relation properties (A = {1, 2, 3, 4}) — lecture definitions used

Formulas (properties):

From lecture:

• Reflexive: $\forall a\,((a, a) \in R)$
• Irreflexive: $\forall a\,((a, a) \notin R)$
• Symmetric: $\forall a \forall b\,((a, b) \in R \rightarrow (b, a) \in R)$
• Asymmetric: $\forall a \forall b\,((a, b) \in R \rightarrow (b, a) \notin R)$
• Antisymmetric: $\forall a \forall b\,(((a, b) \in R \wedge (b, a) \in R) \rightarrow (a = b))$
• Transitive: $\forall a \forall b \forall c\,(((a, b) \in R \wedge (b, c) \in R) \rightarrow (a, c) \in R)$

Checking each relation in that same way.

a) R1 =

• Reflexive? (1,1) (2,2) (3,3) (4,4) all present → ✅ Reflexive
• Irreflexive? No (because (1,1) etc exist) → ❌
• Symmetric? (2,4) exists and (4,2) exists; all self-pairs symmetric → ✅ Symmetric
• Asymmetric? If (2,4) then (4,2) must NOT exist, but it exists → ❌
• Antisymmetric? (2,4) and (4,2) both exist with 2≠4 → ❌
• Transitive?
  • (2,4) and (4,2) ⇒ must have (2,2) (exists)
  • (4,2) and (2,4) ⇒ must have (4,4) (exists) Self-pairs keep it true → ✅ Transitive

✅ R1: Irreflexive ❌, Asymmetric ❌, Antisymmetric ❌, Reflexive ✅, Symmetric ✅, Transitive ✅

b) R2 =

• Reflexive? (1,1) missing → ❌
• Irreflexive? None of (1,1) (2,2) (3,3) (4,4) are present → ✅
• Symmetric? (1,2) exists but (2,1) not → ❌
• Asymmetric? Check reverse pairs:
  • (1,2) but (2,1) not present ✅
  • (2,4) but (4,2) not present ✅
  • (3,1) but (1,3) not present ✅ Also no (a,a) pairs, so ✅ Asymmetric
• Antisymmetric? There is no pair (a,b) and (b,a) for $a \neq b$ → ✅
• Transitive? (3,1) and (1,2) would require (3,2), but not present → ❌

✅ R2: Irreflexive ✅, Asymmetric ✅, Antisymmetric ✅, Reflexive ❌, Symmetric ❌, Transitive ❌

c) R3 =

• Reflexive? All (a,a) exist → ✅
• Irreflexive? ❌
• Symmetric? (2,3) exists but (3,2) not → ❌
• Asymmetric? Impossible because has (1,3) and (3,1) → ❌
• Antisymmetric? Fails because (1,3) and (3,1) and 1≠3 → ❌
• Transitive? (2,3) and (3,1) would require (2,1), not present → ❌

✅ R3: Irreflexive ❌, Asymmetric ❌, Antisymmetric ❌, Reflexive ✅, Symmetric ❌, Transitive ❌

d) R4 =

• Reflexive? All (a,a) exist → ✅
• Irreflexive? ❌
• Symmetric? (4,1) exists but (1,4) not → ❌
• Asymmetric? Cannot (because reflexive pairs exist) → ❌
• Antisymmetric? No (a,b) & (b,a) with $a \neq b$ → ✅
• Transitive? (4,1) and (1,2) would require (4,2), not present → ❌

✅ R4: Irreflexive ❌, Asymmetric ❌, Antisymmetric ✅, Reflexive ✅, Symmetric ❌, Transitive ❌

e) R5 = A × A

This contains all ordered pairs.

So automatically:

• Reflexive ✅ (all (a,a) exist)
• Symmetric ✅ (if (a,b) exists then (b,a) also exists)
• Transitive ✅ (if (a,b) and (b,c), then (a,c) is also in A×A)
• Irreflexive ❌
• Asymmetric ❌
• Antisymmetric ❌

✅ R5: Irreflexive ❌, Asymmetric ❌, Antisymmetric ❌, Reflexive ✅, Symmetric ✅, Transitive ✅

f) R6 =

• Reflexive? All (a,a) exist → ✅
• Irreflexive? ❌
• Symmetric? (1,3) exists and (3,1) exists → ✅
• Asymmetric? Fails because reverse exists → ❌
• Antisymmetric? Fails because (1,3) and (3,1) with 1≠3 → ❌
• Transitive?
  • (1,3) and (3,1) ⇒ need (1,1) (exists)
  • (3,1) and (1,3) ⇒ need (3,3) (exists) So ✅ Transitive

✅ R6: Irreflexive ❌, Asymmetric ❌, Antisymmetric ❌, Reflexive ✅, Symmetric ✅, Transitive ✅

---

IUS Preps - Your Academic Success Partner