Assignment 1 – Solutions
COMP3121/9101 22T1 Released February 15, due March 3
This document gives model solutions to the assignment problems. Note that alternative solutions may exist.
1. (20 points) You are playing a level of the latest smash-hit kung-fu video game. The level is composed of a sequence of n rooms filled with enemies. The hero must go through all n rooms in order, fighting all the enemies in each room. The level is completed when the hero exits the final room. For each room i, you know the number of times ai that the hero will die in that room.
Copyright By PowCoder代写 加微信 powcoder
Furthermore, this game has a very interesting death mechanic. The hero starts at age 20, and each time they die, their age is increased by the value of the death counter, which is the number of times that the hero has died. For example, after the first, second and third deaths, the hero’s age becomes 21, 23 and 26 respectively. Moreover, before the hero enters any room, you can reset the death counter to 0, though this ability may only be used once in the entire level.
Design an algorithm which runs in O(n) time and calculates the minimum age at which the hero can finish the level.
First sum up the number of deaths in the entire level (S = ai). Then, loop through each room, keeping track of how many deaths we have suffered so far (l), and how many deaths we still have to come (r = S − l). For each room, we consider using the reset ability in the current room; the final age of the hero would be
20+(1+2+…+l)+(1+2+…+r), which we can calculate using arithmetic series as
20+ l(l+1) + r(r+1). 22
The smallest of these n values is the minimum age at which the hero can finish the level.
This is an exhaustive search, considering all n possible uses of the reset ability, so it must be correct.
S is calculated in O(n) time. For each of n rooms, we update l and r in constant time, and calculate the final age also in constant time. Therefore the overall time complexity is O(n).
As in Method I, but in each room instead of calculating the final age directly, we consider modifying the previous value. The final age after resetting in room k was given by
20 + 12 l(l + 1) + 12 r(r + 1),
so resetting in room k + 1 gives final age
20+21l∗(l∗ +1)+12r∗(r∗ +1),
wherel∗ =l+ak andr∗ =r−ak. ThereforewecanupdateLandRvia
L∗ = 21[(ak +l)(ak +l+1)]
= 1a2k +(2l+1)ak +l(l+1)
=ak ak+l+2 +L, ∗ 1
and similarly
ak + l − r
=ak +(a1 +…+ak−1)−(ak +ak+1 +…+an) =(a1 +…+ak−1)−(ak+1 +…+an),
which is non-decreasing in k. Indeed, we need only find the first room k for which this quantity is non-negative, i.e. the smallest k such that
(a1 +…+ak−1)≥(ak+1 +…+an).
We can perform a linear search to find this k, at which point the minimum final age can be computed directly.
so the final age changes by
Since ak ≥ 0, the sign of this quantity is determined by
R=ak ak−r−2+R, ak (ak + l − r) .
Method III
As in Method II, but we claim that the optimal room is that which minimises S2 − l. This claim must be proven, using the proof below or equivalent.
The final age can be simplified as follows:
20+ l(l+1) + r(r+1) 22
= 20 + l(l + 1) + (S − l)(S − l + 1) 22
= 20 + l2 + l + (S − l)2 + (S − l) 22
=20+l2 +l+S2 −2Sl−l2 +S−l 2
=20+ 2 + 2 −Sl+l2
S S2 S 2 =20+2+4+ 2−l ,
which is minimised when S2 − l is minimised, as required. Method IV
As in Method IV, but we claim that the optimal room is that which minimises |r − l|. This claim is equivalent to that made in Method III, since
S l + r r − l 2 −l= 2 −l= 2 .
2. You are given an array A consisting of n integers, each between 1 and M inclusive. You are guaranteed that no more than k distinct values appear in the array.
You are required to identify which of the values between 1 and M appear in the array, and for each such value, how many times it appears. Design algorithms which solve this problem and run in:
(a) (5 points) worst case Θ(n + M ) time; (b) (5 points) worst case Θ(n log n) time; (c) (5 points) worst case Θ(n log k) time;
(d) (5 points) expected Θ(n) time. Solution
(a) First, we create a zero-initialised array B of size M, which will serve as a fre- quency table. Next, we iterate through array A. At index i, we record an instance of the value A[i] by incrementing B[A[i]]. Finally, we iterate through B and report the pairs (j, B[j]) where B[j] is nonzero, representing B[j] occur- rences of j in array A.
Creating array B takes Θ(M) time. Each of n entries of A is processed in con- stant time. Reporting the answer takes Θ(M) time. Therefore, this algorithm takes Θ(n + M ) overall.
(b) First, we sort A using mergesort. Now, we begin iterating through the sorted array A. When we see a new value, we report it, and begin a counter at 1, which is incremented for each subsequent occurrence of that number and reported when a new number is seen.
After sorting the array, any identical elements are consecutive, so the frequencies are correctly counted by this iterative procedure.
Mergesort takes Θ(n log n) time. Each of n entries of A is processed in constant time. Therefore, this algorithm takes Θ(n log n) overall.
(c) We create a self-balancing binary search tree of key-value pairs, where the key is a number appearing in A and the value is its frequency in A. For each index i of A, we search the BST to determine whether A[i] is an existing key. If so, we increment the corresponding value, and if not, we insert the key-value pair (A[i], 1). Once we have exhausted A, we traverse the BST using DFS (or BFS) and report each key-value pair.
In a self-balancing BST with k keys, searching and insertion each take Θ(log k) time. For each of n entries, we perform at most two such tree operations. Finally, reporting the answer takes Θ(k) time. Therefore, this algorithm takes Θ(n log k) overall, since k ≤ n.
(d) We create a hash table, where each key is a number appearing in A and the value is its frequency in A. For each index i of A, we search the hash table to determine whether A[i] is an existing key. If so, we increment the corresponding value, and if not, we insert it with value 1. Once we have exhausted A, we iterate over the hash table and report each key with its corresponding value.
In a hash table with k keys, searching and insertion each take expected Θ(1) time. For each of n entries, we perform at most two such hash table operations. Finally, reporting the answer takes Θ(k) time. Therefore, this algorithm takes expected Θ(n) overall, since k ≤ n.
3. (20 points) You are given an n by n matrix of distinct integers. A summit is an element that is larger than all its neighbours in each of the (up to) 4 directions. Design an algorithm which runs in O(nlogn) time and finds the location of any summit.
Note that integers in the corners and boundaries can be summits, and there will al- ways be at least one summit, the maximum element. However, you do not necessarily have to find this specific summit.
Firstly, note that we can always find a summit that is at least as big as any particular element. Starting at that element, keep stepping towards any neighbouring element that is larger. This process terminates when we are unable to step in any direction, so by definition we have reached a summit.
We can use this observation to develop a divide and conquer solution. First, pick the middle column, and perform a linear search to find the maximum element out of that column and the (up to) two on either side. If this maximum element is in the central column, then it must be greater than all its neighbours and we are done.
If the maximum element is in the left column, then by our first observation, we know that there must be a summit somewhere on the left of the central column – since that element is larger than everything in the central column, running our stepping strategy from the maximum will never cross from the left side over to the central column or anything to the right of it, and since we’re guaranteed to find a summit, there must be a summit on the left side.
This reasoning also applies to the right side, in which case we restrict our search to half of the matrix.
As such, we can use divide and conquer, at each stage testing the middle three columns. We terminate at subproblems with three columns or fewer, where the linear search finds a summit. After each stage, the number of columns is halved, so there are at most log2 n stages, each requiring at most 3n comparisons. Therefore the overall time complexity is O(n log n).
Note however that this is not the fastest possible algorithm. If we first test the middle
three columns and then analogously the middle three rows, we will have reduced
the search space from n-by-n to n -by- n using approximately 3n + 3n comparisons. 222
Therefore, the time complexity is given by the following recurrence:
T (n) = T n + Θ(n), 2
so by Case 3 of the Master Theorem T (n) = Θ(n).
4. (20 points) You have n poles of distinct heights spaced in a line, the ith of which is hi metres tall. You can wire together two poles i < j only if they are both taller than allpolesinbetweenthem,thatis,foreachi
• If instead r < l, increment j until:
– j exceeds n, in which case we terminate, or
– hj >r,inwhichcaseweupdatertothevaluehj andaddonetothe answer, representing the wire between poles i and j.
To prove the correctness of this algorithm, we must guarantee that it counts all wires crossing the midpoint. Such a wire must join pole i to pole j, where i ≤ ⌊n/2⌋ and j > ⌊n/2⌋ and poles i + 1 to j − 1 have height less than min(hi,hj). We need to confirm that updates to l and r happen at all such pairs (i,j) and only these pairs.
Claim: If l is not updated at index i, then there are no wires (i,j) crossing the midpoint.
Proof: This occurs when pole i is shorter than some pole k where i < k ≤ ⌊n/2⌋. This pole obstructs any wires (i,j) crossing the midpoint.
Similarly, if r is not updated at index j, then there are also no wires (i,j) crossing the midpoint.
If we say that l and r are updated at strong poles, then any wire crossing the midpoint must join two strong poles. However, not all pairs of strong poles can be connected by a wire.
Claim: If there is a wire (i,k) where hi < hk, then there are no wires (i,j) where k < j.
Proof: Pole k is taller than pole i, so it obstructs any such wires.
Therefore, when we count a wire (i,k) where pole i is taller than pole k, any other wires from pole i have already been counted. There may still be other wires to pole k, which we can find by iterating left of pole i. If we find a strong pole left of pole i, it is guaranteed to have a wire to pole k, at which point we can repeat the procedure, having counted all wires within the current range of poles. If instead there is no strong pole left of pole i, we have counted all wires so we terminate.
In the two pointers procedure, each update to i or j is processed in constant time, and they can be updated only n times in total. Therefore, the loop takes Θ(n) time in total. The recurrence is therefore
T(n) = 2T n + Θ(n), 2
so the algorithm runs in O(n log n) overall.
Note that there is also a Θ(n) time solution using sorted stacks.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com