Consider the following problem. Two weather stations periodically take temperature data samples. Each data point consists of a pair, (d, t) where d is the date/time of the sample and t is the temperature. The two weather stations are not necessarily synchronized, however. The collections of data are not necessarily in chronological order and may or may not contain samples on the same time(s) or the same temperature(s). The problem is to detect data anomalies in which the two stations differ in temperature.

(a) Consider the following algorithm that solves this problem.

input : Two lists of date/temperature data,

A = {(d1, t1), . . .(dn, tn)} and B = {(D1, T1), . . .(Dn, Tn)} output: All data points that differ. for i = 1, . . . n do for j = 1, . . . n do if di = Dj then if ti 6= Tj then output ((di , ti),(Dj , Tj )) end end end end Analyze this algorithm using the 5-step process and give an asymptotic characterization of the algorithm.

(b) How well would this algorithm perform in practice? Suppose our machine can process data at 1 million pairs per second. How long would it take to execute this algorithm on the following input sizes? 1. n = 100 2. n = 10, 000 3. n = 1, 000, 000 4. n = 10, 000, 000 5. n = 1, 000, 000, 000

(c) Can you do better? Design a better algorithm and give a full analysis. Indicate how fast your algorithm would run on the machine that can process 1 million pairs per second.