ASSIGNMENT 3. Due January 22.
----------------------------

==================================================================
1.

- Compute E\theta, where E=f(x,f(x,b,y),g(a,z)) and \theta= {x -> y, y -> g(a,z), z -> x\}.

- Compute \theta\sigma, where \theta={x -> f(x), y -> z, z -> g(a,y,h(x))} and \sigma= {x -> y, z -> y,  y -> h(y), w -> a}.

- Compute \theta\theta, where \theta={x -> f(x), y -> z, z -> g(a,y,h(x))}.


==================================================================

2. Write a binary predicate count_occurrences(input,result) that is true if 'result' is
a list of two-element lists [el, number_of_occurrences_in_input], where 'el' is an element of
the list 'input', and 'number_of_occurrences_in_input' is an integer specifying how many times
'el' occurs in 'input'. For each element 'el' in 'input' there should be a corresponding pair
[el, number_of_occurrences_in_input] in 'result'.
Sample run:

?- count_occurrences([a,b,a,a,b,c],X).

X = [[c, 1], [b, 2], [a, 3]] ;

No

================================================================

3. Write a predicate count_and_print_occurrences that first asks the user
to provide a list, then asks where to print the output (on the screen or
in a file), counts occurrences in the list using the program developed
in the exercise 4 above, and prints the output either on the screen or in a
file specified by the user as follows: If, for instance, the count_occurrences
program computes the answer [[c, 1], [b, 2], [a, 3]], then
count_and_print_occurrences should print the following:

c occurs in the input once.
b occurs in the input twice.
a occurs in the input 3 times.
No other element occurs in the input.

=================================================================

4. Implement the mergesort algorithm.


====================================================================

5. Is the predicate p defined below tail recursive? Justify your answer.

p([H|T]):-
    q,
    p(T).
p([]).
q.

====================================================================

6. Solve the following puzzle (from Edi Weitz).

Three mice are living next to each other in three holes in the wall. Each mouse
has a favorite cheese flavor and a favorite TV show. Here are the hints:

1. Mice: Mickey, Mighty and Minny.
2. Cheese: Gouda, Emmentaler, Brie.
3. Shows: Emergency Room, Seinfeld, Simpsons.
4. Mickey Mouse loves Gouda.
5. Mighty Mouse's favorite TV show is Emergency Room.
6. The mouse that lives in the left hole never misses an episode of Seinfeld.
7. Mickey Mouse and Mighty Mouse have one mouse hole between them.
8. The Simpsons fan does not live on the left of the Brie lover.

For each mouse find the hole where it leaves, a favorite cheese and a favorite show.

=======================================================================

7. Implement a ternary predicate flatten_term(Function_symbol, Term, Flattened_term)
that succeeds if Flattened_term is obtained from Term by flattening out all
nested occurrences of Function_symbol. Term contains no Prolog variables and no lists.
Sample runs:

?- flatten_term(f, f(f(x)), Flattened_term).
Flattened_term = f(x).

?- flatten_term(f, f(x), Flattened_term).
Flattened_term = f(x).

?- flatten_term(f, a, Flattened_term).
Flattened_term = a.

?- flatten_term(f, g(f(x)), Flattened_term).
Flattened_term = g(f(x)).

?- flatten_term(f, g(f(f(x))), Flattened_term).
Flattened_term = g(f(x)).

?- flatten_term(f, f(g(f(x))), Flattened_term).
Flattened_term = f(g(f(x))).

?- flatten_term(f, f(f(f,g(f(y)))), Flattened_term).
Flattened_term = f(g(f(y))).