In this assignment we review the basic algorithms and data structures.
1. You are given an array A of n distinct integers.
(a) You have to determine if there exists a number (not necessarilyin A) which can be written as a sum of squares of two distinct numbers from A in two different ways (note: m2 +n2 and n2 +m2 counts as a single way) and which runs in time n2 logn in the worst case performance. Note that the brute force algorithm would examine all quadruples of elements in A and there are O(n4) such quadruples. (10 points)
(b) Solve the same problem but with an algorithm which runs in theexpected time of O(n2). (10 points)
2. Suppose that you bought a bag of n bolts with nuts screwed on them. Your 5 year old nephew unscrewed all the nuts from the bolts and put both the nuts and the bolts back into the bag. The bolts are all of similar quite large size but are actually of many different diameters, differing only by at most a few millimetres, so the only way to see if a nut fits a bolt is to try to screw it on and determine if the nut is too small, if it fits or if it is too large. Design an algorithm for matching each bolt with a nut of a fitting size which runs in the expected time O(nlogn). (20 points)
3. You are given 1024 apples, all of similar but different sizes and a smallpan balance which can accommodate only one apple on each side. Your task is to find the heaviest and the second heaviest apple while making at most 1032 weighings. (20 points)
4. You are in an orchard which has a quadratic shape of size 4n by 4n with equally spaced trees. You purchased apples from n2 trees which also form a square, but the owner is allowing to choose such a square anywhere in the orchard. You have a map with the number of apples on each tree. Your task is to chose such a square which contains the largest total number of apples and which runs in time O(n2). Note that the brute force algorithm would run in time Θ(n4). (20 points)
1
5. Determine if f(n) = O(g(n)) or g(n) = O(f(n) or both (i.e., f(n) = Θ(g(n))) or neither of the two, for the following pairs of functions
(a) f(n) = (log2(n))2; g(n) = log2(nlog2n)2; (6 points)
10√
(b) f(n) = n10; g(n) = 2 n; (6 points)
(c) f(n) = n1+(−1)n; g(n) = n. (8 points)
2
