Contents

## Code

This is hardly the only solution.

• ```;; insert takes a number and a list of numbers
;; and returns a new list with the number argument inserted in order
(define insert
(lambda (elt lst)             ;; unsugared form of define
(cond ((null? lst) (list elt))     ;; don't forget null test!  (cons elt '())
((> elt (car lst)) (cons elt lst))   ;; if elt is smaller than car, insert it
(else (cons (car lst) (insert elt (cdr lst)))))))  ;; else keep going

;; delete takes a number and a list of numbers
;; and returns a new list with the number argument deleted
(define delete
(lambda (elt lst)
(cond ((null? lst) lst)  ;; don't forget null test!
((> elt (car lst)) lst)   ;; check if we've gone too far (to improve runtime)
((= elt (car lst)) (cdr lst))   ;; get rid of elt if we find it
(else (cons (car lst) (delete elt (cdr lst)))))))   ;; else keep going

;; Note the use of = rather than eq?  (equal? would be OK too, but = is really
;; right if you're using >.  Note also that we use the same short circuit if we've
;; gone too far.
;; Two variants (among many):

(define delete
(lambda (elt lst)
(cond ((or (null? lst) (> elt (car lst))) lst)  ;; fold null and > cases
((= elt (car lst)) (delete elt (cdr lst)))  ;; keep going in case repeated!
(else (cons (car lst) (delete elt (cdr lst)))))))

;; member? takes a number and a list of numbers and returns a boolean; true if the
;; number argument is a member of the list, false otherwise.

(define member?
(lambda (elt lst)
(cond ((null? lst) #f)      ;; empty list has no members
((> elt (car lst)) #f)    ;; went too far; it's not there (short circuit)
((= elt (car lst)) #t)    ;; found it!
(else (member? elt (cdr lst))))))   ;; keep looking```

## Analysis

• What is the running time (in terms of O or Theta) of each of your three operations? Give a brief (informal is OK) justification.

The running time of each of these algorithms is O(n) and also Theta(n), i.e., n is a bound above and a tight bound. This is because each algorithm has to cdr down the list until the element is found. (Insert and delete also cons back up an answer, but this is also proportional to n.) In both the worst case -- needing to cdr all the way to the end of the list -- and the average case, in which we only expect to go halfway -- the running time is proportional to the length of the list. (The best case is actually O(1).)

Said a different way, if I double the length of the list, I'd expect the running time of each algorithm to double.

• What (if any) benefits do you get from keeping the list in order (vs. a simple unordered list implementation)? What (if any) costs do you incur?

The major benefit of keeping the list in order, from the perspective of the collection ADT, is that member? and delete are expected to take only half as long in the case that the element is absent. (That is, we've cut the constant factor in half.) This is because you can tell when you've gone too far in an ordered list but must keep searching to the end in an unordered list. There's actually no benefit (expected) in the case where the element is present as in both an ordered and an unordered list you'd expect to find the element halfway, on average.

A second benefit is that an ordered list is already sorted. Although sorting isn't a part of the collection ADT, it's a nice benefit to have. Since sorting is O(n log n) (for the better algorithms), this could make a difference (see below).

The major cost of keeping the list in order is that insertion goes from an O(1) operation -- cons -- to an O(n) operation.

• Under what (if any) circumstances would you prefer the ordered list implementation over the unordered implementation? The unordered list over the ordered implementation?

Times I'd prefer the ordered list implementation:

• If the data are relatively static, i.e., insertion doesn't happen a lot but member (or delete) is frequent. This is because insertion is more expensive than in the unordered case, but member/delete are faster. Assuming that member is equally likely to look for something that's there or that's not, it takes 2-4 member? queries just to cancel out the cost of one insert.
• If I know that I'm going to want the data sorted. I can pay for log n insertions by avoiding one sort.

Times I'd prefer the unordered list implementation:

• If the data are dynamic (lots of inserts and deletes), especially if I know that the deletes are mostly going to be of elements actually in the list. In this case, only member? queries pay for the cost of insertion.

The truth is that there are other collection implementations (like Hashtables or Binary Trees) that are more efficient for many profiles.

2013-07-17 10:43