Quick Revision

1) Number definitions (with examples)

Term	Definition	Example
Composite	More than two factors (not 1).	12: 1,2,3,4,6,12. Even: 12; Odd: 15
Perfect	Sum of proper divisors = number.	6: 1+2+3 = 6
Lucas	Like Fibonacci; first two terms 2, 1.	2, 1, 3, 4, 7, 11, 18, 29, 47, 76…
Fibonacci	Each term = sum of two preceding; first two 0, 1.	$F_n = F_{n-1} + F_{n-2}$; 0,1,1,2,3,5,8,13…
Deficient	Sum of factors (excl. itself) < number.	8: 1+2+4 = 7 < 8
Abundant	Sum of factors (excl. itself) > number.	18: 1+2+3+6+9 = 21 > 18
Prime	Exactly two factors: 1 and itself. 1 is not prime.	3: only 1 and 3

---

2) Key sequences & lists

• Lucas between 10 and 100: 11, 18, 29, 47, 76
• Fibonacci between 10 and 100: 13, 21, 34, 55, 89
• Perfect numbers up to 1000: 6, 28, 496
• Perfect vs Deficient vs Abundant: sum(proper divisors) = / < / > number

---

3) Quotient Remainder Theorem

For integers $a$ and $b > 0$, unique $q$, $r$:

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

Example: $29 = 5 \cdot 5 + 4$ → $q=5$, $r=4$

---

4) Caesar cipher

• Mapping: A=0, B=1, …, Z=25
• Encryption: $E_n(x) = (x + n) \bmod 26$
• Decryption: $D_n(x) = (x_i - n) \bmod 26$
• Example (key 3): SCHOLARS → VFKRODUV

---

5) Handshaking Lemma

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

• Use to find total degree from edges, or to find number of vertices / check if a degree sequence is possible.
• If unknown vertices have degree $d$, solve for count; must be integer (else no such graph).

---

6) GCD & LCM

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

• GCD: Euclidean algorithm (repeated division: $a = bq + r$, then replace $a \leftarrow b$, $b \leftarrow r$ until $r=0$; GCD = last non-zero remainder).
• No common factor ⇒ GCD = 1.

---

7) MST — Kruskal

1. Step 1: Sort all edges by weight (ascending).
2. Step 2: Pick smallest edge.
3. Step 3: Add next smallest that does not form a cycle (if cycle, discard).
4. Repeat until $|V|-1$ edges. Sum weights = MST cost.

---

8) MST — Prim’s

1. Step 1: Start at given vertex; choose least cost edge from it.
2. Step 2: From current tree, choose least cost edge that joins a new vertex.
3. Repeat until all vertices included. Sum weights = MST cost.

• Prim’s and Kruskal’s give same total weight (may differ edge set).

---

9) Graph types (definitions)

Type	Definition
Bipartite	Vertices split into $V_1$, $V_2$; every edge joins $V_1$–$V_2$; no edge inside $V_1$ or $V_2$.
Complete Bipartite	Bipartite + every vertex in $V_1$ joined to every vertex in $V_2$. Edges = m·n.
Cyclic	Contains at least one cycle.
Acyclic	No cycle.
DAG	Directed graph with no directed cycles.
Planar	Can be drawn in plane with no edge crossings (except at endpoints).
Non-Planar	Cannot be drawn without edge crossings.

---

10) Searching

• Linear search: Start at index 0; compare key with each element until match (or end). Report index (0-based) or position (1-based).
• Binary search: Sorted array only. low/high; mid = (low+high)//2; if key < value go left (high = mid−1), if key > value go right (low = mid+1); repeat until match or low > high.

---

11) Sorting

• Bubble sort: Pass through array; compare adjacent pairs; swap if out of order. Repeat until no swaps. Pass count ≤ n−1.
• Merge sort: Divide into halves until single elements. Conquer: merge sorted halves (compare fronts, take smaller). Combine: final merge gives sorted array.

---

12) Relation properties (A = {1,2,3,4})

Property	Meaning
Reflexive	$\forall a\,((a,a) \in R)$
Irreflexive	$\forall a\,((a,a) \notin R)$
Symmetric	$(a,b) \in R \Rightarrow (b,a) \in R$
Asymmetric	$(a,b) \in R \Rightarrow (b,a) \notin R$ (and no $(a,a)$)
Antisymmetric	$(a,b),(b,a) \in R \Rightarrow a = b$
Transitive	$(a,b),(b,c) \in R \Rightarrow (a,c) \in R$

Quick summary:

Relation	Reflexive	Irreflexive	Symmetric	Asymmetric	Antisymmetric	Transitive
R1	✅	❌	✅	❌	❌	✅
R2	❌	✅	❌	✅	✅	❌
R3	✅	❌	❌	❌	❌	❌
R4	✅	❌	❌	❌	✅	❌
R5 A×A	✅	❌	✅	❌	❌	✅
R6	✅	❌	✅	❌	❌	✅

---

IUS Preps - Your Academic Success Partner