Software Developer

6.3-2 Why do we want the loop index $i$ in line 2 of BUILD-MAX-HEAP to decrease from $\lfloor A.length/2 \rfloor$ to 1 rather than increase from to $\lfloor A.length/2 \rfloor$? Otherwise we won't be allowed to call MAX-HEAPIFY, since it will fail the condition of having the subtrees be max-heaps. That is, if we start with 1, there is no guarantee that A[2] and A[3] are roots of max-heaps. 6.3-3 Show that there are at most $\lceil n/2^{h+1}\rceil$ nodes of height $h$ in any $n$-element heap. The height of binary heap is as following: A heap of size $n$ has at most $\lceil n/2^{h+1} \rceil$ nodes with height $h$. Key Observation : For any $n > 0$, the number of leaves of nearly complete binary tree is $\lceil n/2 \rceil$. Proof by induction Base case : Show that it's true for $h = 0$. This is the direct result from above observation. Inductive step : Suppose it's ture for $h - 1$. Let $N_h$ be the number of nodes at height $h$ in the n-node tree $T$. Consider the tre...

 6.2-2 Staring with the procedure MAX-HEAPIFY, write pseudocode for the procedure MIN-HEAPIFY(A, i), which performs the corresponding manipulation on a min-heap. How does the running time of MIN-HEAPIFY compare to that of MAX-HEAPIFY? MIN-HEAPIFY(A, i) l = LEFT(i) r = RIGHT(i) if l ≤ A.heap-size and A[l] < A[i] smallest = l else smallest = i if r ≤ A.heap-size and A[r] < A[smallest] smallest = r if smallest != i exchange A[i] with A[smallest] MIN-HEAPIFY(A, smallest) The running time is the same. Actually, the algorithm is the same with the exceptions of two comparisons and some names. 6.2-5 The code for MAX-HEAPIFY is quite efficient in terms of constant factors, except possibly for the recursive call in line 10, which might cause some compilers to produce inefficient code. Write an efficient MAX-HEAPIFY that uses an interative control construct (a loop) instead of recursion. MAX-HEAPIFY(A, i) while true l = LEFT(i) r = RIGHT(i) ...

6.1-1  What are the minimum and maximum numbers of elements in a heap of height h? At least $2^h$ and at most $2^{h+1}-1$. Can be seen because a complete binary tree of depth $h-1$ has $\Sigma_{i=0}^{h-1}2^i = 2^h -1$ elements, and the number of elements in a heap of depth is $h$ between the number for a complete binary tree of depth $h-1$ exclusive and the number in a complete binary tree of depth $h$ inclusive. 6.1-2 Show that an n-element heap has height $\lfloor lgn \rfloor$. Write $n = 2^m - 1 + k$ where $m$ is as large as possible. Then the heap consists of a complete binary tree of height $m-1$, along with $k$ additional leaves along the bottom. The height of the root is the length of the longest simple path to one of these k leaves, which must have length $m$. It is clear from the way we defined $m$ that $m=\lfloor lgn \rfloor$. 6.1-3 Show that in any subtree of a max-heap, the root of the subtree contains the largest value occurring anywhere in that subtree. If the largest...

6.1 Heaps The (binary) heap data structure is an array object. An array A that represents a heap is an object with two attributes: A. length , which (as usual) gives the number of elements in the array, and A. heap-size , which represents how many elements in the heap are stored within array A. That is, although A[1..A. length ] may contain numbers, only the elements in A[1..A. heap-size ], where 0 $\leqslant$ A. heap-size  $\leqslant$ A. length , are valid elements of the heap. The root of the tree is A[1], and given the index i of a node, we can easily compute the indices of its parent, left child, and right child:   PARENT(i) return [i/2] LEFT(i) return 2i RIGHT(i) return 2i + 1 6.2 Maintaining the heap property MAX-HEAPIFY(A, i) l = LEFT(i) r = RIGHT (i) if l <= A.heap-size and A[l] > A[i] largest = l else largest = i if r <= A.heap-size and A[r] > A[largest] largest = r if largest != i exchange A[i] with A[largest] ...

FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high) left-sum = - infty // It is INT_MIN in c in limits.h sum = 0 for i = mid downto low sum = sum + A[i] if sum > left-sum left-sum = sum max-left = i right-sum = - infty // It is INT_MIN in c in limits.h sum = 0 for j = mid + 1 to high sum = sum + A[j] if sum > right-sum right-sum = sum max-right = j return (max-left, max-right, left-sum + right-sum) FIND-MAXIMUM-SUBARRAY(A, low, high) if high == low return (low, high, A[low]) // base case: only one element else mid = (low + high)/2 (left-low, left-high, left-sum) = FIND-MAXIMUM-SUBARRAY(A, low, mid) (right-low, right-high, right-sum) = FIND-MAXIMUM-SUBARRAY(A, mid+1, high) (cross-low, cross-high, cross-sum) = FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high) if left-sum >= right-sum and left-sum >= cross-sum return (left-low, left-high, left-sum) elseif right-sum >= left-sum and righ...

$log_aM +  log_aN = log_aMN$  (1) proof:  assume: $log_aM = m, log_aN = n$  so:  $a^m = M, a^n = N \Rightarrow M \cdot N = a^m \cdot a^n = a^{m+n}$  $log_a{MN} = m + n = log_aM + log_aN$  $log_aM - log_aN = log_a\frac{M}{N}$ (2) proof: assume: $log_aM = m, log_aN = n$ so: $a^m = M, a^n = N \Rightarrow \frac{M}{N}=\frac{a^m}{a^n} = a^{m - n} \Rightarrow log_a{\frac{M}{N}} = m - n = log_aM - log_aN$ $log_aa^M = M$ (3) proof: assume: $a^M = B \Rightarrow log_aB = M$ so: $log_aa^M = M$ $a^{log_aM} = M$ (4) proof: assume: $log_aM = B$ so: $a^B = M$ $\because B = log_aM, a^B = M$ $\therefore a^B = a^{log_aM} = M$ $log_aM^N = Nlog_aM$ (5) proof: $log_aM^N = log_a(\overbrace{M \cdot M \cdots M}^{N})$ $\because log_aM +  log_aN = log_aMN$  property (1) $\therefore log_a(\overbrace{M \cdot M \cdots M}^{N}) = \overbrace{log_aM + log_aM + \cdots log_aM}^{N} = Nlog_aM$ $log_ab = \frac{log_cb}{log_ca}= \frac{lnb}{lna} = \frac{lgb}{lga}$ (6) ...

The Simple Arithmetic Sequences Let's say we have the simplest of arithmetic sequences. $\{1, 2, 3, \cdot\cdot\cdot, n\}$ And what I want to think about is what is the sum of this sequence going to be? And the sum of a sequence, we already know we call a series as following: $S_n = 1 + 2 + 3 + \cdot\cdot\cdot + n$ $S_n = n + (n-1) + (n-2) + \cdot\cdot\cdot + 1$ Now I'm going to add these two equations. $2S_n = (n+1) + (n+1) + (n+1) + \cdot\cdot\cdot + (n+1)$ So how many of these $(n+1)$ do we have? Well we have n of them there were n of these terms in each of these equations. So, we can rewrite this thing as following: $2S_n = n(n+1)$ $$ S_n = \frac{n(n+1)}{2} = n \cdot \frac{n+1}{2} = n \cdot \frac{a_n+a_1}{2} $$ $a_n$ is the nth term in our sequence, $a_1$ is the first term in our sequence. General Arithmetic Sequences Let's write an arithmetic sequence in general terms. $\{a, a+d, a+2d,\cdot\cdot\cdot, a+(n-1)d\}$ d  could be a positive or a negative number, which we cal...