To calculate the table you have provided, you start with the two given polynomials in the first column, the one with higher order at the top. In this case, $P(x) = x^3 + x + 1$ goes in the first row.
So, for the case you have provided, the table looks like,
\begin{array}{c|c|c}
\text{Remainder}\ (a) & \text{Quotient}\ (q) & y\\\hline
x^3 + x + 1 && \\
x^2& & \\
\end{array}
As indicated in the document provided, the $a$ and $q$ columns are filled in using the Euclidean algorithm, i.e. by successive division: divide
the next-to-the-last $a$ by the last $a$. The quotient goes into the $q$-column, and the remainder goes into the
$a$-column.
After the $a$ and $q$ columns are filled up, the table will look like,
\begin{array}{c|c|c}
\text{Remainder}\ (a) & \text{Quotient}\ (q) & y\\\hline
x^3 + x + 1&&\\
x^2& x&\\
x + 1& x + 1&\\
1& x + 1
\end{array}
You should remember that all mathematical operations are done over
$\textit{GF}(2^3)$.
Your mistake was that when you divide $x^2$ by $x+1$, the quotient is $x+1$ and the remainder is $1$. It will be incorrect to take the quotient as $x$ and remainder as $x$. When carrying out a polynomial division, you should remember that: given two univariate polynomials $a$ and $b \not= 0$ defined over a field, there exist two polynomials $q$ (the quotient) and $r$ (the remainder) which satisfy,
$a=bq+r$
and
$\deg(r)<\deg(b)$,
where $\deg(...)$ denotes the degree. Moreover $q$ and $r$ are uniquely defined by these relations.
Quotient $x$ and remainder $x$ violates the condition, degree of remainder is strictly less than degree of divisor.
Anyway, coming back to your original problem, the only task remains is to fill up the $y$ column. The $y$-column is filled in from bottom to top. Always start with $0$ for the last $y$ and $1$ for the next-to-
the-last $y$.
Then, working from bottom to top, fill in the $y$’s using the rule,
$(\text{next}\ y) = (\text{last}\ q) \times (\text{last}\ y) + (\text{next-to-last}\ y)$.
So, with the $y$'s filled up, the table becomes,
\begin{array}{c|c|c}
\text{Remainder}\ (a) & \text{Quotient}\ (q) & y\\\hline
x^3 + x + 1&& x^2 + x + 1\\
x^2& x&x + 1\\
x + 1& x + 1&1\\
1& x + 1&0
\end{array}
Again, you should remember that all mathematical operations are done over
$\textit{GF}(2^3)$.
So, your inverse of $x^2$ is now given as the topmost $y$ value
that was computed, $x^2 + x + 1$.
Indeed, to check that $x^2 + x + 1$ is in fact the inverse of $x^2$, where we use the properties
that $x^3 \equiv x + 1 \bmod P(x)$ and $x^4 \equiv x^2 + x \bmod P(x)$:
\begin{align}
(x^2 + x + 1) \cdot x^2 &=& x^4 + x^3 + x^2\\
&\equiv& (x^2 + x) + (x + 1) + x^2 \bmod P(x)\\
&\equiv& 1 \bmod P(x)
\end{align}
Best Answer
As an alternative, build the table of the so called discrete logarithm. Let $a$ be a root of $f = x^{3} + x + 1$. Then \begin{align} &a^{0} = 1\\ &a^{1} = a\\ &a^{2} = a^{2}\\ &a^{3} = a + 1\\ &a^{4} = a^{2} + a\\ &a^{5} = a^{2} + a + 1\\ &a^{6} = a^{2} + 1\\ &a^{7} = 1\\ \end{align} So to compute the inverse of $a^{2} + a$, say, you note that $a^{2} + a = a^{4}$. Since $a^{7} = 1$, the inverse of $a^{4}$ is $a^{3} = a + 1$.
Note that in building the table you are doing Euclidean divisions in a simplified form. For instance $$ a^{5} = a^{4} a = (a^{2} + a) a = a^{3} + a^{2} = a + 1 + a^{2} $$ since $a$ is a root of $x^{3} + x + 1$, and thus $a^{3} = a + 1$.