The objectives of this assignment are:

1. Make sure everyone can write some scheme procedures.
2. Recursion, Recursion, Recursion
3. Get familiar with a Scheme reference (there may be many useful/necessary procedures that are part of the Scheme library).

You are to write a number of Scheme procedures, each is described below. You will put all procedure definitions into a single file, named "hw1.scm" and submit this file to the WebCT dropbox named "HW1".

This procedure generates a list of the first n Fibonacci numbers, where n is a non-negative integer that is passed to the procedure.

If you don't know what a Fibonacci number is, you can read about them at en.wikipedia.org/wiki/Fibonacci_number

Sample Usage:

(fibo 0)
=> ()

(fibo 1)
=> (1)
(fibo 2)
=> (1 1)
(fibo 10)
=> (1 1 2 3 5 8 13 21 34 55)
(fibo 20)
=> (1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)

Issues: There are some efficiency issues you may want to consider, but for now all you have to worry about is getting a procedure to work any way you can.

This procedure removes all duplicate elements from a list or numbers. Each element in the list returned is unique. This procedure could be used to generate a representation of a set when given a list of numbers in the set (possibly containing duplicates). The order of elements in the return value is not important (If there are two 3s in the list, you can remove the first or the last - we don't care). Note that there can be many duplicates in the list!

Sample Usage:

(remove-duplicates '(1 2 3))
=> (1 2 3)

(remove-duplicates '(1 2 1))
=> (2 1)

(remove-duplicates '(1 1 1 1))
=> (1)

(remove-duplicates '(1 2 3 2 1 4 3 9 8 9 2))
=> (1 4 3 8 9 2)

Issues: You don't need to worry about anything other than numbers in the list.

This procedure produces the transpose of a matrix represented using Scheme lists. The single argument is a list-based representation of a matrix, where the number of elements of the list is the number of rows in the matrix and each list element is actually another list representing the individual values in one row. A few examples:

1 2 3 
4 5 6  --is represented as-->  ( (1 2 3) (4 5 6) (7 8 9) ) 
7 8 9   

1 0 1 1 0 1
0 0 1 0 0 0  -is-->  ( (1 0 1 1 0 1) (0 0 1 0 0 0) )

If you can't remember any linear algebra, Wikipedia can: en.wikipedia.org/wiki/Matrix_transpose.

Sample Usage:

(transpose '((1 2 3 4) (3 4 5 5)))
=> ((1 3) (2 4) (3 5) (4 5))
(transpose '( (1 2 3) (4 5 6) (7 8 9) ))
=> ((1 4 7) (2 5 8) (3 6 9))
(transpose '( (1 0 1 1 0 1) (0 0 1 0 0 0) ))
=> ((1 0) (0 0) (1 1) (1 0) (0 0) (1 0))

NOTE: Look at map and apply!

You need to write a scheme version of our thought exercise from class on 9/7: Write a scheme procedure that figures out how many valid tic-tac-toe boards exist. A board is valid if it reflects a possible game state when both players have played by the rules. An empty board is a valid game state, and a board that represents a (legal) win is also valid and should be counted.

Below are some examples of valid and invalid boards:

Don't consider isomorphisms, that is, don't worry about reflections, etc. If the board looks different, it is different. Strategic position is not important, just the actual geographic position of pieces on the board.

X goes first (always)!

Don't ask Dave what the correct answer is, as he has not yet figured it out (although he is working on a scheme procedure that will figure it out).

NOTE: You will very likely need to/want to write many procedures that are called by ttt-legal-boards, this is expected.

Grades will be based on the formula below. Note that to get full credit we must be able to understand your code. Your code must be neat (indented), and if it's not obvious what it's doing you must provide comments!

You can get partial credit for any part as long as your provide a description of what the code does do and what is missing/broken.