8.2-3

8.2-3
Suppose that we were to rewrite the for loop header in line 10 of the COUNTINGSORT as
10 for j = 1 to A.length
Show that the algorithm still works properly. Is the modified algorithm stable?
The algorithm would still work because we are changing only the order in which the element are processed (they were processed in reverse order earlier). The only thing that changes is the similar value elements are not processed in the same order as the input. So the algorithm works but the algorithm is not stable because of the above reason.

8.2-2

Prove that COUNTING-SORT is stable. COUNTING-SORT is stable because the lines 10 -12 picks the last occurrence of the same value and inserts in the last possible place. All future occurrences will be inserted in front of the last occurrence.

8.1-4

Suppose that you are given a sequence of n elements to sort. The input sequence consists of n/k subsequences, each containing k elements. The elements in a given subsequence are all smaller than the elements in the succeeding subsequence and larger than the elements in the preceding subsequence. Thus, all that is needed to sort the whole sequence of length n is to sort the k elements in each of the n/k subsequences. Show an $ \Omega(n lg k)$ lower bound on the number of comparisons needed to solve this variant of the sorting problem. (Hint: It is not rigorous to simply combine the lower bounds for the individual subsequences.)
let $h_k$ be height of the subtree tree of k elements and l be the reachable leaves $$k! \leq l \leq 2^h $$ applying log on both sides $$ log k! \leq log 2^h_k $$ $$ log k! \leq h_k $$ The above height is one sub tree we have n/k subsequences. Add n / k subsequences of log k! height. $$ n/k log k! \leq h $$ since log k can be written as k log k as per stirlings approximation or bounding it using integrals $$ n/k . k log k \leq h $$ $$ n log k \leq h $$ since h is no of comparisons as well as height as per lower bound for worst case on pg 193 $$ h = \Omega(n log k) $$

8.1-3

Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length n. What about a fraction of $1/n$ of the inputs of length n? What about a fraction $1/2^n$?
using the formula from theorem 8.1
$$n! \leq l \leq 2^h$$ $$ n!/2 \leq n! \leq l \leq 2^h$$ taking logs on both sides $$ log (n!/2) \leq log (2^h)$$ $$ log (n!) - log 2 \leq log (2^h)$$ $$ log (n!) - 1 \leq log (2^h)$$ $$ log (n!) - 1 \leq h $$ $$ log (n!) - 1 \leq log(n!) \leq h $$ $$log(n!) \leq h $$ $$log(n!) = h $$ $$ \Omega(n log(n)) = h $$ b)fraction of $1/n$ of the inputs of length n?
$$ n!/n \leq n! \leq l \leq 2^h$$ $$ n!/n \leq 2^h$$ taking logs on both sides $$ log (n!/n) \leq log 2^h$$ $$ log n! - log n \leq h$$ $$ log n! - log n \leq h$$ c.What about a fraction $1/2^n$ $$ n!/2^n \leq n! \leq l \leq 2^h$$ taking log on both sides $$ log n!/2^n \leq log 2^h $$ $$ log n!/2^n \leq h $$ $$ log n! - log 2^n \leq h $$ $$ log n! - n \leq h $$

8.1-2

Obtain asymptotically tight bounds on lg(n!) without using Stirling’s approximation. Instead, evaluate the summation $\sum_{k = 1}^n lg k$ using techniques from Section A.2.

$$lg n!$$ $$lg (n+n-1+..1)$$ $$log n + log (n-1)+...+1$$ above can be written as summation $$\sum_{k = 1}^n lg k$$ lg k is monotonically increasing function and can be bounded by integrals $$ \int_{0}^n log k \leq \sum_{k = 1}^n lg k$$ $$ [k (log k-1)+ck ]_{0}^n \leq \sum_{k = 1}^n lg k$$ $$ [n (log n-1)+cn +0 ] \leq \sum_{k = 1}^n lg k$$ $$ n log n- n + cn \leq \sum_{k = 1}^n lg k$$ $$ \leq n log n $$ $$ = n log n $$

8.1-1

What is the smallest possible depth of a leaf in a decision tree for a comparison sort?
n-1 if n is the no of elements. It happens when the input is already in sorted order. we compare element from 1 to n and tree follows the leftmost path in the decision tree.

7-6