## Pessimal Algorithms and Simplexity Analysis

### October 25, 2013

I’ve been reading *Pessimal Algorithms and Simplexity Analysis* by Andrei Broder and Jorge Stolfi. It’s fun. They write three programs: search for an item in a sorted array, enumerate all items in a connected graph, and sort an array into ascending order; we’ll look at the sorting algorithm, but you may want to look at the others yourself. Here is their sorting algorithm:

The

slowsortalgorithm is a perfect illustration of themultiply and surrenderparadigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.To get a ﬁrmer grasp of the multiply and surrender method, let us follow the step-by-step development of the

slowsortalgorithm. We can decompose the problem of sortingnnumbers A_{l}, A_{2}, …, A_{n}in ascending order into (1) ﬁnding the maximum of those numbers, and (2) sorting the remaining ones. Subproblem (1) can be further decomposed into (1.1) ﬁnd the maximum of the ﬁrst [n/2] elements, (1.2) ﬁnd the maximum of the remaining [n/2] elements, and (1.3) ﬁnd the largest of those two maxima. Finally, subproblems (1.1) and (1.2) can be solved by sorting the speciﬁed elements and taking the last element in the result. We have thus multiplied the original problem into three slightly simpler ones (sort the ﬁrst half, sort the second half, sort all elements but one), plus some overhead processing. We continue doing this recursively until the lists have at most one element each, at which point we are forced to surrender.

I didn’t copy the code from the article; if you go look at it, beware the bug! The time complexity of the algorithm is O(*n*^{log2(n)/2}).

Your task is to write the *slowsort* program; you may also want to write the *research* and *bwfs* programs mentioned in the article. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.

Slowsort in Python.

Slowsort implementation in Racket.

Non-in-place and extracting minima instead of maxima. CoffeeScript. (Apparently there is no integer division in this language, whether flooring or another kind, but there are a number of “tricks” like x|0 to truncate an x.)

sort = (arr) ->

[arr, res] = [arr[0...arr.length], []]

while arr.length > 0

i = min(arr)

res.push(i)

k = arr.indexOf(i)

arr[k..k] = []

res

min = (arr) ->

if arr.length is 1 then arr[0]

else

a = sort(arr[0...arr.length/2|0])[0]

b = sort(arr[arr.length/2|0...arr.length])[0]

if a < b then a else b

`console.log(sort([3,1,4,1,5,9,2,6]))`

[…] find the index of a target x in a sorted array. We looked at a different algorithm that paper in a previous exercise. I’ll leave it to you to fetch the paper and enjoy the sincerity of the authors’ […]

In studying the slowsort algorithm, I realized that it is entirely to eager to move A[m] into place by swapping A[m] with A[j]. A better (i.e., worse) algorithm would swap A[m] with A[m+1], and repeat until A[m] is at the end of the list (like a bubble sort). Clearly the improved algorithm, which I call ‘slowersort’, is more pessimal.