5. Sorting out complaints. A group of In students, all of whom have distinct heights, line...

Transcribed Image Text:

5. Sorting out complaints. A group of In students, all of whom have distinct heights, line up in a single-file line for a group photo. Any student who stands somewhere in front of a shorter student will conceal the shorter student, who will not appear in the picture. (The taller student need not be directly in front of the shorter one.) For this reason, each student makes one complaint to the photographer for each taller student in front of them. In this problem we are concerned with algorithms that determine the number of complaints that will be made. The input is an array A[1,..., n] of the students' heights, from the front of the line to the back. (So, A[1] is the height of the student in the very front, and A[n] is the height of the student in the very back.) The desired output is the total number of complaints. (Throughout this question, assume that two heights can be compared in constant time, independent of n.) (a) Describe briefly, clearly, and precisely (in English) a simple brute-force algorithm for this problem; do not give pseudocode. State, with brief justification, a O(.) bound on its (worst-case) running time as a function of n. You do not need to give a formal proof. Solution: (b) Suppose that both the front half and back half of the line (i.e., the two halves of the array A) happen to be sorted in ascending order, though the line as a whole may not be. Describe clearly and precisely (in English or in pseudocode, as you prefer) an O(n)-time algorithm that outputs the number of complaints in this scenario, and briefly justify its correctness and running time. Solution: (c) Give a O(n log n)-time divide-and-conquer algorithm for this complaint-counting prob- lem. Briefly and clearly describe (in English) how the algorithm works, then give clear pseudocode. Hint: Enhance the MERGESORT algorithm to both sort and count. Think about how sorting the two halves of the array affects, or doesn't affect, whether a specific student will be concealed by a particular other student. Solution: 5. Sorting out complaints. A group of In students, all of whom have distinct heights, line up in a single-file line for a group photo. Any student who stands somewhere in front of a shorter student will conceal the shorter student, who will not appear in the picture. (The taller student need not be directly in front of the shorter one.) For this reason, each student makes one complaint to the photographer for each taller student in front of them. In this problem we are concerned with algorithms that determine the number of complaints that will be made. The input is an array A[1,..., n] of the students' heights, from the front of the line to the back. (So, A[1] is the height of the student in the very front, and A[n] is the height of the student in the very back.) The desired output is the total number of complaints. (Throughout this question, assume that two heights can be compared in constant time, independent of n.) (a) Describe briefly, clearly, and precisely (in English) a simple brute-force algorithm for this problem; do not give pseudocode. State, with brief justification, a O(.) bound on its (worst-case) running time as a function of n. You do not need to give a formal proof. Solution: (b) Suppose that both the front half and back half of the line (i.e., the two halves of the array A) happen to be sorted in ascending order, though the line as a whole may not be. Describe clearly and precisely (in English or in pseudocode, as you prefer) an O(n)-time algorithm that outputs the number of complaints in this scenario, and briefly justify its correctness and running time. Solution: (c) Give a O(n log n)-time divide-and-conquer algorithm for this complaint-counting prob- lem. Briefly and clearly describe (in English) how the algorithm works, then give clear pseudocode. Hint: Enhance the MERGESORT algorithm to both sort and count. Think about how sorting the two halves of the array affects, or doesn't affect, whether a specific student will be concealed by a particular other student. Solution: