Answers

1) Define the following with an example

a) Composite number (Even and Odd)

Composite Numbers: A composite number has more than two factors. Besides 1 and itself, it is divisible by at least one more integer. We do not consider 1 as a composite number.

Example:
12 is composite because it can be divided by 1, 2, 3, 4, 6, and 12 $\Rightarrow$ more than two factors.

• Even composite example: 12
• Odd composite example: 15 (factors: 1, 3, 5, 15 $\Rightarrow$ composite and odd)

b) Perfect number

Perfect Number: A positive integer $N$ is perfect if the sum of its proper divisors equals the number.

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

Example:
$6 \Rightarrow$ 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. Each term is the sum of the previous two terms, but the first two terms are 2 and 1.

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: Each number is the sum of the two preceding numbers.

Formula:
$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 proper divisors is less than the number.

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

Example:
Factors of 8 are 1, 2, 4
$1+2+4 = 7$
$7 < 8 \Rightarrow$ deficient

f) Abundant number

Abundant Number: The sum of the proper divisors is greater than the number.

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

Example:
$18 \Rightarrow$ factors excluding itself: 1, 2, 3, 6, 9
Sum $= 1+2+3+6+9 = 21$
$21 > 18 \Rightarrow$ abundant

g) Prime number

Prime Number: A prime number has exactly two factors: 1 and itself. 1 is not prime.

Example: 3 is prime because it is divisible by only 1 and 3.

---

2) Find the Lucas numbers 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:

• 11, 18, 29, 47, 76

---

3) Find the Fibonacci numbers between 10 and 100

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

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

Between 10 and 100:

• 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$.

From the lecture list: 6, 28, 496, 8128...

Up to 1000:

• 6, 28, 496

---

5) Check whether numbers are perfect or not

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.
Perfect

b) 520

520 has many factors, so the sum of proper divisors is greater than the number.
Abundant

c) 320

320 has many factors, so the sum of proper divisors is greater than the number.
Abundant

d) 630

630 has many factors, so the sum of proper divisors is greater than the number.
Abundant

---

6) Explain the Quotient Remainder Theorem with an example

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

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) + 4,\quad 0 \le 4 < 5$$

So, $q = 5$ and $r = 4$.

---

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

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

Letters: $A=0$, $B=1$, ..., $Z=25$

Encryption ($n = 3$)

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

Do all letters:

• $S \Rightarrow V$
• $C \Rightarrow F$
• $H \Rightarrow K$
• $O \Rightarrow R$
• $L \Rightarrow O$
• $A \Rightarrow D$
• $R \Rightarrow U$
• $S \Rightarrow V$

Ciphertext = VFKRODUV

Decryption ($n = 3$)

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

$V \Rightarrow 21$

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

Doing all letters returns:

SCHOLARS

---

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

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

Encryption ($n = 4$)

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

$A \Rightarrow E$, $S \Rightarrow W$, $S \Rightarrow W$, $I \Rightarrow M$, $G \Rightarrow K$, $N \Rightarrow R$, $M \Rightarrow Q$, $E \Rightarrow I$, $N \Rightarrow R$, $T \Rightarrow X$

Ciphertext = EWWMKRQIRX

Decryption ($n = 4$)

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

$$\text{EWWMKRQIRX} \Rightarrow \text{ASSIGNMENT}$$

---

9) Handshaking Lemma (20 edges)

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

So:

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

Given:

• 3 vertices degree 5 $\Rightarrow 3 \times 5 = 15$
• 7 vertices degree 3 $\Rightarrow 7 \times 3 = 21$

Current sum:

$$15 + 21 = 36$$

Let remaining vertices be $x$, each 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) = 2 \times 22 = 44$$

Given:

• 6 vertices degree 5 $\Rightarrow 6 \times 5 = 30$
• 4 vertices degree 3 $\Rightarrow 4 \times 3 = 12$

Sum:

$$30 + 12 = 42$$

Remaining vertices degree 3: let count = $x$

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

But $x$ must be an integer. So this is not possible.

No such graph exists with this data.

---

11) Find GCD & LCM of 33 and 12

Formula:

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

First find $GCD(33,12)$ using Euclidean algorithm:

• $33 = 12 \times 2 + 9$
• $12 = 9 \times 1 + 3$
• $9 = 3 \times 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

Formula:

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

Check common factors:

• $95 = 5 \times 19$
• $496 = 2^4 \times 31$

No common factor $\Rightarrow 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)

Formula: MST has exactly $|V|-1$ edges.

Kruskal

Sort edge weights:

$$10,\ 12,\ 14,\ 16,\ 18,\ 22,\ 24,\ 25,\ 28$$

Pick smallest non-cycle edges:

• $(1,6)=10$
• $(3,4)=12$
• $(2,7)=14$
• $(2,3)=16$
• $(7,4)=18$ discard (cycle)
• $(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)

From 1:

• $(1,6)=10$, $(1,2)=28 \Rightarrow$ pick $(1,6)=10$

Visited: $\{1,6\}$

• Candidate: $(6,5)=25$, $(1,2)=28 \Rightarrow$ pick $(6,5)=25$
• Candidate: $(5,4)=22$, $(5,7)=24$, $(1,2)=28 \Rightarrow$ pick $(5,4)=22$
• Candidate: $(4,3)=12$, $(4,7)=18$, $(1,2)=28 \Rightarrow$ pick $(4,3)=12$
• Candidate: $(3,2)=16$, $(4,7)=18$, $(1,2)=28 \Rightarrow$ pick $(3,2)=16$
• Candidate: $(2,7)=14$, $(4,7)=18$, $(5,7)=24 \Rightarrow$ pick $(2,7)=14$

Total weight:

$$10+25+22+12+16+14 = 99$$

Result: Prim's MST cost = 99 and Kruskal MST cost = 99, so they are equal.

---

14) MST using Prim's and Kruskal's (Start = a)

Formula: Same as Question 13.

Note: In the picture, the rightmost vertex is labeled "e" again. Here it is treated as $g$.

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

Pick smallest non-cycle edges:

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

Total:

$$1+2+3+4+6+10 = 26$$

Prim (start at $a$)

• Pick $a$-$b(1)$
• From $\{a,b\}$ pick $b$-$c(4)$
• Next pick $c$-$f(2)$
• Next pick $f$-$e(3)$
• Next pick $c$-$d(6)$
• Next pick $e$-$g(10)$

Total:

$$1+4+2+3+6+10 = 26$$

Result: Prim's = 26 and Kruskal = 26, so they are equal.

---

15) Differentiate between Bipartite & Complete Bipartite Graph

Formula (Complete Bipartite):

$$|E| = |V_1| \cdot |V_2| = m \cdot n$$

Bipartite Graph: A graph whose vertex set can be split into two disjoint sets $V_1$ and $V_2$ such that every edge joins a vertex in $V_1$ to a vertex in $V_2$.

Complete Bipartite Graph: A bipartite graph in which every vertex of $V_1$ is connected to every vertex of $V_2$.

---

16) Differentiate between Cyclic, Acyclic, and DAG

• Cyclic graph: contains a cycle
• Acyclic graph: contains no cycle
• Directed Acyclic Graph (DAG): a directed graph with no directed cycles

---

17) Differentiate between Planar & Non-Planar Graph

• Planar graph: can be drawn in a plane without edge crossings except at endpoints
• Non-planar graph: cannot be drawn in a plane without edge crossings

---

18) Searching (show all steps)

Formulas:

• Linear search: compare key with each element from index 0 until match or end
• Binary search: $mid = \lfloor (low + high)/2 \rfloor$; if key $<$ value go left, else go right

Array: 10 20 30 40 50 60 70 80 90

a) Linear Search for 40

• $40$ vs $10 \Rightarrow$ not match
• $40$ vs $20 \Rightarrow$ not match
• $40$ vs $30 \Rightarrow$ not match
• $40$ vs $40 \Rightarrow$ match

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

b) Binary Search for 30

Array is sorted.

• $low=0$, $high=8 \Rightarrow mid=(0+8)//2=4 \Rightarrow value=50$
• $30 < 50 \Rightarrow$ go left
• $low=0$, $high=3 \Rightarrow mid=(0+3)//2=1 \Rightarrow value=20$
• $30 > 20 \Rightarrow$ go right
• $low=2$, $high=3 \Rightarrow mid=(2+3)//2=2 \Rightarrow value=30$
• Match

So, 30 is 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 -> Conquer -> Combine

a) Bubble Sort

Start:

$$[14, 33, 27, 35, 10]$$

Pass 1

• $(14, 33)$ ok $\Rightarrow [14, 33, 27, 35, 10]$
• $(33, 27)$ swap $\Rightarrow [14, 27, 33, 35, 10]$
• $(33, 35)$ ok $\Rightarrow [14, 27, 33, 35, 10]$
• $(35, 10)$ swap $\Rightarrow [14, 27, 33, 10, 35]$

Pass 2

• $(14, 27)$ ok
• $(27, 33)$ ok
• $(33, 10)$ swap $\Rightarrow [14, 27, 10, 33, 35]$

Pass 3

• $(14, 27)$ ok
• $(27, 10)$ swap $\Rightarrow [14, 10, 27, 33, 35]$

Pass 4

• $(14, 10)$ swap $\Rightarrow [10, 14, 27, 33, 35]$

b) Merge Sort

Start:

$$[14, 33, 27, 35, 10]$$

Divide

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

Further divide:

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

Conquer

• $merge([33],[27]) \Rightarrow [27,33]$
• $merge([14],[27,33]) \Rightarrow [14,27,33]$
• $merge([35],[10]) \Rightarrow [10,35]$

Combine

• $merge([14,27,33],[10,35]) \Rightarrow [10,14,27,33,35]$

---

20) Relation properties ($A = \{1,2,3,4\}$)

Property formulas:

• 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)$

a) $R_1 = \{(1,1), (2,2), (3,3), (4,4), (2,4), (4,2)\}$

• Reflexive? Yes
• Irreflexive? No
• Symmetric? Yes
• Asymmetric? No
• Antisymmetric? No
• Transitive? Yes

b) $R_2 = \{(1,2), (2,4), (1,4), (3,1)\}$

• Reflexive? No
• Irreflexive? Yes
• Symmetric? No
• Asymmetric? Yes
• Antisymmetric? Yes
• Transitive? No

c) $R_3 = \{(1,1), (2,2), (3,3), (4,4), (1,3), (3,1), (2,3)\}$

• Reflexive? Yes
• Irreflexive? No
• Symmetric? No
• Asymmetric? No
• Antisymmetric? No
• Transitive? No

d) $R_4 = \{(1,1), (2,2), (3,3), (4,4), (4,1), (1,2)\}$

• Reflexive? Yes
• Irreflexive? No
• Symmetric? No
• Asymmetric? No
• Antisymmetric? Yes
• Transitive? No

e) $R_5 = A \times A$

• Reflexive? Yes
• Irreflexive? No
• Symmetric? Yes
• Asymmetric? No
• Antisymmetric? No
• Transitive? Yes

f) $R_6 = \{(1,1), (2,2), (3,3), (4,4), (1,3), (3,1)\}$

• Reflexive? Yes
• Irreflexive? No
• Symmetric? Yes
• Asymmetric? No
• Antisymmetric? No
• Transitive? Yes

---

IUS Preps - Your Academic Success Partner