STATUS

Because I didn't get my act together and complete this assignment in time, the version posted here as of Friday's class is the assignment. I may post a couple of optional problems here later today.

Specificially, the only required problem is the ordered list problem found under Actual Assignment on this page. (SideChatter moved.)

Administrivia

This assignment is due on Tuesday 14 September. It is pretty late coming out, so it is shorter than future assignments may be. (On the other hand, there were lots of things that you were asked to do but aren't being required to turn in....). I would like to think that "on Tuesday 14 September" means by 5pm, but I will not argue with lawyers who insist that it means midnight. The goal is actually that you should complete it before coming to class on Tuesday.

Please send it to las by email with a descriptive subject line such as FOCS Assignment 1. I have previously demonstrated an ability to handle ascii, rtf, pdf, microsoft word. If you want to use a different format, please let me know so I can verify that I have something on my computer to handle it.

There are several parts to this assignment. Some were described in class. Some are new in this document. A few sections are being included here as learning aids and do not need to be turned in.

Residuals from Class

1. On 3 September, I asked you to learn enough scheme to write a factorial program. If you wrote one, you can turn it in. It's not required, but I will take a look at it if you want me to. If you didn't write one because you didn't know how, please see me or do something else to learn how. One something else to learn scheme is the scheme finger exercises, below.

2. On 7 September, I asked you to write a queue abstract data type in scheme. There were actually a few steps:

   1. Write something that counts the elements in a list, much like lisp's length function.

      • (count-elements '(1 3 5 a c 3)) should be 6 (count-elements '(a (b c) d () e f) should also be 6

   2. Write something that takes a list of numbers and returns a new list with each number incremented:

      • (increment-all '(1 3 5 8 2)) should be (2 4 6 9 3) I didn't say it explicitly, but I didn't intend for you to use map in your answer.

   3. Build a queue abstract data type including:

      • (enqueue elt queue) returns a (new) queue with elt added to the end/back/last position/poor schmo who has to wait a long time

      • (front queue) returns the lucky element that's at the head of the line

      • (dequeue queue) returns a (new) queue with the lucky element removed

   • You are welcome to turn in your queue implementation, along with count-elements and/or increment-all, but these are not required.

Actual Assignment

1. Implementing member? on a linked list ADT -- like a scheme list -- (potentially) involves checking each element in the list. However, if the list is always stored in order you can stop looking as soon as you've gone too far. (This means that only n/2 elements need be checked, on average, even when the element is not in the list, assuming that (a) n is the number of elements in the list and (b) the thing you're looking and the things in the list are drawn from the same distribution. Of course, you'd have to ask Dr. M. for details.)

   • Your assignment is to write an ordered list implementation of the collection ADT. That is, you should implement:

     • insert elt list    : elt, list -> list        ; return a (new) list with element in it, in order

     • member? elt list : elt, list -> boolean  ; return true iff elt is found in list

     • delete elt list    : elt, list -> list        ; return a (new) list without element in it

     You are encouraged but not required to write this code in scheme. In addition to your (clean, beautiful, appropriately documented) code, you should turn answer the following questions:

     • What is the running time (in terms of O or theta) of each of your three operations? Give a brief (informal is OK) justification.
     • 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?
     • Under what (if any) circumstances would you prefer the ordered list implementation over the unordered implementation? The unordered list over the ordered implementation?

Non-Assignment

This stuff made it in too late to be actual assignment, but is here for posterity. (It also indicates the kind of thing I hope you're able to do now.)

1. Write a scheme procedure double that takes one number as an argument and returns twice its argument (in the mathematical sense). For example,

   • > (double 6)
     12
     > (double 4.5)
     9

2. Write the scheme procedure substitute that takes two elements and a list and returns a new list in which any occurrences of the second element have been replaced with the first. For example:

   • > (substitute 4 'x  '(a square has x sides and x corners))
     (a square has 4 sides and 4 corners)
     > (substitute 'you 'I '(I feel like I have to sleep))
     (you feel like you have to sleep)
     > (substitute 4 'a (substitute 3 'e '(c e l e b r a t e)))
     (c 3 l 3 b r 4 t 3)

Challenge Problems

You do not need to do or even look at these problems. They're here for those who like to warp their brains....

1. Do exercises 2.4 and 2.6 from Structure and Interpretation of Computer Programs. They are also reproduced here for the curious:

• SICP 2.4 Here is an alternative procedural representation of pairs. For this representation, verify that (car (cons x y)) yields x for any objects x and y.

  • (define (cons x y)
      (lambda (m) (m x y)))
    
    (define (car z)
      (z (lambda (p q) p)))

    What is the corresponding definition of cdr?

  SICP 2.6 In case representing pairs as procedures wasn't mind-boggling enough, consider that, in a language that can manipulate procedures, we can get by without numbers (at least insofar as nonnegative integers are concerned) by implementing 0 and the operation of adding 1 as

  • (define zero (lambda (f) (lambda (x) x)))
    
    (define (add-1 n) (lambda (f) (lambda (x) (f ((n f) x)))))

    This representation is known as Church numerals, after its inventor, Alonzo Church, the logician who invented the lambda calculus.

    Define one and two directly (not in terms of zero and add-1.) (Hint: Use substitution to evaluate (add-1 zero)).

    Give a direct of the addition procedure + (not in terms of repeated application of add-1).