Tutorial 1 – Problems
COMP3121/9101
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.
Copyright By PowCoder代写 加微信 powcoder
(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..n] which contains all natural numbers between 1 and n−1, design an algorithm that runs in O(n) time and returns the duplicate value, using:
(a) O(n) additional space; (b) O(1) additional space.
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.
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 interval [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.
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, “ ” 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
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
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.
(b) Solvethesameproblembutwithanalgorithmwhichrunsintheexpected time of O(n2).
19. You are in a square orchard of 4n by 4n 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. Determine if f(n) = O(g(n)), f(n) = Ω(g(n)), both (i.e. f(n) = Θ(g(n))) or neither for the following pairs. Justify your answers.
f(n) (log2 n)2
g(n) log2(nlog2 n)2 + 2 log2 n
2n/100 √log n
n1.001 n(1+sin(πn/2))/2
n log2 n √n
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).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com