From p. 38 of Richard Hodel's An Introduction to Mathematical Logic,
"Construct an algorithm that, given an integer $a$, decides in a finite number of steps whether the equation $x^2+y^3-a=0$ has a solution in integers."
I don't see how to place any bound on $x$ or $y$ in terms of $a$, and given the nature of the text I don't think Hodel was expecting any heavy-duty number theory.
POSTSCRIPT: It seems most likely that Hodel meant "a solution in POSITIVE integers", as I don't think the author was expecting familiarity with the bound mentioned by Qiaochu.
The above equation is shown below:
$$x^2+y^3-a=0 \tag1\label1$$
Consider restricting value of $a$ to $a=(x+y)^2$ then, the solution to equation \eqref{1} above is given below:
\begin{align} x &= \frac{6k^2-7k+2}{k^2} \\ y &= \frac{-3k^2+2k}{k^2}. \end{align}