$($a$)$ Give two alternative algorithms which solve a simple problem $($both should solve the

same one$)$ and which illustrate time and space tradeoff. Give the time and space

complexity of each.

$(10$ marks$)$

$($b$)$ What is meant by saying that an algorithm can solve a problem in polynomial time?

Mention an algorithm which has polynomial running time and describe a simple

problem which is not solvable in polynomial time.

$($c$)$ Briefly explain what is meant by the following terms, mentioning any relevant

examples:

i$)$ tractable and intractable problems

ii$),P$

iii$),NP$

iv$)$ NP$-$complete

v$)$ decidability and the halting problem

$(15$ marks$)$