Full binary tree with $L$ leaves has $2L - 1$ total nodes.

Definition of Full Binary Tree      A Binary Tree is full if and only if every node has 0 or 2 children.

Proof by Induction Inductive Hypothesis The full binary tree with $L$ leaves has $N = 2L - 1$ total nodes. Base Case We can easily think of two base cases. Note that the shape of the tree at each base case is unique (Draw by yourself).
If L = 1, then N = 1. If L = 2, then N = 3. Inductive Step We want to show that the full binary tree with $L + 1$ leaves has $2(L + 1) - 1$ total leaves $\forall n \gt 2, n \in \mathbb{N}$.

Suppose that $\exists n \gt 2, n \in \mathbb{N} $ the full binary tree with $L$ leaves has $2L - 1$ total leaves.

$T$ : the full binary tree with $L$ leaves.
$v$ : a leaf node of $T$

If we want to append a new node in $T$, two nodes must be inserted on the left and right side of some leaf node of $T$. Which implies that every node insertion increases $N$ by $2$ and $L$ by $1$.

$2L - 1 + 2 = 2(L + 1) - 1$
Hence, the inductive hypothesis is proved.
- Please mail or …

Iterative DFS on the graph with post-visit ordering.

Recently, I'm studying about SCC(Strongly Connected Component) related subjects. Kosaraju's algorithm and Tarjan's algorithm are two representative algorithm to calculate SCC of graph.

Kosaraju's algorithm requires post-visit order list of DFS.
With recursive DFS, it's straightforward. But conventional iterative DFS algorithm can't calculate post-visit order.
Since that it doesn't store any information about vertices that previously visited.
Although I've googled several hrs to find nice implementation, I failed it.

So, I implemented with additional depth stack and parent array. If you have idea for any furture simplification or optimization, please mail me! #include <iostream> #include <vector> #include <algorithm> #include <stack> using namespace std; int main() { int N; // Number of vertices int M; // Number of edges vector<vector<int>> graph; // Adjacency list of graph stack<int> dfs; /…

Basic properties of ring homomorphisms

$R,\ S$ : ring.
$\phi$ : $R \rightarrow S$ be ring homomorphism.
Let $A$ be subring of $R$ and $B$ be ideal of $S$.

1. For any $r \in R$ and any positive integer $n$, $\phi(nr) = n\phi(r)$ and $\phi(r^{n}) = (\phi(r))^{n}$

By operation-preserving property of ring homomorphism, following equations must be satisfied.
$\phi(r + \dots + r) = \phi(r) + \dots + \phi(r)$
$\phi(r \cdot r \dots r) = \phi(r) \cdot \phi(r) \dots \phi(r)$

2. $\phi(A) = \{\phi(a) \mid a \in A\}$ is subring of $S$.

Since that $A$ is subring of R, $a - b \in A$ and $ab \in A,\ \forall a,\ b \in A$.
Hence, $\phi(a - b) = \phi(a) - \phi(b) \in \phi(A)$ and $\phi(ab) = \phi(a)\phi(b) \in \phi(A),\ \forall a,\ b \in A)$.

$\therefore \text{By subring test, } \phi(A) \text{ is subring of }S.$

3. If $A$ is an ideal and $\phi$ is onto $S$, then $\phi(A)$ is an ideal.

$\phi$ is onto $S$ implies that $\phi(r) = s ,\ \exists r \in R,\ \forall s \in S$ or equivalently, $\phi(A) = S$.
$A$ is ideal of $R$ implies $ar,\ ra \in A,\ \f…

Reducibility over $Q$ implies reducibility over $Z$

$Q$ : ring of rational number (which is field)
$Z$ : ring of integer (which is integral domain, not a field)
content of polynomial : greatest common divisor of the coefficients of polynomial (must be nonzero polynomial)

Suppose $f(x) \in Z[x]$ and $f(x) = g(x)h(x)$, where $g(x),\ h(x) \in Q[x]$ and $1 \leq deg\ g(x),\ h(x) < deg\ f(x)$. Also, we can assume that $f(x)$ is primitive polynomial. Since that dividing both sides with the content of $f(x)$, say $c_{f(x)}$, derives  $$\frac{f(x)}{c_{f(x)}} = \frac{g(x)h(x)}{c_f(x)}$$

Which makes polynomial in left side primitive, but does not affect degree of $g(x)$ nor $h(x)$. Hence, $f(x)$ can be primitive in any situation.

Let $a$ be the LCM(Least Common Divisor) of the denominators of the coefficients of $g(x)$, and $b$ be the LCM of the denominators of the coefficients of $h(x)$.
Then, $abf(x) = ag(x) \cdot bh(x)\ (ag(x),\ bh(x) \in Z[x])$.

Let $c_{1}$ be the content of $ag(x)$, and $c_{2}$ be the content of $bh(x)$.
Then, we can writ…

Reducibility test for degrees 2 and 3

$F$ : field

Reducibility test for degrees 2 and 3 is as follows,

$$f(x) \in F[x] \text{ and } deg\ f(x) = 2\text{ or }3$$$$ \implies $$$$f(x)\text{ is reducible over }F\text{ iff }f(x)\text{ has a zero in }F$$

Suppose that $f(x) = g(x)h(x)$, where $g(x),\ h(x) \in F[x]$. Since that, polynomials of zero degree are the only unit over integral domain, forms containing zero polynomial are not our concern. Hence, $1 \leq g(x),\  h(x) < deg\ f(x)$

Since, in integral domain, deg $f(x) = deg\ g(x) + deg\ h(x)$ and $deg\ f(x)$ is $2$ or $3$, at least one of g(x) and h(x) has degree 1. Say $g(x) = ax + b$. Then, clearly, $-a^{-1}b$ is a zero of $g(x)$ and therefore a zero of $f(x)$.

Conversely, suppose that $f(a) = 0, a \in F$. Then by the Factor Theorem, we know that $x - a$ is a factor of $f(x)$ and, therefore $f(x)$ is reducible over $F$.

고등학생의 아우성

로그의 미적분 가지고 힘들어 할 정도면 문과인가보다.
 “로그, 로그!”
Reference [1] 곱셈을 덧셈으로 바꿔 천문학적 숫자 계산 손쉽게

On the form of ring homomorphism from $Z_{n}$ to itself.

$\phi$ : $Z_{n} \rightarrow Z_{n}$, $x \mapsto ax$, where $a^{2} = a$ is ring homomorphism.

Let $\phi(1) = a$.
Then $a = \phi(1) = \phi(1)\phi(1) = a^{2}$.

Let $x \in Z_{n}$.
Then $\phi(x) = \phi(1 + \dots + 1) = \phi(1)x = ax$.

Hence, our original conjecture is true.