**Due date:** Thu 4/17 11:00 pm

val A = [[1,2,3],[3,4,5],[3,1,1]]; val B = [[1,2,3,5],[5,3,4,5],[5,3,1,1],[5,3,1,1]]; val C = [[1,2,3,5],[5,3,4,5],[5,3,1,1]]; A corresponds to B corresponds to C corresponds to [ 1 2 3 ] [ 1 2 3 5 ] [ 1 2 3 5 ] [ 3 4 5 ] [ 5 3 4 5 ] [ 5 3 4 5 ] [ 3 1 1 ] [ 5 3 1 1 ] [ 5 3 1 1 ] [ 5 3 1 1 ]

- Write a function
`transpose: 'a list list -> 'a list list`whose input is a matrix and whose output is the transpose of the matrix where columns of the original matrix become the rows of the output matrix. For example`transpose(A)`returns`[[1,3,3],[2,4,1],[3,5,1]]`.You may use any number of helper functions in this part. You must use some higher order functions (such as

`map or foldl`or your own functions) in the implementation. Code using direct iteration without higher order functions will not obtain full credit. - Recall that when calculating a matrix product
`M1 x M2`each element of the resulting matrix is a dot product of a row in`M1`with a column in`M2`where a dot product is a sum of products of the corresponding elements. For example if we are calculating`A x A`then the element in the second column of the first row in the result is equal to the dot product of`[1,2,3]`and`[2,4,1]`and therefore has the value . Similarly the entry is equal to the dot product of the 'th row of`M1`and 'th column of`M2`. For exampleA x A is equal to A x C is equal to [ 16 13 16 ] [ 26 17 14 18] [ 30 27 34 ] [ 48 33 30 40] [ 9 11 15 ] [ 13 12 14 21]

Write a function

`MM : int list list * int list list -> int list list`that calculates matrix multiplication.You may use any number of helper functions in this part. You must use some higher order functions (such as

`map or foldl`or your own functions) in the implementation. Code using direct iteration without higher order functions will not obtain full credit.

- To start Prolog type:
`pl`at the unix prompt. This will get you to the Prolog prompt. - To load the contents of a file named
`myfile.pl`use`[myfile]`at the Prolog prompt. After that you can start typing in queries. Remember that every query must end with a fullstop. - If the query is a Yes/No query you will get the answer and get back to the prompt.
- If the query requests an answer binding (that is, it has a variable for
which bindings are sought) then you may get the answer No or you may
get a binding as an answer. If you then press
`[Enter]`you will get back to the prompt. To get additional answers press`;`(a semicolon). - Note that you have a history mechanism just like in the unix shell. Press up-arrow to get previous commands and then edit them.
- To start tracing use
`trace.`This will trace the next query that you ask. Pressing`[space]`will take the run one step at a time. - If the system appears stuck or in a funny state
`CTRL-C`will normally rescue you; if followed by`a`(for abort) you will return to the Prolog prompt. - To exit the Prolog system use
`CTRL-D`or`halt.`

- Use the file
`db1.pl`(from class examples) and write queries to extract information from the database as follows. (NB use the database predicates only -- do not use the rules in`db1-rules.pl`.) Write expressions for queries that:- Check whether eric is enrolled in comp1b.
- Find a student who is enrolled for comp2b (if one exists).
- Check whether justin and janet are classmates.
- Find a course which is taken by daniel and which has a prerequisite (if one exists).
- Find three different courses which daniel is taking (if they exist). Note: here a single answer to the query must have the list of three courses as output. These courses must be distinct.

- Write one or more rules defining the predicate
`hereOnTue(Student)`. The predicate identifies students who are taking classes on Tuesdays. Your programs should work for`db1.pl`and any other database in the same format (note the lower case encoding of Tuesday in`db1.pl`). - Write one or more rules defining the predicate
`everyday(Student)`. The predicate identifies students who are taking classes on Mondays, Tuesdays, Wednesdays, and Thursdays. Your programs should work for`db1.pl`and any other database in the same format. - Write one or more rules defining the predicate
`deep(Course)`. The predicate identifies courses that require a sequence of at least two courses to be taken before them. In`db1.pl`the only course that satisfies this predicate is`comp3b`. - For this part please refer to the code for binary search trees in
`usingterms.pl`. Write one or more rules defining the predicate`range(Tree,Value)`. The predicate is true when value is the difference between the maximum value in the tree and the minimum value in the tree. For the example tree in the file this value is .You may want to first write rules calculating the minimum and maximum of the tree and then write a rule to calculate the range.

The Prolog files are available through the class examples section of the course web page.

Your code for the ML section
should be in a file `pp5.sml`,
the code for the Prolog section in `pp5.pl`.

Assuming your files are in
the current directory on one of our Sun workstations or servers,
you should submit by typing
`provide comp80 pp5 pp5.pl pp5.sml`

This document was generated using the
**LaTeX**2`HTML` translator Version 2002-2-1 (1.70)

Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.

Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.

The command line arguments were:

**latex2html** `-split 0 -no_navigation -no_images -dir TEMPHTML pp5.tex`

The translation was initiated by Roni Khardon on 2008-04-08

Roni Khardon 2008-04-08