perm filename PROJ.TXT[1,LMM] blob sn#108391 filedate 1974-06-26 generic text, type T, neo UTF8

CS 206 HANDOUT #20 05-02-74 POSSIBLE PROJECTS Projects come in two flavors: additions and corrections to existing programs, and "new starts." In addition to a source listing and test output, you will be expected to provide a description of what your program/addition/correction does, your method and your reasons for choosing that method. 1. MILISY. A natural language program. MILISY (see HANDOUT #17) is an existing natural language program written in LISP. It accepts simple English language assertions about its "world" (e.g., A RED BLOCK IS ON A TABLE) and answers questions (e.g., WHICH BLOCK IS ON THE TABLE). A suitable project would be to add relative clauses and one other worthwhile addition or correction. See the other handout for details. 2. SPOT. A program which learns structural descriptions by example. SPOT is a learning program, written in LISP, which is similar in concept, though not in sophistication, to P. H. Winston's learning program. The program accepts a named "scene" which is an example of a particular structural type (e.g., ARCH (A B C) (A SUPPORTS C) (B SUPPORTS C) (A BLOCK) (B BLOCK) (C PYRAMID), which is an example of an arch). SPOT may learn more about the "scene" through further examples. After sufficient information has been gathered, it is capable of identifying an unnamed scene as an example of some structure about which it knows. Making SPOT "remember" structures (so that, for example, a VIADUCT could be recognized as several ARCHes) and implementing repeated structures (e.g., a BRICK WALL) would constitute a suitable project. Further information on this project will be available shortly. 3. Program optimization. This is a new project. In "A System Which Automatically Improves Programs" (3rd IJCAI, pp 479-485. on reserve for AI qual), Darlington and Burstall describe a system which optimizes a source program. They present methods for recursion removal, "factoring" of common subexpressions, merging of loops, a (particularly interesting) method of optimizing adjacent calls to the same function, etc. A suitable project entails implementing recursion removal, "factoring" of common subexpressions and either "compound operations" (optimizing adjacent function calls) or merging of loops. 4. MINIT. A mini theorem prover for the propositional calculus. Although this is an existing program (written in MLISP), it is a "high-risk" project. MINIT runs - sort of. Previous projects have attempted to extend it to predicate calculus, and it has a number of interesting (and subtle) bugs which should be corrected. A suitable project would be to make MINIT run correctly and/or implement some of the strategies described in the last chapter of Nilsson. Again, further information will be available in a short time. 5. Polya enumeration. This project involves modifications to an existing INTERLISP program. (Incompatibilities may force a complete rewrite into UCI LISP.) The general problem is to compute the number of different colorings of a set of N objects under symmetry group G contained in Sn, coloring n1 of the objects with color 1, n2 with color 2, ..., nk with color k, where (n1 + n2 + ... + nk) = N. By application of Polya enumeration formula, the number of colorings is the coefficient of x1↑n1 * x2↑n2 * ... * xk↑nk in the cycle index of G. (The cycle index of a group is a polynomial expressed as a sum of products of sums of powers of the xi's.) The existing program will work, given the cycle index in a suitable representation. The project will consist of adding a preprocessor which will compute the cycle index given a group in permutation list form, improving the algorithm by eliminating expansion of terms which will not contribute to the final sum, and possibly writing/rewriting the algorithm so that it counts the number of double cosets (in Sn, given two groups G and H; the above program is a special case of this). (As an alternative to the third part, you might expand it to work on some other application of general Polya enumeration.) Larry will have further details shortly. *************** A possible portion of all projects would be the translation of the program from UCI/AI LISP to INTERLISP. Projects will be due Thursday, May 30.