I am reading up 'exact test' from Wikipedia, where it says:
when the result of statistical analysis is said to be an “exact test” or an “exact p-value”, it implies that the test is defined without parametric assumptions and evaluated without using approximate algorithms.
I'm confused about what are the 'approximate' algorithms for hypothesis testing? I've never heard of any approximate/non-approximate algorithms for hypothesis testing. What are they?
As the term is typically used, for a test at level $\alpha$, exact means that the distribution for the test statistic attains significance levels that can be calculated (usually quite directly, typically via counting), but not necessarily that it is conducted at exactly level $\alpha$; e.g. it may be that the test is conducted conservatively, at the highest attainable significance level that doesn't exceed $\alpha$ (which in some cases, may be considerably lower than $\alpha$).
Often, but not always, as it says in your quote, this is irrespective of the distribution you're sampling -- but sometimes the term is applied to situations I'd regard as formally parametric.
As an example, consider a binomial test to test a population proportion. If that test is conducted using the binomial distribution to calculate available significance levels, critical values and p-values, it's considered an exact test.
This is arguably parametric, since under both null and alternative the distribution of the number of successes is binomial with fixed $n$; the null specifies the value of the binomial parameter.
It's exact in the sense that the exact type I error rate for a rejection rule is directly available. For example, at $n=17$ and $p_0=0.5$ if I use the rejection rule "reject if $X\leq 4$ or $X\geq 13$", then (if the remaining assumptions, such as independence, hold) the type I error rate is exactly $6428/2^{17} \approx 0.04904$
On the other hand, if a normal approximation to the binomial were used (as is found in many introductory statistics books), it would be an approximate test (which approaches exactness asymptotically). Similarly if it were conducted as a chi-squared goodness of fit test, it would again be an approximate test.
We can in principle still calculate the type I error rate from a given rejection rule in these 'approximate test' cases, but it won't be direct in this sense -- we'd have to convert such a calculation back to the actual binomial before we could get the actual type I error rate for the rejection rule we used.
