1
$\begingroup$

As a starting point for our course in Artificial Intelligence, we are being taught induction. We received a number of homework assignments where we have to show our inductive approach for a given problem.

An example of such a problem: "Sort an array of N numbers".

Reading through the course material and online sources I feel I have grasped the first concepts of induction. I have successfully proven some statements using induction, such as the number of steps for the Tower of Hanoi problem. However, I was able to prove it because I had some information beforehand, such as the number of steps required to move the tower in the form of a formula.

In the problems handed to us, we get a sentence like the one above and are asked: "Describe the inductive approach"

Should I select an arbitrary sorting algorithm, make my own assumptions and devise my own hypothesis and try to prove that? I just want to prove that the array is indeed sorted for any given number of N. What are some exemplary steps I could take in order to provide the inductive approach given that single sentence of "Sort an array of N elements"

$\endgroup$
  • $\begingroup$ Sorry, but if you do not have explicit task we cannot define it for you. But taking "Describe the inductive approach" - it shoud be inductive, it does not pick the algorithm or require runtime, it has to work. I do not know how the answer to your question would look like, but I can share some hint (I hope it is hint and might be helpful) if you take basic sorting algorithm which picks minimum and puts it in place than you have that element in place (sorted) so N - 1 elements left to sort. Maybe this will help? $\endgroup$ – Evil Sep 13 '16 at 0:56
2
$\begingroup$

It seems to me that your teacher wants a induction proof where the induction is on the length of the array. It seems weird that your teacher does not provide a sorting algorithm .

If the task is to sort an array, I would assume that your teacher is looking for an, as you say, arbitrary sorting algorithm and prove it with that.

But if the teacher means that you should check if an array is sorted, it is of course way simpler to show for different sizes of the array.

Either way it sounds like your teacher wants you to identify a base case and show that the induction holds (array is sorted) for $n$ given that it's sorted for an array size of $n-1$

With more details, or the full problem one might be able to draw more conclusions.

$\endgroup$
2
$\begingroup$

Most questions in AI textbooks of this style are intended to be open ended so that the student can experiment on its own with the problem. So the golden rule is do as you see fit to provide the best learning!

In particular for this problem, your approach seems appropriate.

Since most sorting algorithms fall into a divide and conquer schema, you won't have problem fitting it into an inductive schema.

For example, you could take quicksort, which is usually implemented recursively. And then prove that it indeed sorts an array of size $n$ assuming that it sorts an array of size less than $n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.