Description
1. Given a collection of n nuts and a collection of n bolts, arranged in an
increasing order of size, give an O(n) time algorithm to check if there
is a nut and a bolt that have the same size. The sizes of the nuts and
bolts are stored in the sorted arrays NUT S[1..n] and BOLT S[1..n],
respectively. Your algorithm can stop as soon as it finds a single match
(i.e, you do not need to report all matches).
2. Let A[1..n] be an array of distinct positive integers, and let t be a
positive integer.
(a) Assuming that A is sorted, show that in O(n) time it can be
decided if A contains two distinct elements x and y such that
x + y = t.
(b) Use part (a) to show that the following problem, referred to as
the 3-Sum problem, can be solved in O(n
2
) time:
3-Sum
Given an array A[1..n] of distinct positive integers that
is not (necessarily) sorted, and a positive integer t, determine whether or not there are three distinct elements
x, y, z in A such that x + y + z = t.
3. Let A[1..n] be an array of positive integers (A is not sorted). Pinocchio
claims that there exists an O(n)-time algorithm that decides if there
are two integers in A whose sum is 1000. Is Pinocchio right, or will his
nose grow? If you say Pinocchio is right, explain how it can be done
in O(n) time; otherwise, argue why it is impossible.
4. Let A[1..n] be an array of points in the plane, where A[i] contains the
coordinates (xi
, yi) of a point pi
, for i = 1, . . . , n. Give an O(n lg n)
time algorithm that determines whether any two points in A are identical (that is, have the same x and y coordinates).
5. Textbook, page 1066, exercise 34.2-6.
6. Textbook, page 1086, exercise 34.4-5 (look for the definition of disjunctive normal form in chapter 34 of the textbook).
7. Textbook, page 1086, exercise 34.4-6.
2
