Dr. Christoph F. Eick COSC 4350 ASSIGNMENTS Spring 1998 1) CONS,LIST,CAR,CDR,APPEND a) Provide LISP-expressions that create the following list structures: a1) (2 4 ((3)) ((4 8 5))) a2) ((a)) a3) ((2 (1)) . b) a4) ((a) b (c (e)) (1 2 3)) b) For each of the following list structures provide a lisp expression that generates the same list by only using the operator cons. For example for (list 'a) the solution is: (cons 'a nil). b1) (list 'a 'b (list 'a 'b) 'c) b2) (append '(1 2 nil) '(3 4) '(((1))) ) b3) (car '(((6)) 3)) b4) (append '(a b) (list 2 3)) 2) CELL NOTATION Give the contents of x, y, z in cell notation after the following assignments are executed. (setq x '(1 2)) (setq y (list (list x x (car x)))) (setq z (append x x (car y) x)) (setq x (cons x (cddr z)) 3) WRITING A RECURSIVE LISP-PROGRAM Write a functions rotate that puts the first element of a list to the end of the list. E.g. (rotate '(1 2 3)) returns (2 3 1); (rotate '(8)) returns (8), and (rotate nil) returns (nil) and (rotate 'b) returns b. Next write a recursive LISP-function my-rotate that rotates all levels of a list and not only the toplevel --- like rotate does; e.g. > (my-rotate '(1 2 (4 5 6) (7 8))) (2 (5 6 4) (8 7) 1) 4) Write functions north, south, east and west to manipulate 3x4 12 puzzles (each operator moves, if possible, * in the indicated direction and produces an error message otherwise). The state of a 8 puzzle is represented as a 12 element list. For example, * 1 2 10 3 4 5 9 7 8 9 11 7 8 11 1 5 4 3 9 * 2 10 5 correspond to the lists (* 1 2 10 7 8 9 11 5 4 3 9) and (3 4 5 9 7 8 11 1 * 2 10 5), respectively. Moreover, provide an function apprules that returns a list of opertors which can be applied to the particular configuration of the puzzle. For example: > (south '(* 1 2 10 7 8 9 11 5 4 3 9)) (7 1 2 10 * 8 9 11 5 4 3 9) > (east '(* 1 2 10 7 8 9 11 5 4 3 9)) (1 * 2 10 7 8 9 11 5 4 3 9) > (apprules '(* 1 2 10 7 8 9 11 5 4 3 9)) (south east) 5) SEARCH Write a LISP-function (defun 12-puzzle (in-state goal-state) ... that can solve 12-puzzles relying on a backtracking strategy or by using graphsearch strategy possibly combined with heuristics; if your program can find a solution, it will returns the successful path that leads from the initial state to the goal state; otherwise, it returns fail. Your are allowed to reuse code that has been discussed in the book and/or in the class. Run your program for the test-cases that will be given to to you later. 6) Write a "greedy" hillclimbing algorithm (defun tsp ( <#-of-cities>) ...) that solves the travelling salesman problem for n cities 0,...,n-1. The algorithm starts with a starting city and completes the path by choosing the cheapest continuation until all cities have been visited. Assume a 2 parameter integer function cost is available that returns the cost for getting from city i to city j. The function tsp returns its solution in the form: ( ) e.g. it might return ((0 1 2 3 4 5 6 9 10 8 7) 299) which represents the solution 0-1-2-3-4-5-6-9-10-8-7 with cost of 299. Run your program 10 times using different starting cities for a 11-city travelling salesman problem for two cost functions d2 and d3 whose definitions are given in the file "distance.l" in the WWW-4350 directory. Then solve the 60 city travelling salesman problem with starting city 0 for distance function d4. 7) Write a program that checks if a list is cyclic (be careful that your program never prints the list because the printing will never stop). Remark: A cyclic list is a list whose cell-notation graph contains a cycle. 8) Extend the backtracking algorithm so that it immediately returns control to the top-level function in the case that a solution has been found (hint: use catch and throw for this purpose). Rerun the algorithm for two easy test-cases of the 12-puzzle)! 9) BAYESIAN INFERENCE NETWORKS Design and implement an inference network that evaluates students that apply for a scholarship. Provide some functions on the top of the inference network that request inputs from the user, print out the results of the evaluation process and explains the inference network's decision making. Depict and explain your inference network. Submit two example runs of your inference network and add explanation to the two example runs that clarifies how your inference network comes up with a decision in the particular case. Be prepared to demo your program. You can reuse the code of the program that is described in chapter 7 of our textbook! 10) SYMBOLIC REGRESSION WITH GENETIC PROGRAMMING Develop a program that can perform symbolic regression to learn functions of arity 2 relying on a genetic programming approach: * Function Set: |cos(x)|, |sin((* 30 x)|, *, +, -, sqrt(|x|), '+','-' and '*' are assumed to be binary. and cosa, sin30a, sqrta are assumed to be unary. * Constant Set: floating points in [0,1]: 0.00, 0.01, 0.002,...,1.00, and the variables x and y. * Functions to be learnt are resticted to: [0,1] x [0,1] --> [0,1] * A training set of 25 triples (x, y, z=h(x,y)); i=1,...,25) is given for each function. Training-sets consist of 25 pairs, and can be found in our web-page. * Use the following error function for evaluating a function f with respect to a particular training set TS: error(TS):= sum |f(x_i,y_i)-o_i| i=1,..,n (n is the number of input/output pairs, w is the ) * Use roulette-wheel or 3-player-tournament as your selection method * During the development of the system you get two training sets for evaluating and testing your system. * Use crossover, mutation, and copying as your genetic operators. * Fill your initial population by generating 50% trees of height 2, and 25% trees of height 3, and 25% trees of height 4. Generate the variable x or y in 60% of the cases and a constant in 40% of the cases. Binary and unary operators have the same chance to be selected. * Write a brief report has to be written that summarizes the main results of the project, and describes the evolution of your system(2 pages). * Implement a size restricting crossover and mutation operator that reject updates that generate trees whose number exeeds the maximum number of crossover points (which is a constant that is set to 55 in the experiments). * Use a population size of 200 and run your program for 300 generations; or use a population size of 300 and run your program for 200 generations or use a population size of 120 and run it for 500 generations. Observe best-fitness, average size, average-fitness in every run. * Run experiments that try out the following system set-ups for the two benchmarks (repeat each experiment once) a) 50% mutation 50% crossover b) 90% mutation 10% copying c) 90% crossover 10% copying Include a table in your report that summarizes the experiment in your report. 11) MACROS Write a macro cond1 that extents LISP's cond-construct by offering the following additional commands: (continue) := causes that the next condition is evaluated (although the current condition was true). (repeat) := causes that the current condition is reprocessed. (c-return ) := terminates the cond1-conditional. Explain how your macro works. Give two non-trivial examples that demonstrate that your program works correctly!