homework2

homework2 Before beginning this homework, please review the policies regarding group- based homework, online submission of homework, and academic integrity, all of which are available on the syllabus. Remember that your homework must be typed and submitted to TurnItIn on Ted. The questions in this assignment are marked as short or long. The short questions will be graded on the correctness of your response only and do not require proof. Answers to long questions should be fully justied, and you will be graded on the correctness of your answer as well as your ability to show that it is correct using proof techniques and logical arguments. For questions that require pseudocode, you can follow the same format as the textbook, or you can write pseudocode in your own style, as long as you specify what your notation means. For example, are you using "=" to mean assignment or to check equality? You are welcome to use any algorithm from class as a subroutine in your pseudocode. For example, if you want to sort array A using InsertionSort, you can call InsertionSort(A) instead of writing out the pseudocode for InsertionSort. 1. For this problem, refer to the two algorithms below: BubbleSort( A[1, : : : , n], array of integers) 1. For i   1 To n-1 2. For j   1 To n-i 3. If A[j] > A[j+1] Then 4. Interchange A[j] and A[j+1] RevisedBubbleSort( A[1, : : : , n], array of integers) 1. For i   1 To n-1 2. done   true 3. For j   1 To n-i 4. If A[j] > A[j+1] Then 5. Interchange A[j] and A[j+1] 6. done   false 7. If done Then Break (a) (SHORT, 2 points) How many comparisons does BubbleSort make on an array of size n that is already sorted from smallest to largest? (b) (SHORT, 2 points) How many comparisons does BubbleSort make on an array of size n sorted from largest to smallest? (c) (SHORT, 2 points) Explain the dierence between BubbleSort and RevisedBubbleSort. (d) (SHORT, 2 points) How many comparisons does RevisedBubbleSort make on an array of size n that is already sorted from smallest to largest? (e) (SHORT, 2 points) How many comparisons does RevisedBubbleSort make on an array of size n sorted from largest to smallest? 2. (LONG, 10 points total) Use a loop invariant to prove that the linear search algorithm from the lecture slides is correct, i.e., that it returns the (rst) location of the target value x in the array, or 0 if the target is not present in the array. Be sure to include all parts: (a) State the loop invariant precisely. (3 points) (b) Prove the loop invariant by induction on the number of loop iterations. (4 points) (c) Conclude from the invariant that the algorithm is correct as dened above. (3 points) 3. (LONG, 10 points) Prove the following loop invariant for BubbleSort, whose pseudocode is given in problem 1: After the ith pass, positions A[n??i+1; : : : ; n] contain the i largest elements of the input, in sorted order. 4. (a) (LONG, 6 points) Give an algorithm which, given as input an array A[1; : : : ; n] of integers, decides whether A is sorted from smallest to largest. Write pseudocode and an English description of how your algorithm works. (b) (SHORT, 2 points) What is the maximum number of comparisons your algorithm makes on an array of size n? (c) (SHORT, 2 points) What is the minimum number of comparisons your algorithm makes on an array of size n? 5. (LONG, 10 points) In this problem, your goal is to identify who among a group of people has a certain disease. You collect a blood sample from each of the people in the group, and label them 1 through n. Suppose that you know in advance that exactly one person is infected with the disease, and you must identify who that person is by performing blood tests. In a single blood test, you can specify any subset of the samples, combine a drop of blood from each of these samples, and then get a result. If any sample in the subset is infected, the test will come up positive, otherwise it will come up negative. Your goal is to nd the infected person with as few blood tests as possible. This idea of testing multiple samples at a time has been used in history at times when it was impractical or expensive to perform blood tests, for example, to nd out which soldiers inWorldWar II were carrying diseases. In those situations, the problem was even harder because there could be any number of infected people in the group. Later, we will encounter this same problem in more generality. Give an algorithm that nds the infected sample in a set of n blood sam- ples, using as few tests as you can. Write pseudocode and an English description of how your algorithm works.