CS 503 Quiz 2

CS 503, Advanced Programming I

Quiz 2, 13 February 2007

One of these two algorithms is asymptotically better than the other:
A: i = 1 while i < n if a[i] < a[i - 1] swap(a[i], a[i - 1])
B: max = 0 i = 1 while i < n if a[max] < a[i] max = i swap(a[n - 1], a[max])
Give an asymptotic analysis for each algorithm that indicates the better of the two algorithms. Clearly state your assumptions, your analysis, and your conclusions.
Both algorithms do O(n) iterations; algorithm A does on swap per iteration and algorithm B does on swap after all iterations are done. It seems that a worst-case analaysis using the size of the array as input and the number of swaps as output is what is wanted. Let's see:
In terms of swaps, algorithm A reduces to
```
while i < n
  swap(a[i], a[i - 1])
```
For worst case analysis assume the if-guard is always true and the swap is always taken. Relative to swaps, the while-statement body reduces to
```
while i < n
  O(1)
```
The while guard contributes no swaps and a worst-case bound of n for the number of iterations, leading to
```
O(n)*O(1) = O(n*1) = O(n)
```
swaps. Because almost no statements contribute swaps, algorithm B collapses to
```
swap(a[n - 1], a[max])
```
which immediately reduces O(1) swaps, an asymptotic improvement over algorithm A.
The book's description of the counting sort includes a step we didn't discuss in class: the counts at indices less than i are added to the count at index i.
```
for i = n - 1 to 1
  for j = i - 1 to 0
    counts[i] += counts[j]
```
Explain what this extra step does for the counting sort.
The counts array is used to make sure the counting sort is stable; that is, to make sure that already sorted elements in the array remain sorted in the same order after the sort.
Stability is important when sorting records having identical primary keys; the order is
Explain why merge sort needs O(n) extra space to sort properly.
The two sorted segments that get merged into a single, larger sorted segment occupy the section of the array into which they will be merged. If the two segments are merged in place, it's possible data could be overwritten during the merge and lost, wrecking the sort.
A degenerate interval set S has the property that the smallest possible partition for S contains n subsets, where n is the number of intervals in S. Describe how to recognize degenerate interval sets without actually finding the partitions.
A degenerate interval set S can be recognized by a value x that appears in each interval (a, b): a ≤ x ≤ b. Because any two intervals S have x in common, they can't appear in the same partition; that is, each partition contains a single interval from S.

This page last modified on 17 February 2006.