COMP3121/9101 (Tutorial 1, solutions) School of Computer Science and Engineering, UNSW Sydney List of Abbreviations and Symbols
A[1..n] An array indexed from 1 to n of n elements.
N Set of all natural numbers, i.e., {1, 2, 3, . . . }.
R Set of all real numbers.
Copyright By PowCoder代写 加微信 powcoder
Z Set of all integers, i.e., {…,−2,−1,0,1,2,…}.
To help you with what problems to try, problems marked with [K] are key questions that tests you on the core concepts, please do them first. Problems marked with [H] are harder problems that we recommend you to try after you complete all other questions (or perhaps you prefer a challenge). Good luck!!!
1 Introductory problems
2 Searching algorithms
3 Sorting algorithms
4 Complexity analysis
COMP3121/9101 (Tutorial 1, solutions) School of Computer Science and Engineering, UNSW Sydney
§1 Introductory problems
Exercise 1.1. [K] You are given an array A[1..2n − 1] of integers. Design an algorithm which finds all of the n possible sums of n consecutive elements of A 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).
Solution. Here we provide two valid approaches:
Approach 1 – Sliding window: We start by computing S[1] in O(n) by simply adding up A[1], . . . , A[n], this hence will be our initial window (denote with (1, n)).To compute the sum of a window 1 shift towards the end of the array, we only need to include the element to the right of the window (A[n + 1]) and exclude the left-most element of the window (A[1]).
…A[i−2]+A[i−1]+A[i]+A[i+1]+···+A[i+n−2]+A[i+n−1]+…
S [i−1] …A[i−2]+A[i−1]+A[i]+A[i+1]+···+A[i+n−2]+A[i+n−1]+…
By generalizing this idea via above, we can compute for each i = 2, · · · , n, S[i] = S[i−1]−A[i−1]+A[n+i−1]. As we can compute each subsequent S[i] in O(1) time each, the total of n computations gives an O(n) algorithm.
Approach 2 – Cumulative sum: We can first compute the cumulative sum array C[0..2n − 1] where C[i]=A[1]+A[2]+···+A[i]. ByrecognizingthatC[0]=0,andfori=1,…,n,C[i]=C[i−1]+A[i], by continuously updating a single variable, we can compute all entries of C in O(n) total time. Then we note that for any i = 1,…,n, we have
C[i + n − 1] = A[1] + A[2] + · · · + A[i − 1] + A[i] + · · · + A[i + n − 1]
C [i−1] S [i]
Then S[i] = C[i + n − 1] − C[i − 1] which is computable in O(1) thus all the S values can be computed in
O(n) also.
Exercise 1.2. [K] 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). 2
COMP3121/9101 (Tutorial 1, solutions) School of Computer Science and Engineering, UNSW Sydney (b) This solution requires us to acknowledge a very important fact which Gauss discovered when he was
7 years old, namely
Therefore, we simply add up all elements of A (which we denote as S), then all that remains is computing S subtracted by the sum of all numbers from 1 to n−1, i.e., S−n(n−1)/2. The remaining value will be the duplicate value.
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).
Exercise 1.3. [K] 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: A[m]2 + A[k]2 and A[k]2 + A[m]2
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) Solve the same problem but with an algorithm which runs in the expected time of O(n2).
n n(n + 1)
(a) There are n = n(n−1) pairs of distinct indices 1 ≤ k < m ≤ n. For each such pair, compute the sum
A[k]2 + A[m]2 and store it in an array of size n(n − 1)/2. Sort the array using MergeSort. Finally,
iterate over the sorted array to determine if any number appears in it at least twice (such occurrences would be consecutive).
There are O(n2) pairs of indices, so computing them and storing them in an array takes O(n2). Sorting takes O(n2 log n2), which can be simplified to O(n2 log n). The final search takes O(n2). Therefore the overall time complexity is O(n2 log n).
(b) As above, compute each sum A[k]2 +A[m]2, but instead store the sums in a hash table. Before adding a sum to the hash table, we check whether the same sum already appears there, if so, report yes.
For each of O(n2) pairs of indices, we perform expected O(1) work, so the overall time complexity is expected O(n2).
Exercise 1.4. [H] 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 (a) 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.
COMP3121/9101 (Tutorial 1, solutions) School of Computer Science and Engineering, UNSW Sydney Solution
(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 student 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 precisely 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 single choice for t’s vote. We can repeatedly follow these pieces of paper until we arrive back to s. We then repeat with another student appearing on two pieces of paper until all votes have been resolved. We can do this in O(n) altogether, for instance using a (simplified) Depth-First Search (DFS).
Now we combine this with part (b) to obtain an algorithm for the general case. We repeatedly check if a student has no votes (by counting votes) and resolve their vote. Once we reach a point where this is no longer possible, we know every student received at least one vote, and use the algorithm above.
This can be done in O(n2) by repeatedly taking O(n) to identify a student who has no votes, or more cleverly in O(n) as follows. We keep a count, for each student, how many pieces of paper they appear on and maintain a queue of students who appear on only one piece of paper. We can initially populate this queue in O(n). Then, we repeatedly process the front student of the queue by removing their vote. Note that this only changes the vote count of the person they voted for, so we simply decrease their count. If their count reaches 1, we push them onto the queue. Hence, we process each student, updating counts and the queue in O(1) so this step is O(n) as well, giving an O(n) algorithm.
Exercise 1.5. [H] 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 that the people are assigned a number from 1 to n. (a) We make the following observation.
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).
COMP3121/9101 (Tutorial 1, solutions) School of Computer Science and Engineering, UNSW Sydney Observation. There can be at most one celebrity.
Suppose that there are two celebrities, say A and B. Since A is a celebrity, B must know A since everyone knows the celebrity. But then this implies that A cannot be a celebrity since a celebrity does not know anyone. So there can only be at most one celebrity. With this observation, we proceed as follows.
Arbitrarily pick any two people, say A and B. Ask if A knows B.
• If A knows B, then we know that A cannot be a celebrity.
• If A does not know B, then we know that B cannot be a celebrity.
In either case, we can eliminate one person from our celebrity candidate list. Since there are n people, we can ask n − 1 people to find the celebrity candidate. Let this candidate be C.
We now check if C is indeed the celebrity (it could very well be the case that C is not the celebrity and as such, no celebrity exists). For each person X in the party, we ask the following question:
Does X know C?
• If X does not know C, then we conclude that C cannot be the celebrity and thus, no celebrity is
• Otherwise, C may still be the celebrity.
We finally need to check if C knows anyone in the party. Again, choosing every person X in the party, we ask the following question:
Does C know X?
• If C knows X, then we conclude that C cannot be the celebrity and thus, no celebrity is present.
• If C does not know X, we continue until we have exhausted everyone in the party.
We only conclude that C must be the only celebrity once we have concluded that C does not know anyone. In the worst case, we consume n − 1 questions to determine who the potential celebrity candidate is and then 2(n − 1) questions to verify whether C is indeed the celebrity. Thus, in the worst case, we use (n − 1) + 2(n − 1) = 3n − 3 questions in total.
(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 =nleavesexactly,buteachleafnowhas 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.
Exercise 1.6. [H] 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
COMP3121/9101 (Tutorial 1, solutions) School of Computer Science and Engineering, UNSW Sydney
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.
Solution. Suppose your friends are numbered 1 to N and the teams are also numbered 1 to N. Then, for each i, ask friend i if they support team i. If they do, we choose not to support them and if they don’t, we do support them. Clearly, this subset of teams is different to all of our friends’, and it uses N queries, which is the minimal possible for any deterministic solution (we must have some information about each friend). Note: this method is called “diagonalisation”.
Exercise 1.7. [H] You are in a square orchard of 4n by 4n equally spaced trees. You want to purchase apples from precisely n2 many of those trees, which also form a square. Fortunately, the owner is allowing you to choose such a square anywhere in the orchard and you have a map with the number of apples on each tree. Your task is to choose a square that contains the largest amount of apples and which runs in time O(n2). Note that the brute force algorithm would run in time Θ(n4).
Solution. We start by noting that there is a heavy overlap between such possible squares and we should use this fact to compute the number of apples in all of such squares in an efficient way. Consider to the figure below.
Setup: Let us visualize the orchard as a 4n × 4n discrete grid and let C(i, j) denote the cell at the coordinate (i, j). Also let A[i, j] denote the amount of apples at C[i, j].
Step 1: Now, we start by examining the first column by computing the sum α(1, 1) = nk=1 A[k, 1], (corresponding to cells C[1,1] to C[n,1] shown in blue in the top left corner of the orchard map) which takes n − 1 = O(n) additions. We then compute the number of apples α(i, 1) in all rectangles r(i, 1) consisting of cells C[i,1] to C[i+n−1,1] for all i such that 2 ≤ i ≤ 3n+1, starting from α(1,1) and using
recurrence
α(i + 1, 1) = α(i, 1) − A[i, 1] + A[i + n, 1].
We know that the recurrence is valid as the rectangle (denoted with r(i,1)) consisting of cells C[i,1] to C[i + n − 1, 1] and rectangle r(i + 1, 1) consisting of cells C[i + 1, 1] to C[i + n, 1] in the first column overlap and differ only in the first square of r(i) and the last square of r(i + 1)(this idea is similar to Question 1.1
COMP3121/9101 (Tutorial 1, solutions) School of Computer Science and Engineering, UNSW Sydney but embedded 2 dimensions). Since each recursion step involves only one addition and one subtraction,
this can all be done in O(n) steps.
Step 2: We can now apply the same procedure to each different column j, thus obtaining the number of apples α(i, j) in every rectangle consisting of cells C(i, j) to C(i + n − 1, j). As each column requires O(n) many computations, it takes O(n2) many computations in total.
Step 3: Now for 1 ≤ i ≤ 3n + 1, we compute β(i, 1) = np=1 α(i, p). This gives the total number of apples acquired in the square with corner vertices at cells C(i, 1), C(i, n), C(i + n − 1, 1) and C(i + n − 1, n) (square with vertices along a single column). For n such computations it takes O(n) additions each, thus
the total number of additions then runs in O(n2).
Step 4: So for each fixed i such that1 ≤ i ≤ 3n + 1, with the value of β(i, 1), we can now compute β(i, j)
for all 2 ≤ j ≤ 3n + 1 using recursion
β(i, j + 1) = β(i, j) − α(i, j) + α(i, j + n).
because the two adjacent squares overlap, except for the first column of the first square and the last column of the second square (overlap between red and blue square), the rest of the considered squares overlap. Each step of recursion takes only one addition and one subtraction so the whole recursion takes O(n) many steps. Thus, recursions for all 1 ≤ i ≤ 3n + 1 takes O(n2) many operations. (idea is again similar to Question 1.1 but in 2 dimensions).
Step 5: Lastly,we only require to find the largest value of β(i, j) among all 1 ≤ i, j ≤ 3n + 1, giving a complexity of O((3n)2) = O(n2) for finding the maximum.
As all required steps of the algorithm runs in a complexity of O(n2), the total complexity of the algorithm is then O(n2) as required.
COMP3121/9101 (Tutorial 1, solutions) School of Computer Science and Engineering, UNSW Sydney §2 Searching algorithms
Exercise2.1. [K]LetM beann×nmatrixofdistinctintegersM(i,j),1≤i≤n,1≤j≤n. Eachrow and each column of the matrix is sorted in the increasing order, so that for each row i, 1 ≤ i ≤ n,
and for each column j, 1 ≤ j ≤ n,
M(i,1) < M(i,2) < ... < M(i,n)
M(1,j) < M(2,j) < ... < M(n,j).
You need to determine whether M contains an integer x in O(n) time. Solution. Consider M(1,n) (i.e., top right cell).
• If M(1,n) = x, we are done.
• If M(1,n) < x, the number x is not found in the top row because M(1,1) < M(1,2) < ... <
M (1, n) < x. We can therefore ignore this row.
• If M (1, n) > x, then similarly x cannot be found in the rightmost column because all other elements
there are larger than M(1,n). Thus the last column can be ignored.
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.
Exercise 2.2. [K] You are given an array of A[1..2n] distinct integers. You are tasked to find the largest and the second largest number using only 2n + n − 2 comparisons.
Solution. Consider the figure below.
We see a complete binary tree with 2n leaves and 2n − 1 internal nodes and of depth n (the root has depth 0). We then 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 (like a sports tournament!!).
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 eq
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com