CSE 341 Assignment 1 Solution (postscript)
October 27, 1998

1.

Write and test a Scheme function pythagoras that takes the lengths of the two legs of a right triangle and returns the length of the hypotenuse. For example:

(pythagoras 3.0 4.0)  => 5.0

Solution:

hw1-1.s

Output:

hw1-1.out

2.

Write and test a Scheme function no-duplicates that takes a list of numbers as an argument, and returns a new list which is like the argument but with duplicate elements dropped. The order of the elements in the returned list doesn't matter. For example:

(no-duplicates '(1 3 3 8 5 3 5))  => (1 3 8 5)
(no-duplicates '(1 3 5))  => (1 3 5)
(no-duplicates ())  => ()

Solution:

hw1-2.s

Output:

hw1-2.out

3.

Write and test Scheme functions contains, add, and delete to manipulate binary search trees. contains should take a tree and an element as arguments, and return true or false depending on whether the tree contains the element. add should take a tree and an element as arguments, and return a new tree with the element added. delete should take a tree and an element as arguments, and return a new tree with the element deleted. For both add and delete, the existing tree that is the argument should not be altered.

If you try to add an element to a tree that already contains that element, just return the tree (don't make a new tree). If you try to delete an element from a tree that doesn't contain it, signal an error using

     (error "element not found")

You should choose an appropriate representation for binary trees (hint: represent a node in the tree as a list with 3 elements).

Solution:

hw1-3.s

Correctness Checking Code:

hw1-3-test.s

Output:

hw1-3.out

The entire assignment 1 solution hw1.s and postscript.