A total of N students took a standardized test and their test scores were forwarded to...

 

Transcribed Image Text:

A total of N students took a standardized test and their test scores were forwarded to us in the form of (s₁, m₁), (s2, m2),,(sn, mn) where s, is a score and m; is the num- ber of students with score si. For example, if the data is (10,3), (7.5, 5), (21, 6), then 14 students took the test and their scores are (10, 10, 10, 7.5, 7.5, 7.5, 7.5, 7.5, 21, 21, 21, 21, 21, 21). a. (2 pts.) Given (s₁, m₁), (s2, m₂),,(Sn, mn) and a positive integer k, design an algorithm based on sorting that outputs the kth lowest score. For instance, when the input is (10,3), (7.5, 5), (21, 6) and k = 3, the output should be 7.5; when k = 7, the output should be 10. What is the running time of your algorithm? b. (3 pts.) Solve the same problem this time in O(n) average time. Explain why your algorithm is correct and why its average running time is O(n). A total of N students took a standardized test and their test scores were forwarded to us in the form of (s₁, m₁), (s2, m2),,(sn, mn) where s, is a score and m; is the num- ber of students with score si. For example, if the data is (10,3), (7.5, 5), (21, 6), then 14 students took the test and their scores are (10, 10, 10, 7.5, 7.5, 7.5, 7.5, 7.5, 21, 21, 21, 21, 21, 21). a. (2 pts.) Given (s₁, m₁), (s2, m₂),,(Sn, mn) and a positive integer k, design an algorithm based on sorting that outputs the kth lowest score. For instance, when the input is (10,3), (7.5, 5), (21, 6) and k = 3, the output should be 7.5; when k = 7, the output should be 10. What is the running time of your algorithm? b. (3 pts.) Solve the same problem this time in O(n) average time. Explain why your algorithm is correct and why its average running time is O(n).

Answer rating: 100% (QA)

a Sortingbased Algorithm for kth Lowest Score def ... View the full answer