CS 541 HOMEWORK 3, part b, Prolog For all Prolog programs, you must run your code with either C Prolog or SBProlog. You must also provide evidence that your program is correct (verbal arguments or test cases or both). You might wish to look again at section 4 of the course specification for more details. NOTE FOR NEXT YEAR: GIVE INFO ABOUT WHAT KINDS OF QUERIES THE SOLUTIONS MUST BE ABLE TO ANSWER The following problems are due Friday, Feb. 14. 1. Specify a relation, permutations/2, such that permutations(L1,L2) holds if L1 and L2 are lists such that each element of L1 is found exactly once in L2, and L2 does not have any extra elements not found in L1. Essentially this is a multiset equality relation (where a list represents a multiset). You should be able to use permutations/2 as both a test and as a generator of permutations. 2. Specify a relation, set_equality/2, such that set_equality(L1,L2) holds if L1 and L2 are lists such that each element of L1 is a member of L2 and vice versa. 3. Consider binary trees as described by the following clauses. binary_tree(null). binary_tree(tree(Left,Val,Right)) :- binary_tree(Left), binary_tree(Right). a. Specify a relation, leaves/2, such that leaves(T,L) holds if T is a binary tree, L is a list or a difference list (say which), and L is the list of all the leaves of T, in order from left to right. For example, if you are using lists, leaves(tree(tree(null,a,null),b,tree(null,c,null)),[a,c]) should be satisfied. If you are using difference lists, leaves(tree(tree(null,a,null),b,tree(null,c,null)),[a,c]\[]) should be satisfied. b. Specify a relation same_leaves/2, such that same_leaves(T1,T2) holds if T1 and T2 are binary trees with the same leaves in the same order. 4. Consider the following plan (PERT diagram) for building a house. walls-6 ceiling-5 /-------->[c]----------\ / \ \ foundation-5 / \ \ [a]------------->[b] \electric-2 \ painting-2 \ ----------->[d]------------[e] \ plumbing-4 / \------------------------/ The idea is that it takes 5 days to pour the foundation, and only after the foundation is done can work begin on the walls and plumbing. It takes 6 days for the walls, 4 days for the plumbing. Only after the walls are built can the ceiling and electrical work be done. a. describe the above PERT diagram by assertions in Prolog. b. Write a program that will compute the critical path, both for this example and for all similar databases of assertions describing PERT diagrams. For example, you might make a predicate critical/2, such that critical(Total_Time,Activity_List) holds if Total_Time is the total time needed for the PERT diagram described in Prolog's database and Activity_List is the list of activities (in order) on the critical path. In the example above, critical(18,[foundation,walls,ceiling,painting]) should hold. 5. Program the following operations on difference lists; you are not allowed to simply transform them to ordinary lists. a. diff_add_to_end/3 b. diff_reverse/2 c. (extra credit only) diff_quicksort 6. (extra credit only) Specify a relation learn_regular/2 such that learn_regular(Examples,Grammar) holds if Examples is a list of positive (or negative) examples of sentences in (or not in) a regular language and Grammar is a regular grammar such that each positive example is in the language generated by the grammar, and none of the negative examples are. A variation would be to use regular expressions instead of grammars.