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 slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, 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 firmer grasp of the multiply and surrender method, let us follow the step-by-step development of the slowsort algorithm. We can decompose the problem of sorting n numbers Al, A2, …, An in ascending order into (1) finding the maximum of those numbers, and (2) sorting the remaining ones. Subproblem (1) can be further decomposed into (1.1) find the maximum of the first [n/2] elements, (1.2) find the maximum of the remaining [n/2] elements, and (1.3) find the largest of those two maxima. Finally, subproblems (1.1) and (1.2) can be solved by sorting the specified elements and taking the last element in the result. We have thus multiplied the original problem into three slightly simpler ones (sort the first 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(nlog2(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.

About these ads

Pages: 1 2

3 Responses to “Pessimal Algorithms and Simplexity Analysis”

  1. Paul said

    Slowsort in Python.

    def slowsort(L):
        n = len(L)
        if n == 1:
            return L
        mid = n // 2
        mx = max(slowsort(L[:mid])[-1], slowsort(L[mid:])[-1])
        L.remove(mx)
        return slowsort(L) + [mx]
    
  2. Slowsort implementation in Racket.

    #lang racket
    
    (define (slow-sort! v [i 0] [j (vector-length v)])
      (cond [(<= (- j i) 1) v]
            [else
             (define k (quotient (+ j i) 2))
             (slow-sort! v i k)
             (slow-sort! v k j)
             (define max-a (vector-ref v (- k 1)))
             (define max-b (vector-ref v (- j 1)))
             (vector-set! v (- k 1) (min max-a max-b))
             (vector-set! v (- j 1) (max max-a max-b))
             (slow-sort! v i (- j 1))]))
    
  3. Jussi Piitulainen said

    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]))

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 576 other followers

%d bloggers like this: