Posted: April 11th, 2015

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.