assignment3

COM1340 - Winter 2003
Assignment 3
Due: February 19, 2003

Set DrScheme to use the PLT | Graphical language level.

For each exercise, provide a procedure definition and at least four tests (different from the provided examples) that use eq? or equal?, as appropriate, to compare expected results with the actual results of applying your procedure.
Print out your work. On your printout, legibly write your name and ``COM1340 -- Assignment 3.''

1.) Write a Scheme function min-string that takes a possibly-nested nonempty list whose ``leaf'' elements are all strings and returns the lexicographically least such string. Use the Scheme predicate string<? to compare strings. For example:

 (min-string '("aardvark" "zoologist")) => "aardvark"
 (min-string '(("xylophone" "syzygy") "bilious" "queueing")) => 
    "bilious"
 (min-string '((((("caterwaul")))) "spoonerism" "cubit")) => 
    "caterwaul"

You may not use flatten in your implementation.

2.) A Fibonacci list is either:

the empty list (a Fibonacci list of order 0), or
the list '(fib) (a Fibonacci list of order 1), or
for , a Fibonacci list of order is a nonempty list whose car is a Fibonacci list of order , and whose cdr is a Fibonacci list of order .

Write a Scheme predicate fib-list? that takes a list lst and a number n, and returns #t if lst is a Fibonacci list of order n, and #f otherwise. Examples:

 (fib-list? null 0) => #t 
 (fib-list? null 2) => #f
 (fib-list? '(fib) 1) => #t
 (fib-list? '(bif) 1) => #f
 (fib-list? '((fib)) 2) => #t
 (fib-list? '(((fib)) fib) 3) => #t
 (fib-list? '((((fib)) fib) (fib)) 4) => #t
 (fib-list? '((((fib)) fib) ((fib))) 4) => #f

EXTRA CREDIT: Write the predicate so that it takes just a list lst and returns #t if there exists some number such that lst is a Fibonacci list of order , and #f otherwise.

Last modified: Thurs, Feb 6, 2003, 1:58 pm US/Eastern
HTML conversion by TeX2page 4p14a