How do we represent things in computer? Images, texts, video, audio, databases…. etc.

While those formats are taken for granted, we want to take a deep dive into those

We can open up this black box once

Big Idea: Can compose representations

If you can represent objects by type T, then we can represent list/tuples of objects of type T

Keep in mind that all objects are represented as sequence of 0’s and 1’s (Idea of OOP)

Definition: Representation

E: $\theta \rarr \{0,1\}^\ast$

that is one-to-one “Encoding function”

In other words, a “representation” of an object is just to transfer from a object to a sequence of - and 1 and they are unique

Notation: if we have A, then set $A^2$ is equal to $A \times A$ = $\{(a,a) :a\in A\}$

Similarly,

Definitions are more important than Theorem Statements and proofs

Example: Represent Natural numbers:

E: $\mathbb{N} \rarr \{0,1\}^*$

Unary: E(n) = 000….000 (n+1 zeros to represent n)

Binary: E(0) = 0, E(1) = 1, E(2) = 10 …….

More formally, N to B $\mathbb{N} \rarr \{0,1\}^*$

$$ NtoB(n) = \begin{cases} 0 \quad \text{if } n=0\\ 1 \quad \text{if } n = 1\\ NtoB(\text{floor(}\frac{n}{2})) \_(n\%2)\quad otherwise

\end{cases} $$