Bucket Sort Expected time

The Book skips small but important math during expansion for the square. Below step is transformed to $$ E[n_i^2] = E\Big[ {\Big( \sum_{j = 1}^n X_{ij} \Big)}^2 \Big] $$ $$ = E\Big[ {\Big( \sum_{j = 1}^n \sum_{k = 1}^n X_{ij} X_{ik} \Big)}^2 \Big] $$ expanding below by expanding summation $$ {\Big( \sum_{j = 1}^n X_{ij} \Big) }^2 $$ $$ \sum_{j = 1}^n X_{ij} . \sum_{j = 1}^n X_{ij} $$ $$ (X_{i1}+X_{i2}+X_{i3}+...+X_{in}) (X_{i1}+X_{i2}+X_{i3}+...+X_{in}) $$ multiplying above

$ X_{i1}. X_{i1}+X_{i1} . X{i2}+....+X_{i1}.X_{in} + $
$ X_{i2}. X_{i1}+X_{i2} . X{i2}+....+X_{i2}.X_{in} + $ . . . $ X_{in}. X_{i1}+X_{in} . X{i2}+....+X_{in}.X_{in} + $

we can group all elements with equal subscripts

$ X_{i1}. X_{i1}+X_{i2} . X{i2}+....+X_{in}.X_{in} + $
$ X_{i1}. X_{i2}+X_{i1} . X{i3}+....+X_{i1}.X_{in} + .... $
The first part can be written as $$ \sum_{j = 1} ^ n X_{ij} $$ The second part can be written as $$ \sum_{j = 1} ^ n \sum_{k = 1} ^ n X_{ij} X_{ik} $$ together we can write as $$ \sum_{j = 1} ^ n X_{ij} + \sum_{j = 1} ^ n \sum_{k = 1} ^ n X_{ij} X_{ik} $$

8.3-5

8.3-5 In the first card-sorting algorithm in this section, exactly how many sorting passes are needed to sort d-digit decimal numbers in the worst case? How many piles of cards would an operator need to keep track of in the worst case?

Let recall the procedure from the book. Intuitively, you might sort numbers on their most significant digit, sort each of the resulting bins recursively, and then combine the decks in order. Unfortunately, since the cards in 9 of the 10 bins must be put aside to sort each of the bins, this procedure generates many intermediate piles of cards that you would have to keep track of.

If you see from the above the algorithm will a intermediate sort like counting sort which require $\theta(n+k)$ (we need to sort n cards since k is 10 for decimal numbers(0-9) ) and each of the buckets needs to be recursively solved. In the worst case each bucket on solving will create a new bucket with n values this will happen when we have all equal values (ex: let d =3 and n =3 123,123,123). we need to solve d buckets recursively the worst case running time is $\theta(d(n+10))$. The opertaer need to keep track of nd cards. Since each bin will have n cards if you recursively solve we get a new bin with n cards and this repeats for every digit. Since there are d digits and we have n cards the no of cards is nd.

8.3-4

8.3-4 Show how to sort n integers in the range $0 to n^3 -1$ in $O(n)$ time.


Let n = 10 be the no of integers to be sorted and to represent $n^3 -1$ integers we need 3 digits (ex: 0 -999 needs three digits).Each of the three digits can be represented by 0 to n-1 numbers.

The running time for radix sort is $\theta(d(n+k))$

d = 3 and k = n (0 to n-1 digits)

we have repeat the intermediate sort 3 times for 3 digits

$\theta(3(n+n))$ = $\theta(6n)$ = $\theta(n)$

the constant is absorbed by $\theta(n)$

8.3-3

8.3-3 Use induction to prove that radix sort works. Where does your proof need the assumption that the intermediate sort is stable?

Let us assume the sorting works for 1 to d-1 digits if it works for d-1 digits it works for d digits. let $a_d$ and $b_d$ be two digits to be sorted.

If $a_d > b_d$ then the algorithm places $a_d$ ahead of $b_d$ regardless of its lower order digits.

If $a_d < b_d$ then the algorithm places a_d after $b_d$ regardless of its lower order digits.

If $a_d = b_d$ then the algorithm leaves the elements in the same order they were in because it is stable. If d digits are equal the two numbers already sorted for d-1 digits and now for d- digit. If the all the digits are equal for two numbers if the intermediate sort is not stable then for the third case it will not leave the elements in the order same as the input.

8.3-2

8.3-2 Which of the following sorting algorithms are stable: insertion sort, merge sort, heapsort, and quicksort? Give a simple scheme that makes any sorting algorithm stable. How much additional time and space does your scheme entail?
insertion sort is stable because the comparison in the inner while will move elements to right only when they greater than key. if they are equal they dont move to right.

merge sort is stable the comparison in the merge compare L and R array only check if L is less than R . If it is equal it uses the element from L array which is in order with the input.

heap sort is not stable sort because the comparison is between left and right child and picks the greatest element. ex: 5 3 3 4. element 3 is not inserted in the correct order.

quick sort is not stable because we random procedure to get balanced split which can easily pick an similar element in the beginning and make it pivot element.

Give a simple scheme that makes any sorting algorithm stable.How much additional time and space does your scheme entail?

All we need to make sure is save the inserted order in another array and use it to break the tie for similar element values. we need to store indices from 1 to n each will need log n space(since an element has to written in the form 2^x and x will be no of bits ex: 8 needs 3 bits) we pick log n based on the maximum number. All the elements need $\theta(n log n)$ space.
Additional time: the worst case occurs when all elements are same and we need compare indices for every element. But the comparison occurs in constant time.

8.3-1

8.3-1 Using Figure 8.3 as a model, illustrate the operation of RADIX-SORT on the following list of English words: COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX. first sort on the LSB and till MSB to make a valid word. In the sense don't sort only LSB but also the whole word.If you only sort the letter the final output will be an invalid word. Ex: COW SEA SEA DOG DOG COW SEA COW DOG

8.2-4

8.2-4 Describe an algorithm that, given n integers in the range 0 to k, preprocesses its input and then answers any query about how many of the n integers fall into a range $[a..b]$ in $O(1)$ time. Your algorithm should use $\theta(n + k)$ preprocessing time.
We can calculate array C as in counting sort it would take $\theta(n+k)$ to find the no of elements
If a-1 = 0
return c[b]
else
c[b] - c[a-1]
we cannot subtract c[b] and c[a] because we will loose occurrence of c[a](if their is one)