Due Dates: Due by
midnight on the morning of your next
lab:
In addition, you should
submit the problems marked “in lab” and ask the instructor or grutor check them
before you leave the lab (that is, the lab at the start of the assignment week,
not the end). It would also be good, if you have time, to work on the problems
not to be turned in and ask questions about them. In this way, you can
anticipate areas of difficulty for the week to come.
Submissions
Place your answers in a file named a1.rex. This file must be loadable into the rex system
without generating any errors, so make sure you have comments around all the
non-rex parts of your answers. Whenever you are ready you can submit your file
by running
cs60submit a01.rex
(Make sure that a01.rex
is in the current directory when you do this. Also, this directory should not be at your top-level, for
security reasons; it should be a protected sub-directory. The submit program
will hassle you if you fail to observe this.) You will be prompted for the
assignment number; answer with the number 1. Remember, you can submit the
assignment as many times as you want. Only the last submission you make before
the deadline will be graded, so this is a great way to make backups of your
work as you go along.
It would be a good idea read Chapters 2 and 3 in the
course text in conjunction with this assignment. You will also need to
familiarize yourself with Unix, the operating system used on turing, the
computer we use. You will also need to learn the basics of emacs, the
recommended text editor. Finally, it may be worth spending some time learning
to an e-mail program such as elm or pine. Documentation on Unix, emacs, and
other items can be found on the CS 60 homepage under "Reference Links". Please spend
some time reading documentation, and trying out Unix, emacs, and e-mail before
embarking on the main part of the assignment. The instructor, grutors, and CS
staff in the terminal room will be happy to help you when you have questions.
It would be a good idea to become familiar with the
following built-in rex functions. They could be very useful in solving the
problems presented. It is suggested that you try a few examples to get familiar
with these functions.
|
Calling form |
Returned result |
|
first(L) |
the first element of non-empty list L |
|
second(L) |
the second element of non-empty list L |
|
sort(L) |
a sorted list containing the elements of
list L |
|
map(F, L) |
a list formed by applying function F to
each of the elements of list L |
|
mappend(F, L) |
provided that F returns a list, the result
of appending together the results of applying F to each element of list L |
|
reduce(B, U, L) |
the value obtained by applying binary
operator B to the elements of L and an accumulated value, one at a time; U is
the unit returned for the empty list |
|
member(E, L) |
1 if E is a member of list L, 0 otherwise |
|
explode(S) |
the list of individual characters in string
S |
|
implode(L) |
assuming L is a list of characters, the
string formed from those characters |
|
keep(P, L) |
the list of elements in L for which P is
true |
|
find(P, L) |
the suffix of L beginning with the first
element for which P is true |
|
remove_duplicates(L) |
a list containing the elements of L without
duplication |
|
concat(S, T) |
the string resulting from concatenating
strings S and T |
|
pow(N, P) |
number N raised to the power P |
|
Var =Value |
equate a variable Var to a value Value |
|
ls |
list
directory contents |
|
mkdir
name |
make
a directory |
|
cd directory |
change
to a named directory |
|
cd
.. |
change
to the parent directory |
|
cd |
change
to your home directory |
|
cat > file |
put
input into a file (terminate with control-D) |
|
rm file |
remove
a file |
|
rmdir
directory |
remove
a directory |
|
mv file directory |
move
a file |
|
mv file name |
rename
a file |
|
more |
show
contents of a text file |
|
emacs |
text
editor |
|
elm or pine |
mailer |
|
rex |
rex
language execution |
|
left button |
select |
|
middle button |
paste |
|
right button |
display pop-up menu |
/cs/cs60/a/01/a01.rexfactor
that will factor numbers for you. Alternatively, you may wish to do it more
yourself using the function firstFactor, also in that file, which merely returns the
first factor of a number (or the number itself if there is no smaller
factor other than 1).unFactor that takes the given representation as an argument
and produces the number being represented. For example,unFactor([[2, 3], [3,
1]])
==> 24.unFactor is called the inverse of factor
because it has the property thatunFactor(factor(N)) ==> Nfor
any positive N. Your definition should make use
of the higher-order functions reduce and map. It can employ the built-in
function pow, which raises numbers to a power.The text and lecture notes explain that binary
relations can be identified with sets of ordered pairs; two elements x and y
are said to be related by a
relation if the pair (x,y) is in the set. A relation is reflexive if every element in the domain of interest is related
to itself; that is, if the pair (x,x) is in the relation for every relevant x. A relation is symmetric if whenever (x,y) is in the relation so
is (y,x). Finally, a relation is said to be transitive if whenever (x,y) and (y,z) are in the
relation, so is (x,z).
An equivalence relation is a
binary relation that is reflexive, symmetric and transitive. For example, given
the finite set S = {1,2,3,4,5,6,7},
the relation on this set that relates two numbers in this set if they have the
same remainder when divided by three (also known as equivalence mod 3) is an equivalence relation. As discussed in the
text, we can represent relations on a finite set as a list of all the pairs
that are related:
[[1,1], [1,4], [1,7], [2,2], [2,5], [3,3], [3,6], [4,1], [4,4], [4,7], [5,2], [5,5], [6,3], [6,6], [7,1], [7,4], [7,7]]
However, the properties of equivalence relations
permit a more compact representation: As a set of equivalence classes, wherein
exactly the elements related to each other are grouped into a single
equivalence class. The definition of equivalence relation ensures that
equivalence classes don’t overlap (how?). For example, the relation above could
be represented as a set of equivalence classes below:
[[1, 4, 7], [2, 5], [3, 6]]
which is obviously more compact, as well as more readable.
1 if M is equivalent to
N in EC,
0 otherwise 1 0 equiv(7, 28, ec32) ==> 0 3.
Functional
Anagrams
One word is an anagram of another if it has exactly the same letters, with the
same multiplicity of each letter, but possibly in a different order. For
example, “elvis” is an anagram of “lives” but “eyes” is not an anagram of
“yes”. It should be obvious that we are dealing with an equivalence relation on
a set of words.
isAnagramOf that will check whether one word is an anagram
of another, for example: 1 isAnagramOf("eyes",
"yes")
==>
0 isAnagramOf.4.
Double Anagrams (Extra credit, for those who want more
challenge)
Two pairs
of words are called a double anagram
if the concatenations of the words in each pair are an anagram. For example
[“apple”, “fast”] [“flap”,
“paste”]
is a double anagram because “applefast” and “flappaste” are anagrams. Construct
a function doubleAnagramClasses that constructs the double-anagram equivalence
classes for pairs of words formed from the words in its argument list of words.
For example:
doubleAnagramClasses(
["aced", "cadet", "cut", "duct",
"paint", "pine", "put",
"putt", "tape", "taped", "twin",
"watt", "wet"]) ==>
[[[“duct”,
“tape”], [“cut”, “taped”], [“aced”, “putt”], [“cadet”, “put”]],
[[“tape”, “twin”], [“paint”,
“wet”], [“pine”, “watt”]]]
(so there are two equivalence classes in this case).