CSCI 323/MCS9323: Artificial Intelligence

Assignment 1:

Question 1:

• (2 marks) Define the flatten( X, Y ) relation that holds when Y is a list structure that contains the same elements as X, in the same order, but with no nested lists.
  Hence,
  |?- flatten( [a, b, [c,d], [[e]]], Y).
  Y = [ a, b, c, d, e].
  no
  
  |?- flatten( [a,[b],[[[c]]], [d,e]], X).
  X = [a,b,c,d,e].
  no
  
  You may use the code
  non_nil_atom(X) :- X \== [ ], atomic(X).
  to test if a component is an atom that is not [ ].
• (2 marks) Write a Prolog program that defines a predicate merge(List1, List2, MergedList) that takes two lists List1 and List2 that are sorted in ascending order and generates MergedList which contains all of the elements of List1 and List2 and is also sorted in ascending order. Assume that the merging process eliminates duplicates. Thus, if List1 is [1, 3, 5] and List2 is [2, 4, 5], then MergedList must be [1, 2, 3, 4, 5].
• (2 marks)Define a predicate subsequence(L1,L2) which is satisfied by any pair of lists L1 and L2 which have the property that the elements of L1 occur in order in L2, but are not necessarily consecutive. For example subsequence([tues,wed,sat],[mon,tues,wed,thurs,fri,sat,sun]) should be true, but subsequence([thurs,wed],[mon,tues,wed,thurs,fri,sat,sun]) should fail.
• (2 marks) Write a Prolog program that implements the quicksort algorithm by defining a predicate quicksort(InList, OutList). Quicksort selects an arbitrary element of InList (this could be the first element in your case) and partitions the list into a list of elements smaller than the chosen element and a list of elements greater than the chosen element. The procedure is applied recursively to these two partitions. The resulting Outlist consists of the sorted list of elements smaller than the chosen element, followed by the element itself, followed by a sorted list of elements greater than the chosen element.

Question 2: (2 marks)