CS 538Final Exam1. (a) (8 points)2. (a) (18 points)3. (a) (13 points)4. (25 points) A well-known chess problem (often assigned in programming classes) is the “8 queen...5. (a) (6 points)6. (a) (12 points)CS 538Final ExamFriday, May 12, 20067:45 AM — 9:45 AM1325 Computer ScienceInstructionsAnswer any four questions. (If you answer more, only the first four will count.) Point values areas indicated. Please try to make your answers neat and coherent. Remember, if we can’t read it,it’s wrong. Partial credit will be given, so try to put something down for each question (a blankanswer always gets 0 points!).1. (a) (8 points)Assume we have a Prolog program with two contradictory rules of the form:a(X) :- b(X,Y), c(Y), fail.a(X) :- b(X,Y), c(Y).What is the effect of these two rules? Do they cancel each other out? Does one take precedence?Do they cause the evaluator to crash or loop? Justify your answer.(b) (17 points)The following Prolog rules define a binary relation y (x is used as a subroutine). What is therelation that y defines?x([A],[]).x([A|B],[A|T]) :- x(B,T).y([A],A).y([A|B],C) :- x(B,T), y(T,C).2. (a) (18 points)What is the type of the following ML function? How did you infer the type you selected?fun f(g1,g2,[],[]) = [] | f(g1,g2,h1::t1,h2::t2)=(g1(h1,g2(h2)))::f(g1,g2,t1,t2);(b) (7 points)What does the ML function of part (a) compute? What happens if f’s third and fourthparameters have different lengths?-2-3. (a) (13 points)Complete the following Java class definition. Class Set implements a set of objects (of typeObject). The constructor of no arguments creates an empty set. The constructor with anObject array argument creates a set containing the values in the array (with duplicatesremoved). Function union computes asetthatis the union of its twosetsparameters.Functionintersect computes aset that isthe intersection ofits two sets parameters. Function membertests whether a given object is a member of a set.class Set {Set() { ... }Set(Object[] values) { ... }static Set union(Set s1, Set s2) { ... }static Set intersect(Set s1, Set s2) { ... }static boolean member(Object v, Set s) { ... }}(b) (6 points)Change your Java solution to part (a) into a Pizza definition that uses parametricpolymorphism. That is, ratherthancontainingobjects of type Object,aset,now referenced asSet<T>, contains values of a single fixed type, T.(c) (6 points)Extend your solution to part (b) to include a member function map(f,s). Parameter f is afunction that takes a value of type T and returns a result of type T. Parameter s is a set of typeSet<T>. Function map applies f to each member of s, returning a set of result values (withduplicates removed).4. (25 points)A well-known chess problem (often assigned in programming classes) is the “8 queens prob-lem.” This problem requires you to place 8 queens on a chessboard so that no queen attacks anyother.In this problem we’ll address a simpler version of that problem in which 4 queens must beplaced ona4by4grid so that only one queen appears on each row and on each column, and atmost one queen appears on any diagonal. Assume we represent, in Prolog,a4by4chess boardas a list containing four sub-lists. Each sublist contains 4 elements, which can be a q (represent-ing a queen) or a b (representing a blank position). Thus the gridwould be represented as [[q,b,b,b],[b,b,q,b],[b,q,b,b],[b,b,b,q]]. (Thisposition is not a solution since two q’s appear on the same diagonal.)Write Prolog rules that define the relation solution(L). L is a list of lists representing areduced chessboard as defined above. Given that L is ground (already bound to a value),solution should succeed if L represents a solution to the 4 queens problem. That is,solution(L) should answer yes if L contains exactly 4 q’s, and only one q appears in eachrow and column, and at most one q appears on any diagonal.qqqq-3-5. (a) (6 points)Write an ML datatype definition that defines a polymorphic tree, 'a tree. A tree is defined tobe either a null tree, ora node containinga single valueof type 'a and a listof subtrees oftype'a tree. Your definition should startdatatype 'a tree = (* and you fill in the rest *)(b) 6 points)Write an ML function count, of type 'a tree -> int, that counts the number of leaves in atree. A leaf is a node that contains no subtrees.(c) (6 points)Write an ML function map, of type 'a tree * ('a -> 'b) -> 'b tree, that walks a tree oftype 'a and applies a function of type 'a -> 'b to each node. A tree of type 'b is returned.This output tree has the same structure as the input tree, but with node values updated byapplication of the function. (Note that if the identity function fnx=>xis mapped, a copyof the input tree is produced.)(d) (7 points)The airity of a tree is defined to be the maximum number of non-null children any node has.Thus a binary tree has airity 2 because each node has at most two children.WriteanMLfunctionairity, oftype'a tree -> int, thatdeterminesthe airityofan inputtree. (A null tree has airity 0.)6. (a) (12 points)Let f and g be Python functions and let L be a list containing values [v1,v2,..., vn].Write a Python function munge(f,g,L) that computes a list with the following 2*n values:[f(v1), g(vn), f(v2), g(vn-1), ..., f(vn), g(v1)](b) (13 points)Let f and g be Python functions andlet L be a list containingvalues [v1,v2,..., vn], wheren is even. Write a Python function mangle(f,g,L) that computes a list with the following nvalues: [f(v1), g(v2), f(f(v3)), g(g((v4)), f(f(f(v5))), g(g(g(v6)))),