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 Turnitln 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 justified, 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 AD] > A[j+1] Then
4. Interchange AU] and A D+11 RevisedBubbleSort( A[1, … , n], array of integers)
For i <— 1 To n-1 2. done <— true 3. For j <— 1 To n-i 4. If AD] > A[j+1] Then
5. Interchange AU] and A D+11 6. done <— false 7. If done Then Break
(a) How many comparisons does BubbleSort make on an array of size n that is already sorted from smallest to largest?