For question (b), you are expected to use augmented data structures(based on hash table, tree). Please provide detailed explanation. Thank you!

Suppose we have an array of the gold medal winners in an Olympic sport over many years. The elements in the array start with the most recent Olympic games and are sorted going back in time. For men's 100m freestyle swimming we would have an array like this: [(2016, "Kyle Chambers", "AUS"), (2012, "Nathan Adrian", "USA"), (2008, "Alain Bernard", "FRA"), (1904, "Zoltan Halmay", "HUN"), (1896, "Alfred Hajos", "HUN") ] We are interested in finding the country with the largest number of years between their first gold medal and their most recent one (in this sport). If there is a tie for the largest number of years, then returning any one of the tied countries is fine. One small complication is that sometimes in some sports) there was a tie for gold. (See 2018 bobsled results for an example.) In that case, the input array contains both gold-medal winners listed in either order as individual array elements. (a) Give a naive O(na) algorithm for solving this problem. (b) Devise an algorithm that uses a data-structure we have learned about in class and has asympo- totically smaller expected running time. Explain that algorithm. (c) State and justify the average-case running time of your algorithm. Suppose we have an array of the gold medal winners in an Olympic sport over many years. The elements in the array start with the most recent Olympic games and are sorted going back in time. For men's 100m freestyle swimming we would have an array like this: [(2016, "Kyle Chambers", "AUS"), (2012, "Nathan Adrian", "USA"), (2008, "Alain Bernard", "FRA"), (1904, "Zoltan Halmay", "HUN"), (1896, "Alfred Hajos", "HUN") ] We are interested in finding the country with the largest number of years between their first gold medal and their most recent one (in this sport). If there is a tie for the largest number of years, then returning any one of the tied countries is fine. One small complication is that sometimes in some sports) there was a tie for gold. (See 2018 bobsled results for an example.) In that case, the input array contains both gold-medal winners listed in either order as individual array elements. (a) Give a naive O(na) algorithm for solving this problem. (b) Devise an algorithm that uses a data-structure we have learned about in class and has asympo- totically smaller expected running time. Explain that algorithm. (c) State and justify the average-case running time of your algorithm