Question 1:
CSC263 – Assignment 1
Cristyn Howard January 18, 2018
• After the kth iteration of the for-loop in lines 3-5 (hence referred to as ”loop 3-5”), executed without returning on line 5, we know that:
– A[1] = 2k, because:
⇤ A[1] is initialized to 0 when line 1 executes
⇤ A[1] = A[1] 2 occurs every time line 4 is executed, which happens once per loop 3-5 iteration, or k times for k iterations
– forj2Z, 2jk+1: A[j]=A[j 1]+1
⇤ on kth iteration loop 3-5 has executed with i = {2, 3, …, k + 1}
⇤ each iteration, line 5 executing without return shows that A[i] = A[i 1] + 1
⇤ line 4 increasing A[1] to A[i 1] on future iterations does not alter this equality because A[i]=A[i 1]+1!A[i]+2x=A[i 1]+1+2x 8x2Z
– (i) ) A[1:k+1]=[ 2k, 2k+1, 2k+2,…, 2k+(k 1), 2k+k]
⇤ Notation: A[a:b] denotes a segment of A containing A[a], A[b], and all elements between
them.
• Loop3-5startswithi=2andgoestoi=n, )thereareatmostn 1iterationsofloop3-5.
• From (i), we know that the input array B that does not return for all n 1 iterations looks like:
B = B[1 : n] = [ 2(n 1), 2(n 1)+1, 2(n 1)+2, …, 2(n 1)+((n 1) 1), 2(n 1)+(n 1)] (ii) )B=[ 2n+2, 2n+3, 2n+4,…, n, n+1]
• Given the original input A = [a1, a2, a3, …, an], after the kth iteration of loop 3-5, we have: (iii) A=[ 2k,a2 2(k 1),a3 2(k 2),…,ak 2,ak+1,…,an]
– jth iteration of loop 3-5 decreases elements in A[1:j] by 2 on line 4
– bykth iterationwehavehadeachj2Z, 1jk exactlyonce
• Then input A of size n that ran through all n-1 iterations of loop 3-5 without return, we know from
(ii) and (iii) with k = n 1 that:
[ 2n+2, 2n+3, 2n+4, …, n, n+1] ⌘ [ 2(n 1), a2 2((n 1) 1), a3 2((n 1) 2), …, an 1 2, an]
1
Thisgivesusa2 = 1, a3 = 2,etc. Ormoregenerally,aj =1 j 8validindicesjinA.
• So for input A of size n, the array A = [x, 1, 2, 3, …, n + 1] will run through loop 3-5 without
triggering a return on line 5 for a total of n-1 iterations.
– Note: x is an arbitrary integer. a1 is set to 0 in line 1, so the original input value of a1 is irrelevant.
• Therefore,9aninputarrayAofsizen8n2Nsuchthatloop3-5runsn 1times.
On the kth call of loop 3-5, the for-loop in line 4 executes exactly k times, with each execution occuring in constant time.
So 9 input of size n 8n 2 N where the number of constant calls is:
n 1 n
X i = (X i) n = n2 + n n = n2 + n 2n = n2 n 2 ⇥(n2)
i=1 i=1 2 2 2 So9inputXofsizen8n2Nsuchthatt(X)2⇥(n2). ) T(n)2⌦(n2)
• Loop 3-5 can run at most n-1 times on an input of size n.
On kth iteration of loop 3-5, for-loop in line 4 executes exactly k times, thus loop 4 has at most n-1 iterations on a given call.
SoforarbitraryinputXofsizen8n2N, t(X)c·(n 1)(n 1)=c(n2 2n+1)2⇥(n2).
) T(n)2O(n2) Question 2:
a) Nodes in a complete ternary tree are mapped one-to-one to the elements of an array in a top-to- bottom, left-to-right fashion.
Parent to child navigation: leftChildIndex = 3 · parentIndex 1 middleChildIndex = 3 · parentIndex rightChildIndex = 3 · parentIndex + 1
b) (1) Note: Internal nodes refers to non-leaf nodes.
Let height of complete tePrnary tree (CTT) A, hA = blog3(HeapsizeA · 2)c (proven in part 2).
Max number of leaf nodes in A= 3(hA).
2
So in array A storing CTT, internal nodes are A[i] for i = 1 to i = 3(hA+1) 1 3(hA). 2
b) (2) Assertion: Height h of complete ternary tree (CTT) = blog3(Heapsize · 2)c Proof:
– maxNodes=Max#ofnodesofCTTofheighth=Ph 3i =3h+1 1 i=0 2
– minNodes=Min#nodesofCTTofheighth=[Ph 13i]+1=3h 1 +1=3h+1 i=0 2 2
– minNodes Heapsize of array containing CTT of height h maxNodes
– Must show that 8h 2 N, h = blog3(minNodes · 2)c = blog3(maxNodes · 2)c
Child to parent navigation: parentIndex = bchildIndex+1c
3
3i = 3(hA+1) 1. i=0 2
Max # of nodes in A = hA
Then the number of non-leaf nodes in A is 3(hA+1) 1 3(hA).
2
–
First we will show the equality holds with maxNodes:
h = blog3(maxNodes · 2)c = blog3(3h+1 1 · 2)c = blog3(3h+1 1)c
2
hlog3(3h+1 1)