CS计算机代考程序代写 algorithm Computer Science CSC263H St. George Campus

Computer Science CSC263H St. George Campus
Answer to Question 1.
January 18, 2018 University of Toronto
a. T(n) is O(n2). This is because for every n 2:
Solutions for Homework Assignment #1
(i) For every input array A of size n, the outer for loop of Line 3 consists of doing at most (n 1) iterations, and each such iteration causes at most (n 1) inner iterations of the nested for loop of Line 4; so a total of at most (n 1)(n 1) < n2 inner loop iterations are executed. (ii) Each inner loop iteration, and each one of the statements in line 1, 2, 4 and 5, takes constant time (because each consists of a constant number of comparisons and additions). So it is clear that there is a constant c > 0 such that for all n 2: for every input A of size n, executing the procedure strange(A) takes at most c · n2 time.
b. T(n) is ⌦(n2). This is not obvious because the for loop of Line 3 may end “early” because of the loop exit condition in Line 5: if the condition of Line 5 is satisfied then the procedure call immediately ends. Thus, to show that T(n) is ⌦(n2), we must show that there is at least one input array A such that the procedure takes time proportional to n2 on this input, despite the loop exit condition of Line 5. We do so below.
T(n) is ⌦(n2) because for every n 2:
(i) There is an input array A of size n, namely array A[1..n] = h0, 1, 2, 3, 4, …, n + 1i, i.e., the
array A such that for all i, 1  i  n, A[i] = i+1, such that the procedure does not return in Line 5.
This is because for all i, 2  i  n: (a) just before the loop of Line 4 is executed A[i1] = (i1)+1, (b) just after the loop of Line 4 is executed A[i1] = i, and (c) since A[i] = i+1, in Line 5, we have that A[i] = A[i 1] + 1 and so the procedure does not return in Line 5.
Thus, with this specific input, each iteration of the outer for loop of Line 3 with i n/2 will in turn cause the execution of at least n/2 inner iterations of the nested for loop of Line 4.
So, for input A[1..n] = h0, 1, 2, 3, 4, …, n + 1i, there are at least n2/4 iterations of the inner for loop of Line 4.
(ii) Each inner loop iteration takes constant time.
Soitisclearthatthereisaconstantc>0suchthatforalln>1: thereissomeinputAofsizen (namely, A[1..n] = h0, 1, 2, 3, 4, …, n + 1i) such that executing the procedure strange(A) takes at least c · n2 time.
Important note: For many arrays A of size n, for example all those where A[2] 6= 1, those where A[2] = 1 but A[3] 6= 2, etc…, the execution of procedure strange(A) takes only constant time! This is because the execution stops “early”, in Line 5, on these arrays.
So to prove that the worst-case time complexity of strange() is ⌦(n2), a correct argument must explicitly describe some input array A of size n for which the execution of strange(A) does take time proportional to n2.
Note that since T(n) is both O(n2) and ⌦(n2), it is ⇥(n2).
1

Answer to Question 2.
a. A ternary (max) heap H with n elements can be represented by an array A with an associated variable A.Heapsize = n, such that the elements of H are in A[1..n]. The root of H is stored in A[1], and it contains an element with largest key. The children of A[i] (from left to right in H) are A[3i 1] (if 3i1n),A[3i](if3in)andA[3i+1](if3i+1n). Fori>1,theparentofA[i]isA[bi+1c].
b.
c.
3
1. Consider a ternary heap A with n elements. Element A[i] is an internal node of the heap if and only
if (i↵) it has at least one child. So A[i] is internal i↵ A[3i 1] is an element of the heap, i.e., i↵
3i1n. ThusA[i]isaninternalnodei↵ibn+1c. 3
2. A ternary heap A with n elements has height blog3(2n1)c. To see this, note that a complete ternary tree of height h has:
• at most 30 +31 +…+3h = 3h+11 nodes, and 2
•atleast30+31+…+3h1+1=3h+1 nodes. 2
So in a complete ternary tree, the height h and the number of nodes n are related as follows: 3h+1  n  3h+11. Thus, 3h  2n1 and 3h+1 2n+1. Hence, log (2n+1)1  h  log (2n1).
2233 Therefore h = blog3(2n 1)c = dlog3(2n + 1) 1e.
• Insert(A, key): Insert key into A.
Algorithm sketch: (This is identical to the Insert procedure for binary heaps that we saw in class.) First increment A.Heapsize by one. Then put the (element x with) key in A[A.Heapsize] (for sim- plicity, in this description we identify the element x with its key). Finally, “percolate x up”until it settles to the right place, i.e., until the parent of x is greater or equal to x. To do so, keep comparing x with its parent, and swap the two if x is greater.
• Extract Max(A): Remove a key with highest priority from A.
Algorithm sketch: (This is similar to the Extract Max procedure for binary heaps that we saw in class.) First return A[1], then store A[A.Heapsize] in A[1] (replacing the old content of A[1]) and decrement A.Heapsize by one. Let x be the element now in A[1]. To restore the max-heap property, “drip x down” until it settles to the right place, i.e., until x is greater or equal to each of its children. To do so, keep comparing x with its children, and if one of them is greater, then swap x with the greatest of its children.
• Update(A, i, key), where 1  i  A.Heapsize: Change the priority of element A[i] to key and restore the heap ordering property.
Algorithm sketch: Let x be the element in A[i].
– If Update(A,i,key): increases the (key of) x, then “percolate x up” until it settles to the right place, i.e., until the parent of x is greater or equal to x. To do so, keep comparing x with its parent, and swap the two if x is greater. This procedure is similar to Insert above.
– If Update(A,i,key) decreases the (key of) x, then “drip x down” until it settles to the right place, i.e., until x is greater or equal to each of its children. To do so, keep comparing x with its children, and if one of them is greater, then swap x with the greatest of its children. This procedure is similar to Extract Max above.
2

• Remove(A, i), where 1  i  A.Heapsize: Delete the element A[i] from the heap.
Algorithm sketch: Let x be the element in A[i]. One way to delete x is to first use the Update(A, i, key) procedure to change the key of x to “infinity” (a key greater than any other key in A). This will make x percolate up all the way to the root of the max-heap A. Then execute Extract-Max(A) to remove x.
Let h be the height of the max-heap A (recall that h = blog3(2n 1)c, where n = A.Heapsize). The worst- case time complexity the above algorithms is both O(h) and ⌦(h), because: (1) they never take more than time proportional to h, and (2) they each have at least one execution that does take time proportional to h (e.g., for Update(A, i, key), such an execution occurs when i = n, and the new key is greater than any other key in A: this execution makes the leaf x = A[n] percolate up all the way to the root of the heap). So the worst-case time complexity of the above algorithms is ⇥(h) = ⇥(blog3(2n 1)c) = ⇥(log3 n).
3