CSE 341 -- Programming Languages
Autumn 2002
|
Department of Computer Science and Engineering,
University of Washington
Steve Tanimoto (instructor)
|
Assignment
3
Version 0.1 of October 23 (Subject to
Change) |
One ml of ML
Due date and time: Thursday, November 7,
2002 (at the beginning of section).
Turn-in instructions will be announced later.
|
Title: One ml of ML
Purposes:
1. Get an exposure to ML.
2. Get insight into ML's type facilities.
Instructions:
Part A (Individual Work)
Display the online document "A Gentle Introduction to ML"
by Andrew Cumming. Read Lesson 1 and Lesson 2.
Make up an expression that will evaluate to...
A real number expressing the volume of a pyramid in
terms of its height and the area of its base.
A tuple representing
representing your last name, first name, day, month, and year
of birth (two strings and three ints).
A list representing the nine planets
of the solar system (from Mercury to Pluto) as strings.
A function that takes a list of four numbers (x1, y1, x2, y2)
that represent a line segment and returns the
the length of the line segment.
A function makequadraticevaluator that accepts three
real numbers a, b, and c and returns a function that takes
one argument, x, and returns the value of
2
ax + bx + c.
Part B (Group Work)
Write a function permutations that takes a list of elements
(of any type) and returns a list of all the permutations of
the original list.
Apply it to the problem of finding all possible dining sequences
for a meal that includes salad, turkey, and pie.
Then use it to generate all permutations of {0, 1, 2, 3}
Next, use your permutations function to enumerate all possible
tours for a travelling salesman problem expressed as a list
of 2D points. Here is an example list:
[[23.0,4.2],[38.3,5.8],[31.2,7.6],[27.9,4.9]].
Each point has an x-coordinate and a y-coordinate.
Assume that the distance between two points
is the Euclidean distance:
2 2
d((x ,y ),(x ,y )) = sqrt((x -x ) + (y -y ) )
1 1 2 2 1 2 1 2
Finally, compute the length of each tour by mapping the
distance function onto the list of permutations and finding
the minimum-length tour.