Posted by Staleano on August 05, 1999 at 13:18:21:
For part E i thought it would be possible to find the mode in O(N) time. I think another student mentioned in class the same technique. Assuming you know the maximum value in the array:
1. Go to each element in the list, in second array store the number
of occurrences of each element. When incrementing the number of
occurrences of a number you make sure it takes O(1) time
otherwise algorithm is O(n^2). You can do this by using the
elements value as the second arrays index value or something
similar.
2. After visiting each element use the FindMax algorithm on the
second array like in part (b) to find which value has the maximum
number of occurrences.