1. Express the following relations and queries in Prolog:
   • niece(X,Y): X is a niece of Y.
   • aunt(X,Y): X is an aunt of Y.
   • relative(X,Y): X and Y are relatives.
   • Who are joe's children?
   • How many children does joe have?
   • Are joe and steph relatives?
2. Give a tail-recursive definition for each of the following predicates.
   • power(X,Y,Z): X^Y=Z.
   • gcd(X,Y,Z): The greatest common divisor of X and Y is Z.
   • sum(L,Sum): Sum is the sum of the elements in L.
3. Write a program to generate all perfect numbers between 1 and 100. A perfect number is a positive integer that is equal to the sum of its proper divisors. For example, 6(=1+2+3) is a perfect number.
4. Assume a set is represented as a list without duplicates. Define the following predicates on sets:
   1. contains(X,S): X is a member of S.
   2. proper_subset(S1,S2): S1 is a proper subset of S2.
   3. disjoint(S1,S2): S1 and S2 are disjoint.
   4. union(S1,S2,S): S is the union of S1 and S2.
   5. intersection(S1,S2,S): S is the intersection of S1 and S2.
   6. difference(S1,S2,S): S is the difference of S1 and S2.
5. In Prolog, a binary tree can be represented as a structure of the form t(Value,Left,Right), where Left is the left subtree and Right is the right subtree. An empty tree can be represented as an atom, say void. Define the following predicates on binary trees:
   1. contains(T,X): T contains a node with the value X.
   2. count(T,N): the number of nodes in T is N.
   3. leaves(T,S): S is a set of leaves in T.
   4. inorder(T,L): L is the in-order traversal of the nodes in T.
6. Write a program in Prolog to solve the following arithmetic cryptographic puzzle: Find distinct digits for S, E, N, D, M, O, R, Y such that S and M are non-zero and the equation SEND+MORE=MONEY holds.
7. Find a NFA(Non-deterministic Finite Automaton) and write a program in Prolog to recognize it.