Algorithms Tutorial 1 Problems
1. You are given an array S of n integers and another integer x.
(a) Describe an O(nlogn) algorithm (in the sense of the worst case perfor- mance) that determines whether or not there exist two elements in S whose sum is exactly x.
(b) Describe an algorithm that accomplishes the same task, but runs in O(n) expected (i.e., average) time.
2. Given two arrays of n integers, design an algorithm that finds out in O(n log n) steps if the two arrays have an element in common. (Microsoft interview ques- tion)
3. Given an array A[1..100] which contains all natural numbers between 1 and 99, design an algorithm that runs in O(n) and returns the duplicate value. (Microsoft interview question)
4. Assume you are given two arrays A and B, each containing n distinct positive numbers and the equation x8 − x4y4 = y6 + x2y2 + 10. Design an algorithm which runs in time O(nlogn) which finds if A contains a value for x and B contains a value for y that satisfy the equation.
5. You’re given an array of n integers, and must answer a series of n queries, each of the form: “how many elements of the array have value between L and R?”, where L and R are integers. Design an O(n log n) algorithm that answers all of these queries.
6. Assume you have an array of 2n distinct integers. Find the largest and the smallest number using 3n − 2 comparisons only.
1
7. Assume that you have an array of 2n distinct integers. Find the largest and the second largest number using only 2n + n − 2 comparisons.
8. You are at a party attended by n people (not including yourself), and you suspect that there might be a celebrity present. A celebrity is someone known by everyone, but who does not know anyone else present. Your task is to work out if there is a celebrity present, and if so, which of the n people present is a celebrity. To do so, you can ask a person X if they know another person Y (where you choose X and Y when asking the question).
(a) Show that your task can always be accomplished by asking no more than 3n − 3 such questions, even in the worst case.
(b) Show that your task can always be accomplished by asking no more than 3n − ⌊log2 n⌋ − 3 such questions, even in the worst case.
9. Given n numbers x1, . . . , xn where each xi is a real number in the interval [0, 1], devise an algorithm that runs in linear time that outputs a permutation of the n numbers, say y1, . . . , yn, such that ni=2|yi − yi−1| < 2.
Hint: this is easy to do in O(n log n) time: just sort the sequence in ascending order. In this case, ni=2|yi − yi−1| = ni=2(yi − yi−1) = yn − y1 ≤ 1 − 0 = 1. Here |yi − yi−1| = yi − yi−1 because all the differences are non-negative, and all the terms in the sum except the first and the last one cancel out. To solve this problem, one might think about tweaking the BucketSort algorithm, by carefully avoiding sorting numbers in the same bucket.
10. Given n real numbers x1,...,xn where each xi is a real number in the inter- val [0, 1], devise an algorithm that runs in linear time and that will output a permutation of the n numbers, say y1, ...., yn, such that ni=2 |yi −yi−1| < 1.01.
11. LetM beann×nmatrixofdistinctintegersM(i,j),1≤i≤n,0≤j≤n. Each row and each column of the matrix is sorted in the increasing order, so that for each row i, 1 ≤ i ≤ n,
M(i,1) < M(i,2) < ... < M(i,n) and for each column j, 1 ≤ j ≤ n,
M(1,j) < M(2,j) < ... < M(n,j)
You need to determine whether M contains an integer x in O(n) time.
2
12. Suppose that you are taking care of n kids, who took their shoes off. You have to take the kids out and it is your task to make sure that each kid is wearing a pair of shoes of the right size (not necessarily their own, but one of the same size). Allyoucandoistotrytoputapairofshoesonakid,andseeifthey fit, or are too large or too small; you are NOT allowed to compare a shoe with another shoe or a foot with another foot. Describe an algorithm whose expected number of shoe trials is O(n log n) which properly fits shoes on every kid.
Hint: try “double” QuickSort; one which uses a foot as a pivot for shoes and another one which uses a shoe as a pivot for feet.
13. You are conducting an election among a class of n students. Each student casts precisely one vote by writing their name, and that of their chosen classmate on a single piece of paper. We assume that students are not allowed to vote for themselves. However, the students have forgotten to specify the order of names on each piece of paper – for instance, “Alice Bob” could mean that Alice voted for Bob, or that Bob voted for Alice!
(a) Show how you can still uniquely determine how many votes each student received.
(b) Hence, explain how you can determine which students did not receive any votes. Can you determine who these students voted for?
(c) Suppose every student received at least one vote. What is the maximum possible number of votes received by any student? Justify your answer.
(d) Using parts (b) and (c), or otherwise, design an algorithm that constructs a list of votes of the form “X voted for Y ” consistent with the pieces of paper. Specifically, each piece of paper should match up with precisely one of these votes. If multiple such lists exist, produce any. An O(n2) algorithm earns partial credit, but you should aim for an O(n) algorithm.
Hint: first, use part (c) to consider how you would solve it in the case where every student received at least one vote. Then, apply part (b).
14. There are N teams in the local cricket competition and you happen to have N friends that keenly follow it. Each friend supports some subset (possibly all, or none) of the N teams. Not being the sporty type – but wanting to fit in nonetheless – you must decide for yourself some subset of teams (possibly all, or none) to support. You don’t want to be branded a copycat, so your subset
3
must not be identical to anyone else’s. The trouble is, you don’t know which friends support which teams, so you can ask your friends some questions of the form “Does friend A support team B?” (you choose A and B before asking each question). Design an algorithm that determines a suitable subset of teams for you to support and asks as few questions as possible in doing so.
15. You are given an array A consisting of 2n − 1 integers. Design an algorithm which finds all of the n possible sums of n consecutive elements of A and which runs in time O(n). Thus, you have to find the values of all of the sums
S[1] = A[1] + A[2] + . . . + A[n − 1] + A[n]; S[2] = A[2] + A[3] + . . . + A[n] + A[n + 1];
. . .
S[n] = A[n] + A[n + 1] + . . . + A[2n − 2] + A[2n − 1],
and your algorithm should run in time O(n).
16. You are a fisherman, trying to catch fish with a net that is W meters wide. Using your advanced technology, you know that the positions of all N fish in the sea can be represented as integers on a number line. There may be more than one fish at the same location.
To catch the fish, you will cast your net at position x, and will catch all fish with positions between x and x + W , inclusive. Given N , W and an array X[1..N] denoting the positions of fish in the sea, give an O(NlogN) algorithm to find the maximum number of fish you can catch by casting your net once. For example, if N = 7,W = 3 and X = [1,11,4,10,6,7,7], then the most fish you can catch is 4: by placing your net at x = 4, you will catch one fish at position 4, one fish at position 6 and two fish at position 7.
17. Your army consists of a line of N giants, each with a certain height. You must designate precisely L ≤ N of them to be leaders. Leaders must be spaced out across the line; specifically, every pair of leaders must have at least K ≥ 0 giants standing in between them. Given N,L,K and the heights H[1..N] of the giants in the order that they stand in the line as input, find the maximum height of the shortest leader among all valid choices of L leaders. We call this the optimisation version of the problem.
For instance, suppose N = 10,L = 3,K = 2 and H = [1,10,4,2,3,7,12,8,7,2]. Then among the 10 giants, you must choose 3 leaders so that each pair of leaders has at least 2 giants standing in between them. The best choice of leaders has
4
heights 10, 7 and 7, with the shortest leader having height 7. This is the best possible for this case.
(a) In the decision version of this problem, we are given an additional integer T as input. Our task is to decide if there exists some valid choice of leaders satisfying the constraints whose shortest leader has height no less than T . Give an algorithm that solves the decision version of this problem in O(N) time.
(b) Hence, show that you can solve the optimisation version of this problem in O(N logN) time.
18. You are given an array A of n distinct integers.
(a) You have to determine if there exists a number (not necessarily in 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 log n in the worst case performance. Note that the brute force algorithm would examine all quadruples of elements in A and there are n = O(n4) such quadruples.
4
(b) Solvethesameproblembutwithanalgorithmwhichrunsintheexpected time of O(n2).
19. 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(n log n).
20. You are given 1024 apples, all of similar but different sizes and a small pan 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.
21. 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
5
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).
22. Read the review material from the class website on asymptotic notation and basic properties of logarithms, pages 38-44 and then determine 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(nlog2 n)2; √
(b) f(n) = n10; g(n) = 210 n; (c) f (n) = n1+(−1)n ; g(n) = n.
23. Read the review material from the class website on asymptotic notation and ba- sic properties of logarithms, pages 38-44 and then determine if f(n) = Ω(g(n)), f(n) = O(g(n)) or f(n) = Θ(g(n)) for the following pairs. Justify your an- swers.
f(n) (log2 n)2
n100 √
You might find the following inequality useful: if f(n),g(n),c > 0 then
f(n) < c g(n) if and only if log f(n) < log c + log g(n). Also remember that O(f(n)) does not define a linear ordering; for some f,g neither f = O(g) nor g = O(f).
24. Determine the asymptotic growth rate of the solutions to the following recur- rences. If possible, you can use the Master Theorem, if not, find another way of solving it.
(a) T(n)=2T(n/2)+n(2+sinn) (b) T(n)=2T(n/2)+√n+logn
g(n) log2(nlog2 n) + 2 log2 n
n(1+sin(πn/2))/2 √n
2n/100 √log n
n22 n1.001 n log2 n
(c) T(n)=8T(n/2)+nlogn (d) T(n)=T(n−1)+n
6
25. Assume that you are given an array A containing 2n numbers. The only oper- ation that you can perform is make a query if element A[i] is equal to element A[j], 1 ≤ i,j ≤ 2n. Your task is to determine if there is a number which appears in A at least n times using an algorithm which runs in linear time.
Warning and a Hint: a really tricky one. The reasoning resembles a little bit the reasoning used in the celebrity problem: try comparing them in pairs and first find one or at most two possible candidates and then count how many times they appear.
7