Due by 5 PM, Friday April 14, 2000
1. Suppose you are the Interrogator for an actual trial of the Turing Test (pp. 595-6 of the text) at some time in the future. What are three questions you would ask, and how would you use the answers to help you decide which was the computer? Assume that both entities answer all three questions.
2. Now suppose you were part of the programming team for the computer in the Turing Test. How would you guard against questions like the ones you suggested in your answer to question 1? Of course you can't know, in advance, that exactly those questions will be asked, but you might have some idea of the types of questions.
3. Finally, suppose you were the Human during an actual Turing Test. Your motivation is to persuade the Interrogator that you are the human and the other entity is the computer. Certain things you might say would clearly be foolish, because they could just as easily be said by the computer, e.g.: "I'm the human, believe me--the other thing is the machine." Thinking competitively, then, how would you respond to the three questions you posed in question 1?
4. (If you missed class on April 6, you should probably collaborate with someone who didn't.) Quicksort, which you saw in this week's lab, is a famous recursive sorting algorithm. It works by first partitioning the array into two segments separated by a pivot element. After partitioning, all elements to the left of the pivot (elements with smaller array indices) are less than or equal to the pivot, and all elements to the right are greater than or equal to it. The pivot itself is in its final place in the array. Then Quicksort calls itself on the two segments, and returns. Of course, like any recursive program, it must first of all check to see if there is nothing to do, and return immediately if this is so.
Please write a C program for the Quicksort algorithm, assuming that someone else has already written the partition function for you. The partition function will do as described above, and will return the location of the pivot element. In other words, if you write
p = partition(A, left, right);
then the segment of the array A between elements numbered
left and right (inclusive) will be partitioned and the integer variable p will be
set to the location of the pivot. Note that the pivot
is selected by the partition function; you do not have
to worry about this at all.
Here's how your program should start:
void Quicksort(int A[], int L, int R)
The variables L and R indicate the left and right boundaries
of the segment to be sorted. Your program should first
test L and R to see if there's nothing to do.
If there is something to do, your program should call
partition, and then call Quicksort twice.