Show that any comparison-based algorithm for sorting can be modified to remove all duplicates without requiring any more comparisons to be performed. Given an undirected graph G, the problem is to...

Show that any comparison-based algorithm for sorting can be modified to remove all duplicates without requiring any more comparisons to be performed.

Given an undirected graph G, the problem is to determine whether or not G is connected. Use an adversary argument to prove that it is necessary to look at all (n²
− n)/2 potential edges in the worst case.