Tirgul 10.


119 views
Uploaded on:
Category: General / Misc
Description
Tirgul 10. Understanding parts of the initial two hypothetical activities: T1 Q.1(a,b) T1 Q.4(a,e) T2 Q.2(a) T2 Q.3(b) T2 Q.4(a,b). T1 Q.1(a) - pseudo-code for determination sort. Determination Sort(array A) for j = 0 to A.length - 1 k = smallest(A, j) swap(A, j, k)/swaps A[j] with A[k]
Transcripts
Slide 1

Tirgul 10 Solving parts of the initial two hypothetical activities: T1 Q.1(a,b) T1 Q.4(a,e) T2 Q.2(a) T2 Q.3(b) T2 Q.4(a,b)

Slide 2

T1 Q.1(a) - pseudo-code for determination sort Selection-Sort(array A) for j = 0 to A.length - 1 k = smallest(A, j) swap(A, j, k)/swaps A[j] with A[k] return;/Returns the list of the littlest component of A[j..n] int smallest(array An, int j) smallest = j for i = j+1 to A.length - 1 if A[i] < A[smallest] littlest = i return(smallest)

Slide 3

T1 Q.1(b) - evidence of accuracy The circle invariant: instigation in addition to “termination claim”. Incitement Claim: After performing the j’th cycle, A[0..j-1] contains the j littlest components in A, sorted in a non-diminishing request: For j = 1 : The calculation finds the littlest component and spots it in A[0] The actuation step : Suppose A[0..j-1] are the j littlest components. We locate the littlest component in A[j..N-1], and accordingly after the swap A[0..j] are the j+1 littlest components. Since A[j] is bigger than all components in A[0..j-1] by supposition, then A[0..j] is still sorted. End: After n cycles, A[0..n-1] (the whole cluster) is sorted.

Slide 4

T1 Q.4(a) - fathoming repeats We might want to demonstrate a coordinating lower bound:

Slide 5

T1 Q.4(e) - tackling repeats

Slide 6

T1 Q.4(e) (another point of view) How could we have been able to we figure that T(n) = O(n) ?? Restricted is to take a gander at the recursion tree: for any hub with work x, the work of every one of its kids is (7/8)x. So the aggregate work of some level is 7/8 times the aggregate work of one level higher, and the first level has work n. So we get an upper bound to the aggregate sum of work:

Slide 7

T2 Q.2(a) - actualize line utilizing two stacks Denote the two stacks “L” and “R”. Enqueue : push the thing to stack L. Dequeue: If stack R is unfilled : while stack L is not vacant, pop a component from stack L and push it to stack R. At the point when stack L is discharged, pop a component from stack R and return it. On the off chance that stack R is not void : pop a component from stack R and return it. Clarification : 1) If stack R is unfilled, then in the wake of moving the components from L to R they are in a FIFO request. 2) the length of stack R is not void, the top component is the first component entered the d.s. (extra enqueus does not change this), so it ought to be dequeued.

Slide 8

T2 Q.2(a) (proceeded with) What is the running time? “Most” operations take O(1), every so often we have O(n) when stack R is vacant and we need a dequeue. On the off chance that we do amortized investigation (the bookkeeping technique) it is sufficient to pay 3 for each enqueue and 1 for each dequeue, since, subsequent to being pushed to stack L, every component needs to pay precisely 2 more before being dequeued - 1 for being popped from L and 1 for being pushed to R. Notice the run-time contrast regarding the more straightforward arrangement - dependably keep the components in L, and for a dequeue, move the components to R, give back its top, and move the components back to L. Here, all dequeues are O(n).

Slide 9

T2 Q.3(b) - the determination issue The choice issue: Given a cluster A, discover the k’th littlest component in straight time (by and large). Update from Quicksort: the procdure partition(A,p,r) first picks a turn component x from A[p..r], and afterward adjusts A[p..r] so that all components before x are littler than x and all components after x are bigger than x. It gives back the new record of x (called q). RandomizedPartition(A,p,r) picks the turn arbitrarily. This dependably takes O(n) time. What is the measure of A[p..q-1] (overall)? In the event that we picked the i’th littlest component then the size will be i-1. Since each component is picked with likelihood 1/n then every size 0,..,n-1 has likelihood 1/n.

Slide 10

T2 Q.3(b) - the calculation/Returns the k’th component in A[p..r] Select(A, p, r, k) q = RandomizedPartition(A, p, r) if (k == q-p+1) return A[k] else if (k < q-p+1) return Select(A, p, q-1, k) else return Select(A, q+1, r, k-(q-p+1))

Slide 11

T2 Q.3(b) - Average run time Suppose that the extent of A[p..q-1] is i, and k causes us to enter the bigger piece of A. Since the likelihood of i is 1/n for i=0..n-1 and the parcel takes about n operations: Assume by affectation that T(n) < cn , so (utilizing the math entirety recipe):

Slide 12

T2 Q.4 - check the load property of a given (pointer based) complete double tree A recursive code: boolean isHeap(Node t) if (t == invalid) then return TRUE boolean l = isHeap(t.leftChild()) boolean r = isHeap(t.rightChild()) return ( l && r && checkNode(t) ) boolean checkNode(Node t) if ( t.leftChild().val() > t.val() ) return FALSE if ( t.rightChild().val() > t.val() ) return FALSE return TRUE

Slide 13

T2 Q.4 (proceeded with) An iterative code (utilizing a stack): boolean isHeap(Node t) Stack s s.push(t) While ( ! s.empty() ) t = s.pop() if (t != invalid) if ( ! checkNode(t) ) return FALSE s.push(t.leftChild()) s.push(t.rightChild()) ret