This assignment is to be done in PLT Scheme/Racket. You should get at least some of these functions written in class on Sept. 16, and do the rest on your own time. You are encouraged to do this in teams of two, both students working together on each function; if you do this, turn in one homework with both names on it.
For all functions, follow the design recipe: each function must have a contract, a good collection of test cases, and a function definition.
In order to get your homeworks graded quickly, I won't actually grade every one of these problems, but rather a sample including problems of various levels of difficulty. The rest are practice. If there's one that you want to make sure I look at, call my attention to it when you turn in the homework.
Switch languages to PLAI for the following exercises, which are
intended to be done using define-type and
type-case. Note that PLAI doesn't have
check-expect, but has several other built-in
forms for testing; look them up in the Help Desk.
Define a data type vehicle with three variants:
automobile has a fuel capacity (a number, in gallons) and a fuel
efficiency (a number, in miles per gallon). solar-car has a top speed (a number, in miles per
hour).bicycle has a number of gears (an integer).
Define a function range which takes in a vehicle and
tells how far it can go, as follows: the range of an automobile is its fuel
capacity times its fuel efficiency; the range of a solar-car is its
top speed times 12 (hours of sunlight); and the range of a bicycle is
50 miles.
Define a data type shape with two variants:
circle has a numeric radius and a center
(of type posn; since the PLAI language doesn't have
"posn" built in, you'll need to define it with
(define-struct posn (x y))).rectangle has a numeric width, numeric height, and
top-left (of type posn).
Define a function area which takes in a shape and returns
its area.
Define a function contains? which takes in a shape and a
posn and tells whether the posn is inside the shape.
Modify your data definition so there's a third variant:
union has two shapes, which we'll call by the
names "a" and "b".area and contains? functions to
work correctly for this new variant. area, you may assume that the
two shapes of a union don't overlap, so you can just add their areas.
(Otherwise this becomes a complicated geometry problem, and that's not
what I want you to worry about right now.) For
contains?, your function should work correctly regardless
of whether the two shapes overlap.
Define a data type river with three variants:
spring has a numeric volume, how
much water the spring produces (in gallons per hour).section has a numeric length (in
miles), and another river at the far end.branch has two rivers,
left and right.
Define a function volume that takes in a river and
returns the total amount of water flowing out of it (in gallons per
hour). This is obvious for a spring. For a section, the volume is
the same as the volume at the far end (let's pretend there's no
evaporation). For a branch, the volume is the sum of the volumes of
the two branches.
Define a function max-length that takes in a river and
returns the longest distance to any spring.
You can do these exercises in either PLAI, Beginner, or Beginner with List Abbreviations language.
Write a function add-up which takes in a list of
numbers and returns the sum of the numbers.
Write a function any-matches? which takes in a
string and a list of strings, and tells whether the string matches any
of the strings in the list.
Write a function count-matches which takes in a
string and a list of strings, and tells how many list
elements match the string (possibly 0).
Write a function count-over which takes in a
number and a list of numbers, and tells how many list elements are
larger than the specified number.
Write a function average that takes in a list of
numbers and returns their average. For a first version of this
function, you may assume there is at least one number in the
list. For full credit, your function should generate an
appropriate and user-friendly error message for the empty-list case.
Write a function convert-reversed that takes in
a list of numbers (which you may assume are all integers in the range
0-9), interprets them as digits in a decimal number, ones place
first (trust me, this makes it easier!), and returns the number
they represent. For example,
(convert-reversed (list 3 0 2 5)) should be
5203.
Write a function dollar-store? that takes in a
list of numbers -- the prices of things at a store -- and tells whether
or not everything in the store is priced under a dollar.
Write a function multiply-all that takes in a list
of numbers and returns their product. Hint: What is
the "right answer" for the empty list? It may not be what you think
at first!
Write a function largest that takes in a non-empty
list of numbers and returns the largest one.
Hint: There are several possible ways to handle the
empty case....
Write a function total-votes that takes in a list
of candidate structures (from homework 1) and returns the
total number of votes cast.
Write a function winner that takes in a list of
candidate structures and returns the name of the winner,
or the word "tie" if there was a tie for first place.
(How do you want to handle the empty-list case? I guess we could call
it a "tie"....)
Write a function square-each that takes in a list
of numbers and returns a list of their squares, in the same order.
For example,
(square-each (list 4 -3 1 12)) should return (list
16 9 1 144).
Write a function substitute that takes in two
strings and a list of strings, and returns a list the same length as
the given list, but with all occurrences of the first string replaced
by the second. For example,
(substitute "old" "new" (list "this" "that" "old" "new"
"borrowed" "old" "blue")) should return
(list "this" "that" "new" "new" "borrowed" "new" "blue")
Write a function remove-first that takes in a
string and a list of strings, and returns the same list but with the
first occurrence (if any) of the given string removed. For example,
(remove-first "old" (list "this" "that" "old" "new" "borrowed"
"old" "blue"))
should return
(list "this" "that" "new" "borrowed" "old"
"blue").
Define a data type bst (short for "binary search
tree") with two variants:
leaf has no fields at all.node has a numeric value and two
bst's named "left" and "right".
A proper bst is one in which every node's value
is larger than any of the numbers in its left bst, and
smaller than any of the numbers in its right bst.
Define a function proper-bst? which takes in a
bst and tells whether it is proper.
Define a function in-bst? that takes in a number
and a proper bst, and tells whether that number appears
in the bst. Hint: use the assumption
that the bst is proper to help you efficiently find the
number, if it's there, or know for certain that it isn't there.
Define a function path-to that takes in a number and a
proper bst, and returns a list of node values
encountered
on the way from the root of the tree to the number in question (or to
where it would be if it were there). The list should end with the
desired number if it was in the tree.
Define a function insert that takes in a number and a
proper bst, and returns a proper bst just
like the given one, but containing the specified number. If the
number was already there, you may return the exact same
bst.
Define a function make-bst that takes in a list
of numbers and returns a proper bst containing exactly those
numbers. [I left out the word "proper" when I originally gave this assignment.]