Velin K TzanovExample 4:6.871 Term Project Report Velin K Tzanov 1. Motivation and Problem Statement If we can help Math students learn how to integrate, by creating a knowledge-based system that does integration for them (and shows them how it did it), why can’t we do the same with Computer Science students and dynamic programming (and possibly other algorithmic techniques)? Inspired by this question, I decided to design and implement a system that would take the description of an algorithmic problem and construct a solution (algorithm) for it. Here are three examples of such problems: Example 1: You are given a sequence of N numbers and an integer K. Find a split of this sequence into K sub-sequences of consecutive numbers, so that the product of the sums of the numbers in the groups is maximized. Example 2: You are given N cylinders and each one has specified height, weight and base radius. You can use those cylinders to build a tower, by placing them one over another. In doing that you have to keep in mind that a heavier cylinder cannot stand over a lighter one and that a larger (by base radius) cylinder cannot stand over a smaller one. What’s the highest tower you can build, using the given set of N cylinders? Example 3: You are given the numbers from 1 to N and an integer P between 1 and N. The g-number of a sequence is defined as the number of monotonically decreasing sub-sequences in that sequence. For example in 5 2 4 9 7 3 1 10 8 6 the g-number is 4 (the monotonically decreasing sub-sequences are (5 2) (4) (9 7 3 1) (10 8 6). Find the number of permutations of the numbers from 1 to N that have a g-number equal to P. 2. Input Language In order to describe the problem statements to my program, I had to create a simple, yet powerful language that could be used in my input files. Of course, ideally such a program would read the problem statements in natural language, but that is a really hard task, as we know. That is why I came up with a very simplified object-oriented language, inspired by Minsky’s frames and the C/C++ struct keyword. In this language we have three types of entities: primitive variables types, collections and structures. Primitive variable types are things like integers and floating point numbers. In the current version of the language there is only one primitive type: INT. Collections are simplygroups of objects of the same type (either a primitive type, or a structure). At the moment I have two type types of collections: SET and SEQUENCE. The difference is that the latter is ordered, while the first one doesn’t have any notion about order (which doesn’t mean that you can’t take its elements and arrange them in some order later). Structures on the other hand are completely user-defined. They, similarly to the structs in C/C++ are collections of objects, which can be of different types (primitive types or collections). The main difference with the collections described above (besides the fact that you can have different types of items) is that you have only a finite number of items, while in SETs and SEQUENCEs you have an unbounded number in items (i.e. you specify the type of the items and that’s it, while in the structures you enumerate and name the items one by one). Here is an example of the definition of collections and structures for example problem 2 described above: STRUCT CYL INT HEIGHT INT WEIGHT INT BRAD STRUCT TOWER SET CYL POOL SEQUENCE CYL CHOSEN INT HEIGHT The first line defines CYL as a structure that has an integer HEIGHT, an integer WEIGHT and an integer BRAD. The second line defines TOWER as a structure that has a set of CYLs called POOL, a sequence of CYLs called CHOSEN and an integer HEIGHT. In addition to that we can specify relations between the items in a structure using the EQUATE command. It takes the structure name as its first argument and then it takes the name of one of its items. The next argument is an operation that is performed on the following arguments, which are also items from the structure. For example if we want to make item DEBT of a structure ACCOUNT equal to the sum of all items in the PAYMENTS collection of ACCOUNT, we include the following line: EQUATE ACCOUNT DEBT SUM PAYMENTS In order to make the language more flexible we also have the FIELD keyword that can be used when describing an item. It means that we are not interested in the item whose name follows, but rather in an item of that item. Hence the parser looks for another name after the following name. Also, we have the ELEMENT keyword, which stands for an element of a collection (remember, items in collections are nameless because they are unbounded in number). This element is an abstract notion of an element in this group, not any particular element. Here is an illustration of these two keywords, which tells us that the height of a tower is equal to the sum of the heights of the cylinders in its chosen set: EQUATE TOWER HEIGHT SUM FIELD CHOSEN FIELD ELEMENT HEIGHT Finally, our language has commands that tell the program what objects are given to us and what objects are we trying to compute. There are the GIVEN command and the FIND / HAVING pair, which are illustrated below, again in the context of the tower of cylinders example: GIVEN SET CYL INP FIND TOWER POOL INP HAVING MAX HEIGHTIn addition to those, my initial version of the language had means to define functions, so that things like the g-number from example problem 3 above could be described. Reading and understanding those language constructs was never implemented however (for reasons explained in section 4 below), so I will just give a quick example of this feature, without much explanation. It simply says that we add 1 to G every time an item in the BOARDS sequence is higher than the previous item (something that people usually write as G(X) = G(X-1) + (BOARDS(X) < BOARDS(X-1)) ) EQUATE FENCE G RECURSIVE BOARDS ADD G -1 SMALLER ELEMENT -1 ELEMENT 0 This language seems to be powerful enough for the problems I tried my system on, though I have to admit that often it’s not trivial to convert a problem statement into an input file. Nevertheless, it’s almost always possible to do that and that was the goal of this project (ideally we would use natural language processing, but unfortunately we don’t have this available yet). 3. System Architecture Having this object-oriented input representation, the most natural way to organize the state of the program is