Write a predicate digits(L, B, N) that is true if
L is a list of digits in base B whose value is N. For example,
digits([3, 4, 5], 10, 345) is true. First write the
predicate (a) using an accumulator, then (b) using a left fold.
Write a predicate dot(V, W, X) that
is true if X is the dot product of vectors V and W, which must have
the same dimension. First write the predicate (a) using an
accumulator, then (b) using a left fold.
Write a predicate acute(V, W) that
takes two vectors of dimension 2 or greater, represented as lists of
floats. The predicate should succeed if the angle between the vectors
is acute, i.e. less than 90 degrees.
a) Write the built-in predicate foldl(+P,
?L, ?A, ?R) that performs a left fold over the values
in L. For example, foldl(P, [x, y, z], A,
R) will call
P(x, A, A1), P(y, A1, A2), P(z, A2, R).
b) Write a predicate foldr(+P, ?L, ?A, ?R) that performs
a right fold over the values in L. For example,
foldr(P, [x, y, z], A, R) will
call
P(z, A, A1), P(y, A1, A2), P(x, A2, R).
Write a predicate merge_sort(L, S)
that sorts a list L of integers. Use a merge sort.
Write a predicate quicksort(L, S)
that sorts a list L of integers. Use a quicksort. Use the first
element of L as the pivot element.
Consider binary trees represented as nil
(the empty tree) or as t(L, X, R), where L and R are
left and right subtrees.
a) Write a predicate count(T, N) that
is true if the tree T contains a total of N nodes. Your predicate
should be able to generate all trees with a given number of nodes.
b) Write a predicate height(T, H)
that is true if H is the height of the binary tree T. Recall that the
height of a tree is defined as the maximal distance from the root to
any leaf. Your predicate should be able to generate all possible
trees of any height.
c) Write a predicate maptree(P, T)
that succeeds if a predicate P is true for every value in a tree.
Write a predicate flatten(T, L) that
flattens a tree, producing a list of values in the tree. For any node
t(L, X, R), the values in L should appear before X in
the list, and the values in R should appear after X. What is the
best-case and worst-case running time for your predicate for a tree
with N nodes?
Write a predicate foldr_tree(P, T, A, R)
that performs a right fold of a predicate over all values in a tree.
Write a predicate insert(X, T, T1)
that inserts a value X into a binary search tree T, producing a tree
T1. If the value X is already in the tree T, then T1 should equal T.
Is it possible to delete values from a tree by
running insert() backwards? Why or why not?
In this cryptarithmetic puzzle, every letter stands for a different digit:
A P P L E + G R A P E + P L U M =========== B A N A N A
Write a Prolog program that can find a solution to the puzzle.
A magic square is a square of size N x N that contains all integers from 1 .. N2 and in which every row, column and diagonal adds to the same value.
Write a Prolog predicate that can test whether a square is magical. When run backward, it should also be able to generate magic squares of a given size.
Consider an acyclic graph, such as
We may represent it using an adjacency list representation:
graph1(G) :- G =
[ a -> [b, e], b -> [c, f], c -> [],
d -> [], e -> [d, f], f -> [c],
g -> [d, h], h -> [f] ].
a) Write a predicate edge(G, V, W) that is true if the
graph G in this representation has an edge from vertex V to vertex W.
b) Write a predicate path(G, V, W, P)
that is true if P is a path from V to W in the graph G.
Consider a graph with a cycle, such as
Here is its representation in Prolog:
graph2(G) :- G =
[ a -> [b, e], b -> [c, f], c -> [a],
d -> [], e -> [d, f], f -> [c],
g -> [d, h], h -> [f] ].
a) Try to use your predicate path() from the previous
exercise to search for a path from a to e in this graph. Does it
find a path?
b) Write a predicate iter_path(G,
V, W, P) that searches for a path from V to W using iterative
deepening. Can iter_path() find a path from a to e?
Will the first path that iter_path() produces always be
a shortest path?
c) Suppose that a graph contains N vertices. Is
iter_path() guaranteed to find a path from a vertex V to
a vertex W in O(N)? If not, how long might it take?
d) Write a predicate linear_path(G, V, W, P)
that searches for a path from V to W, only considering paths that do
not contain any vertex twice. Do not use iterative deepening. Hint:
Write a helper method extend(G, V, P, Q) that is true if
the path P can be extended backwards to reach V, producing a path Q.
Can linear_path() find a path from a to e? Will the
first path that linear_path() produces always be a
shortest path?
e) Suppose that a graph contains N vertices. Is
iter_path() guaranteed to find a path from a vertex V to
a vertex W in O(N)? If not, how long might it take?
f) Write a predicate bfs_path(G, S, T, P)
that searches for a path from S to T using a breadth-first search
with a visited set. Hint: Write a helper predicate bfs(G, Q,
Vis, T, P) including arguments Q (a queue for the
breadth-first search) and Vis (a list of visited
vertices). Each element in the queue should be a path from the start
vertex to some vertex V, in reverse order. Can bfs_path()
find a path from a to e? Will the first path that bfs_path()
produces always be a shortest path?
g) Suppose that a graph contains N vertices. Is
bfs_path() guaranteed to find a path from a vertex V to
a vertex W in O(N)? If not, how long might it take?
Write a predicate hamiltonian(+G, ?P)
that takes an undirected graph in adjacency list representation and
succeeds if P is a Hamiltonian path in G, i.e. a path that visits all
vertices exactly once.
You could test your predicate on this graph:
graph(G) :- G = [ a -> [c, e], b -> [d, e], c -> [a, d, f],
d -> [b, c, e, f], e -> [b, d, f], f -> [c, d, e, g],
g -> [f] ]Write a predicate colorable(+G, +N)
that takes an undirected graph in adjacency list representation and a
positive integer N. The predicate should succeed if the graph is
N-colorable, i.e. it is possible to assign one of N colors to each
vertex in such a way that no adjacent vertices have the same color.
Write a predicate isomorphic(+G, +H)
that takes two graphs in adjacency list representation and succeeds
if the graphs are isomorphic.
Suppose that we have a set of rectangles, each with a given width and height. We want to know whether they can be packed into a rectangle R with a given width and height and depth. The rectangles may not be rotated.
We will represent a rectangle
as a structure rect(Width,
Height).
Write a predicate pack(L,
R, Positions)
that is true if the rectangles
in list L can be packed into the rectangle R at the given list of
positions. A rectangle's position pos(X, Y) is
the position of its upper-left corner relative to the upper-left
corner of rectangle R.
Modify
your solution to the previous exercise so that the rectangles in list
L may be rotated by 90 degrees as they are packed into R. Now each
position should have the form pos(X, Y, R),
where R
= rot if the
rectangle has been rotated by 90 degrees, otherwise R
= not.
Write a higher-order predicate solve(+Move,
+Start, +Goal) that can find the shortest path from a start
state to an end state in any state space. Move(+S, ?T) should be a
predicate that succeds if it's possible to move from state S to state
T. Goal(+S) should be a predicate that's true if state S is a goal
state.
Three missionaries and three cannibals wish to cross a river using a boat that can carry only two people. At no time may the cannibals outnumber the missionaries on either river bank, since then they would eat the missionaries. How can they cross? Write a Prolog program that can find the shortest solution.
A farmer is on the south bank of a river with a wolf, a goat, and a cabbage. He has a boat that can hold him plus any one of these three items. If the wolf and goat are left alone without the farmer, the wolf will eat the goat. If the goat and cabbage are left alone without the farmer, the goat will eat the cabbage. The wolf does not like cabbage.
How can the farmer cross with all of these possessions to the north bank? Write a Prolog program that can determine the shortest solution.
Three jugs have capacity 8, 5 and 3 liters. Initially the first jug is full of water, and the others are empty.
We can pour water between the jugs, but they have no markings of any sort, so we can pour between two jars only until one of them becomes full or empty.
What sequence of moves can we make so that the jugs will hold 4, 4, and 0 liters of water, respectively?
Write a Prolog program to find the shortest possible solution.
Four people wish to cross a river using a narrow bridge, which can hold only two people at a time. They have one torch and, because it's night, the bridge crossers must take the torch.
Person A can cross the bridge in 1 minute, B in 2 minutes, C in 5 minutes, and D in 8 minutes. When two people cross the bridge together, they must move at the slower person's pace. Can they all get across the bridge if the torch lasts only 15 minutes? Write a Prolog program that can determine the answer.