Set Wednesday April 10th, due Thursday April 18th
Reading: Over the next couple of weeks, please read chapters 1 and 2 of
the book by Ferber.
Problems: Please do problems 1 through 5. Problems 6 and 7 are for
your interest.
1. Split
Write and run a Prolog predicate split(Numbers,Positives,Negatives)
which splits a list of numbers into two lists,
one containing the positive ones and the other the negatives.
2. Write a predicate no_doubles(X,Y)
which removes all duplicate elements from a given list.
3. Split using cut
Write a version of split (from homework 1) using a cut.
Predicate split(Numbers,Positives,Negatives)
splits a list of numbers into two lists,
one containing the positive ones and the other the negatives.
4.
Define a predicate subtract
subtract(Set1,Set2,Set3)
where Set3 is the result of subtracting Set1 from Set2.
Sets can be represented as lists.
5. Write a predicate route(X,Y,R) which finds
a route between two given nodes X and Y in a directed graph
which may have cycles. For example, you might
represent the graph by a set of assertions such as
arc(a,b).
6. Add cuts to the following insertion sort program
to improve its efficiency.
/*
sort(Xs,Ys) :-
The list Ys is an ordered permutation of the list Xs.
*/
sort([X|Xs],Ys) :- sort(Xs,Zs), insert(X,Zs,Ys).
sort([],[]).
insert(X,[],X).
insert(X,[Y|Ys],[Y|Zs]) :- X > Y, insert(X,Ys,Zs).
insert(X,[Y|Ys],[X,Y|Ys]) :- X =< Y.
7. Use bagof to define the relation powerset(Set,Subsets)
to compute the set of all subsets of a given set, where all sets
are represented as lists.
Please set up a web page with your solutions and email me the URL.
You should include enough data cases to allow me to assess your program.