*-*-Fundamental-*-*

* THIS FILE CONTAINS SELECTED SOLUTIONS TO PROBLEMS ASSIGNED IN CS30b*

* *

*The notation sometimes uses LaTeX-like notation, e.g. x_i for x sub i;*

* x^i for x super i; \SUM for summation sign; \PROD for product sign; etc.*

* *

**Selection Sort:**Done in the stated way, best case is THETA(n^2) because of the

necessity of finding min n times. Worst case is also THETA(n^2), so average case,

too, is THETA(n^2)

**Exercise 1.3-6:**The number of comparisons can be reduced, but the number of

assignments (data moves) remains OMEGA(n^2)

**Problem 1-3d:**This problem asks you to modify mergesort so as to count number

of inversions in permutations. The answer given in class was glib and incorrect.

Here's a better one:

Imagine writing the original permuted data above its final locations, and connecting

each original element to its destination with a line, either slanting left, if the element

ends up earlier than it was; or vertical,if it ends up at the same place; or slanting right

if it ends up later.

Pictorially, an inversion is represented by two lines crossing. The total number of

crossings is the number of inversions.

Now the same description can be used during mergesort, where elements do their

crossings in lg(n) rounds, rather than all at once. The count will still be correct,

because elements always move TOWARDS their destinations during mergesort.

In each recursive call to mergesort, an element starts out in one half of a subarray,

called either L or R, and ends up in either L or R.

These observations make it possible to do the count:

- Elements in L never cross one another, ditto for R. (Because L and R are already

sorted.

- Through the lg(n) rounds elements progress only in the direction they're destined

for. Therefore we can sum up the crossings through the rounds.

- A crossing takes place only when an R element becomes an L element, and the

number of L elements it crosses is exactly mid - l_index + 1. So these numbers are

what we must sum. (By symmetry, we could also discuss L elements crossing R

elements.)

So

`Merge'(A, lo, mid, hi)`

...while l_ptr and r_ptr in bounds

......do if A[l_ptr] <= A[r_ptr]

............B[k] <- A[l_ptr]; l_ptr <- l_ptr + 1; k <- k+1;

.........else B[k <- A[r_ptr]; r_ptr <- r_ptr + 1; k <- k+1;

............inversions <- inversions + mid - l_ptr + 1;

....../* number of L elements crossed */

etc.

In writing Merge, a number of people indexed R (the right subarray) with A[mid + i + j].

But this index increases whether L is copied or R is copied, so it will never finish an

input like [1,3,2,4].

Also, any scheme where "inversions" is incremented by 1 each time is bound to run in

worst-case OMEGA(n^2), so it can't work.

- Elements in L never cross one another, ditto for R. (Because L and R are already