Friday, March 18, 2011

A couple of puzzles

  • Write a program that finds the smallest element in a list.
  • Write a program that, given a predicate, finds an extremum from a list. That is, if the predicate is <, the smallest is returned, if the predicate is >, the largest is returned.
    (define (longer? a b) (> (string-length a) (string-length b)))
    Given longer? it would find the longest string in a list.
C.A.R. “Tony” Hoare proposed a selection algorithm to find the kth order statistic in a collection of elements. The obvious solution is this:
(define (list-select predicate list index)
  (list-ref (sort list predicate) index))

;; Examples:
;; Find the smallest element:
;;   (list-select < list 0)
;; Find the second longest string:
;;   (lsit-select longer? list 1)
The “obvious” solution is O(n log n), but one can do better.