Description
Remarks
For the questions on this assignment, if needed, you may assume that sorting n numbers can be done in time O(n lg n) (e.g., using Heap Sort). If you need to sort, you can directly apply such a sorting algorithm (without writing the pseudocode), and claim that it runs in O(n lg n) time, where n is the number of elments/numbers being sorted.
When asked to give an algorithm that meets a certain time bound, you need to give the algorithm (pseudocode/description) and analyze its running time to show that it meets the required bound; giving only the algorithm is not enough to receive full credit.
Please upload your submission as a single PDF le on D2L. If your submission consists of more than one le, convert all your les into a single PDF le and upload it.

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 N U T S[1::n] and BOLT S[1::n], respectively. Your algorithm can stop as soon as it nds a single match (i.e, you do not need to report all matches).

Let A[1::n] be an array of distinct positive integers, and let t be a positive integer.


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.



Use part (a) to show that the following problem, referred to as the 3Sum problem, can be solved in O(n^{2}) time:

3Sum
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.

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.

Let A[1::n] be an array of points in the plane, where A[i] contains the coordinates (x_{i}; y_{i}) of a point p_{i}, 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).

Textbook, page 1066, exercise 34.26.

Textbook, page 1086, exercise 34.45 (look for the de nition of disjunctive normal form in chapter 34 of the textbook).

Textbook, page 1086, exercise 34.46.
2