Spring 1995
Problem Set 2 (due Thursday 95.02.02)
-
Exercise 9.3-4, page 180.
(Hint: Understand how radix sort works, then apply it here.)
-
Problem 9-2, page 184.
-
Let S be a set containing n integers, and
let x be an integer.
(a) Design an algorithm to determine whether there are two elements
of S whose sum is exactly x. The algorithm should
run in time at most O(n log n).
(b) Suppose now that the set S is given in a sorted order.
Design an algorithm to solve the same problem in time at most
O(n).
In both (a) and (b) measure the running time by counting the
number of comparisons performed, ignoring all other operations.
-
Let A be an algorithm that finds the kth largest
of n elements by a sequence of comparisons. Prove
that A collects enough information to determine which
elements are greater than the kth largest and which
elements are less than it. (In other words, you can partition the
set around the kth largest without making additional
comparisons.)
Assaf Kfoury
Created: 95.01.26