Honors Programming Languages

G22.3110 Fall 2000

SETL Programming Assignment

Due on December 11

Note: I changed  2 < i <= k into 2 <= i <= k, in the text below. The previous version was underspecified, since it allowed N2 to be arbitrary, instead of being equal to N0 + N1.

This program should take you about an hour. Please get it over with as soon as possible.

Write the procedure fib_subsets(S) which returns the set of all subsets of set S that represent a "fibonacci set".

For our purposes, we'll call a fibonacci set a set of (positive or negative) integers

{N0 , ...  , Nk}, k > 1
such that N1 > N0 and Ni = Ni-1 + Ni-2, 2 <= i <= k. Being a set, a fibonacci set is unordered, of course.

An example of a fibonacci set is{29, 4, 3, 11,18, 7}.