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 (excluding itself) $< \text{number}$ .	8: $1+2+4 = 7 < 8$
Abundant	Sum of factors (excluding itself) $> \text{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

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: $\text{sum(proper divisors)} = / < / > \text{number}$

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

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

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

\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).

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 $\Rightarrow GCD = 1$ .

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

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

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 \cdot 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.

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

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

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
$R_1 = \{(1,1),(2,2),(3,3),(4,4),(2,4),(4,2)\}$	✅	❌	✅	❌	❌	✅
$R_2 = \{(1,2),(2,4),(1,4),(3,1)\}$	❌	✅	❌	✅	✅	❌
$R_3 = \{(1,1),(2,2),(3,3),(4,4),(1,3),(3,1),(2,3)\}$	✅	❌	❌	❌	❌	❌
$R_4 = \{(1,1),(2,2),(3,3),(4,4),(4,1),(1,2)\}$	✅	❌	❌	❌	✅	❌
$R_5 = A \times A$	✅	❌	✅	❌	❌	✅
$R_6 = \{(1,1),(2,2),(3,3),(4,4),(1,3),(3,1)\}$	✅	❌	✅	❌	❌	✅

IUS Preps - Your Academic Success Partner