CS341, Spring 1996
Prolog Assignment #1
Assigned 5/22, due 5/31 midnight
merge_sort/2 whose first
argument is a list of numbers, and whose third
argument produces the sorted version of the
first argument. In doing so you should write the
following predicates.
split_evenly/3. The first parameter
is a list of integers, whose elements should be
split into lists of ``approximately'' equal length:
if the input list has even length the output lists
should have equal length; if odd, one should be one
longer than the other. The second two parameters hold
the output lists.
One easy way to do this is by ``alternating'' moving
elements from the first list to the second list, then
from the first list to the third list.
Here are some hints. Notice how my split_evenly
function splits the list:
:- split_evenly([2,1], L2, L3) L2 = [2] L3 = [1] :- split_evenly([1,2,3,4,5], L2, L3) L2 = [1, 3, 5] L3 = [2, 4] :- split_evenly([1], L2, L3) L2 = [1] L3 = []
merge/3. The first two parameters are
sorted lists of integers; the third is the merge of
the first two.
a and g). The ``length''
of a path is defined to be the sum of the weights on the arcs
between the nodes.
One very simple shortest-path algorithm is to find all paths between
a and g, compute the length of each path, and take
the minimum. That is what you will implement here.
connects(source, destination, weight) where source
and destination are node names (these can be symbols),
and weight is a non-negative integer.
path_from(A, B, W)
which succeeds if there is a path from node A to
node B of length W.
min/2 whose first parameter
is a list of integers and whose second parameter holds
the minimum of those integers. This predicate should fail
if there are no integers in the list.
shortest/3 whose first
two parameters are node names, and whose third produces
with the shortest path from the first two parameters.
add_employee take one fewer parameters.
make_manager/2 which
establishes that the first Id number is the manager of the second
Id number. This should fail if the second Id number already
has a manager (and that manager is different from the input).
subordinates/2 should produce
the list of subordinates for the first parameter.
print_nicely predicate so it
prints a list of the people the employee manages indented
under the employee's name. For example,
Employee 3: Name is Sally, Wage is 10.00 Employee 2: Name is Fred, Wage is 5.00You should only nest this list one deep, so if Fred manages anybody, they won't be displayed here.
deadbeat(Id) that succeeds if the
Id is that of a deadbeat.
add_hours(Id, Hours)
that records the fact that the employee worked the specified number
of hours. This should be cumulative. Then write the predicate
payroll(N) which computes and returns in N the
total payroll (total hours times wage rate) for all employees.
The predicate should as a side effect reset the cumulative hours
for all employees to 0.
You will hand this assignment in electronically on the MSCC machines. Hand in two files: in one put your solution code, and in the other a transcript that shows tests of all parts of the solution.