Week 3: Exercises

1. Digits

Write a predicate digits(L, N) that converts a list of digits (e.g. [3, 4, 5]) to an integer (e.g. 345). Your predicate should work in both directions.

2. Permutations

Write a predicate permutation(L, M) that is true if the list L is a permutation of M.

3. Combinations

Write a predicate combination(L, N, M) that is true if M is a combination of N elements of L, i.e. a subset of size N that has its elements in the same order as in L. Elements in M should appear in the same order as in L.

4. Insertion Sort

Write a predicate insertion_sort(L, S) that sorts a list L of integers. Use an insertion sort.

5. Time Addition

Let the structure time(H, M, S) represent the 24-hour time H:M:S, where H, M, and S are integers. Write a predicate plus(T, N, Q) that is true if time T plus N seconds equals time Q. Your predicate should work in all directions.

6. Flatten

Write a predicate flatten(LL, L) that is true if L is a list containing all elements in the list of lists LL. For example, flatten([[a, b, c], [d, e], [f, g, h]], L) will produce L = [a, b, c, d, e, f, g, h].

7. Addition

Suppose that we represent natural numbers using structures: 0 = z, 1 = s(z), 2 = s(s(z)) and so on.

Write a predicate sum(I, J, K) that is true if I + J = K, where I, J, and K have this numeric representation. Your predicate should work in all directions.

8. Lists from Structures

Without using Prolog's built-in list type, we may define lists using structures as follows. Let nil represent the empty list, and let cons(X, L) represent the value X prepended to the list L. With this list representation, write predicates member(X, L) and append(L, M, N).

9. Graph

We may represent a directed or undirected graph in Prolog using adjacency list representation. For example, consider this graph:

We will represent it using this list:

G = [ a -> [b, e], b -> [c, f], c -> [], d -> [],
      e -> [d, f], f -> [a, c], g -> [d, h], h -> [f] ]

Write a predicate edge(G, V, W) that is true if there is an edge from V to W in the graph G.

10. Graph Edges

Write a predicate edges(G, L) that succeeds if L is a list of all edges in the graph G, where an edge from V to W is represented as e(V, W).

11. Graph Path

Write a predicate path(G, V, W, P) that succeeds if P is a path from vertex V to vertex W in the undirected graph G, which may contain cycles.