Tutorial 1 – Solutions
COMP3121/9101
Problems 3, 4, 6, 9, 11, 14, 15, 16, 17, 18 are designated as [A], meaning that their solutions are written to the standard we expect in an assignment submission. You may wish to use at least these solutions as a guide for your own submissions.
1. You are given an array S of n integers and another integer x.
Copyright By PowCoder代写 加微信 powcoder
(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.
Solution: Note that brute force does not work here, because it runs in O(n2) time.
(a) First, we sort the array – we can do this in O(n log n) in the worst case, for example, using Merge Sort. A couple of approaches from here:
• For each element a in the array, we can check if there exists an element x − a also in the array in O(log n) time using binary search. The only special case is if a = x−a (i.e. x = 2a), where we just need to check the two elements adjacent to a in the sorted array to see if another a exists. Hence, we take at most O(log n) time for each element, so this part is also O(n log n) time in the worst case, giving an O(n log n) algorithm.
• Alternatively again, you add the smallest and the largest elements of the array. If the sum exceeds x no solution can exist involving the largest element; if the sum is smaller than x then no solution can exist involving the smallest element. Thus, if this sum is not equal to x you can eliminate one element. After at most n − 1 many such steps you will either find a solution or will eliminate all elements except one, thus verifying no such elements exist.
(b) We take a similar approach as in (a), except using a hash map (hash table) to check if elements exist in the array: each insertion and lookup takes O(1) expected time.
The following approaches correspond to the approaches in (a):
• At index i, we assume the previous i − 1 elements of A are already stored in the hash map. Then we check if x − A[i] is in the hash map in expected O(1), then insert A[i] into the hash map, also in expected O(1).
• Alternatively, we hash all elements of A and then go through elements of A again, this time for each element a checking in expected O(1) timeifx−aisinthehashtable. If2a=x,wealsocheckifatleast2 copies of a appear in the corresponding slot of the hash table.
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)
Solution: We present two alternative solutions.
• Sort one of the arrays and then go through all of the elements of the other array and for each element do a binary search in the sorted array to see if this element also appears there.
• Sort both arrays and then remove elements from both arrays in the same manner as you would if you were merging the arrays (but you do not need to store the elements) and see if you ever encounter the same (smallest remaining) element in both arrays.
3. [A] 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.
(a) Create a zero-initialised array B of length n, which will serve as a frequency table. For each index i = 1..n, record an instance of the value A[i] by incrementing B[A[i]]. The duplicate will be the only value j for which B[j] = 2.
We perform O(1) work for each of n indices of A, so the time complexity is O(n).
(b) Add up all elements of A and subtract from this total the sum of all num- bers from 1 to n − 1, i.e., subtract n × (n − 1)/2. The remaining value will be the duplicate.
The sum of all elements of A is computed in O(n) time, followed by one subtraction, so this algorithm runs in O(n).
Note that this solution is also acceptable for (a).
4. [A] 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(n log n) which finds if A contains a value for x and B contains a value for y that satisfy the equation.
Solution: Let
f(x,y)=y6 +x4y4 +x2y2 +10−x8,
so the original equation is f(x,y) = 0. The crucial observation is that for a fixed value x = x0, f(x0,y) is an increasing function of y. Our algorithm is then:
(a) Sort array B using MergeSort.
(b) For each index i = 1..n of A, we fix x = A[i] and perform a binary search
• Let index m be the midpoint of the current subarray B[l..r] (initially
• If f(A[i],B[m]) = 0, we have found a solution.
• If f(A[i],B[m]) < 0, the value at the midpoint is too small, and all earlier entries of B will also be too small. Therefore, we recurse on B[(m + 1)..r].
• Conversely, if f(A[i],B[m]) > 0, the value at the midpoint is too large, and all later entries of B are also too large, so we recurse on B[l..(m − 1)].
We perform n binary searches, each taking O(log n) time for a total of O(n log n). Note that the evaluation of f(A[i],B[m]) always takes constant time.
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
(inclusively)?”, where L and R are integers. Design an O(nlogn) algorithm that answers all of these queries.
Solution: We first sort the array in O(n log n), using Merge Sort. For each query, we can binary search to find the index of the:
• First element with value no less than L; and
• First element with value strictly greater than R.
The difference between these indices is the answer to the query. Each binary search takes O(log n) so the algorithm runs in O(n log n) overall. Note that if your binary search hits L you have to see if the preceding element is smaller than L; if it is also equal to L, you have to continue the binary search (go- ing towards the smaller elements) until you find the first element equal to L. Similar observation applies if your binary search hits R.
6. [A Assume you have an array of 2n distinct integers. Find the largest and the smallest number using 3n − 2 comparisons only.
Solution: Consider first the brute force algorithm:
(a) Compare the first two elements A[1] and A[2], and set m as the smaller
of them and M as the larger.
(b) For each of the following 2n − 2 elements, compare it with both m and
M, updating either if necessary.
In the best case, we will update m at each step, making it unnecessary to ever compare against M , and resulting in a total of 2n − 1 comparisons. However, this algorithm is not acceptable because in the worst case, each of 2n − 2 elements requires two comparisons, for a total of 2(2n − 2) + 1 = 4n − 3 comparisons.
Instead, we first form n pairs and compare the two elements of each pair, putting the smaller into a new array S and the larger into a new array L. Note that the smallest of all 2n elements must be in S and the largest in L, and we have made n comparisons. We now use two linear searches for the minimum of S and the maximum of L, each taking n − 1 comparisons. In total this takes n + n − 1 + n − 1 = 3n − 2 comparisons.
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.
Solution: See the figure below.
In the figure we see a complete binary tree with 2n leaves and 2n − 1 internal nodes and of depth n (the root has depth 0). Place all the numbers at the leaves, compare each pair and “promote” the larger element (shown in red) to the next level and proceed in such a way till you reach the root of the tree, which will contain the largest element. Clearly, each internal node is a result of one comparison and there are 2n − 1 many nodes thus also the same number of comparisons so far. Now just note that the second largest element must be among the black nodes which were compared with the largest element along the way – all elements underneath them must be smaller or equal to the elements shown in black. There are n many such elements so finding the largest among them will take n − 1 comparisons by brute force. In total this is exactly 2n + n − 2 many 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.
Solution: Assume the people are numbered 1 to n.
(a) We observe that our conditions imply that there can be at most one person who is a celebrity. This is because if there were two celebrities A and B, then A would have to know B because B is a celebrity. But then A cannot be a celebrity because he knows someone else at the party. We now proceed as follows.
We pick two arbitrary people A and B. We ask A if she knows B. If she does, then A cannot be a celebrity. If she does not then B cannot be a celebrity. Thus, it takes 1 question to eliminate one person as a potential celebrity. So after n − 1 questions we arrive at a single possible candidate c who could be a celebrity.
It is possible that c isn’t a celebrity either, so we must verify that they are. To do this, we need to ask n − 1 questions of the form “does j know c?”; if the answer is always yes, c still could be a celebrity (otherwise he is not and we conclude there is no celebrity at the party); then we ask n − 1 questions of the form “does c know j?” and if the answer is always “no” we have found a celebrity, otherwise no celebrity is present. Hence, our algorithm uses n − 1 + 2(n − 1) = 3n − 3 questions, evenin the worst case. Important for the (b) part of the problem, note also that 3n − 4 questions suffice, because we can reuse the answer to at least one question which was asked during the initial search for the potential celebrity c, which was either in of the form “does X knows c” (and the answer was yes) or of the form “does c knows X” (and the answer was no, because c was the final candidate for a celebrity).
(b) We arrange n people present as leaves of a balanced full tree, i.e., a tree in which every node has either 2 or 0 children and the depth of the tree is as small as possible. To do that compute m = ⌊log2 n⌋ and construct a perfect binary three with 2m ≤ n leaves. If 2m < n add two children to each of the leftmost n−2m leaves of such a perfect binary tree. In this way you obtain 2(n−2m)+(2m −(n−2m)) = 2n−2m+1 +2m −n+2m = n leaves exactly, but each leaf now has its pair, and the depth of each leaf is ⌊log2 n⌋ or ⌊log2 n⌋ + 1. For each pair we ask if, say, the left child knows the right child and, depending on the answer as in (a) we promote the potential celebrity one level closer to the root. It will again take n − 1 questions to determine a potential celebrity, but during the verification step we can save ⌊log2 n⌋ questions (one on each level) because we can reuse answers obtained along the path that the potential celebrity traversed through the
tree. Thus, 3n − 3 − ⌊log2 n⌋ questions suffice.
Figure1: Heren=9;thus,m=⌊log2n⌋=3andweaddtwochildrenton−2m = 9−23 = 1 leaf of a perfect binary tree with 8 leaves. Thus obtained tree has 9 leaves. The potential celebrity is in red. Note that we do not have to repeat 3 questions represented by the green arrows.
9. [A] 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.
Solution: Splittheinterval[0,1)intonequalbuckets,namely[0, 1),[1, 2),...,[n−1,1). nnnn
Claim: the value xi belongs to bucket number b(xi) = ⌊n xi⌋. Proof: xi is in the bucket k if and only if
This holds if and only if i.e., if
k ≤ xi < k + 1. nn
k≤nxi
In the worst case, the sum of the width and height of the search table is reduced by one. We continue in this manner until either x is found or we reach an empty table and thus ascertain that x does not occur in the table. Since the initial sum of the height and the width of the table is 2n and at each step we make only one comparison, the algorithm takes O(n) many steps.
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.
Solution: This is done by a “double QuickSort” as follows. Pick a shoe and use it as a pivot to split the kids into three groups: those for whom the shoe was too large, those who fit the shoe and those for whom the shoe was too small. Then pick a kid for whom the shoe was a fit and let him try all the shoes, splitting them in three groups as well: shoes that are too small, shoes that fit him and the shoes which were too large for him. Continue this process with the first group of kids and first group of shoes and then also the third group of shoes with the third group of kids. If kids and shoes are picked randomly, the expected time complexity will be O(nlogn).
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).
(a) If a student’s name appears on x pieces of paper, then the student received x − 1 votes since each student voted precisely once.
(b) If a student did not receive any votes, their name only appears on precisely one piece of paper. The name of the other student is who they voted for.
(c) If every student received at least one vote, then at least n distinct pieces of paper are required to correspond to these votes. There are no more pieces of paper to be distributed, so every student received exactly one vote. Hence, each student also received a maximum of one vote.
(d) Suppose every student received at least one vote. Then, by (c), every stu- dent received exactly one vote. By considering the votes as an undirected graph (where each student is a vertex and every vote is an edge between two students), or otherwise, we can see that every student appears on pre- cisely two pieces of paper. This corresponds to a set of disjoint cycle graphs where students are vertices and pieces of paper are edges between students. Pick any student s appearing on two pieces of paper, and arbitrarily choose one of their pieces of paper as their vote. Suppose they voted for t. We are now left with a singl
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com