(10 points) Problem 1: Basic Search Strategies
(10 points) Problem 2: Search
(10 points) Problem 3: Search
(20 points) Problem 4: Constraint Satisfaction
(20 points) Problem 5: Constraint Satisfaction
(6 Points each) Problem 6 to 10: Lisp
Assume you have the following search space.
| STATE | NEXT-STATE | COST |
| A | B | 4 |
| A | C | 1 |
| B | D | 3 |
| B | E | 8 |
| C | C | 0 |
| C | D | 2 |
| C | F | 6 |
| D | C | 2 |
| D | E | 4 |
| E | G | 2 |
| F | G | 8 |
Task 1: Draw this search space as a directed graph (i.e., states are nodes and actions are directed arcs, labeled with their costs).
Task 2: For each of the following, during each cycle of the search algorithm: report which node is expanded, and the content of the queue. Also report the solution path found.
Problem 3: AIMA 3.11 (in pseudo code).
Problem 4: Constraint Satisfaction
(Courtesy of Djamila-Haroud, Swiss Federal Institute of Technology)
Three employees in a small company, Alice, Rob and Ian must contact
their respective customers as quickly as possible. The company has
one telephone, one fax and one computer (for email), with independent lines.
Alice needs to contact two customers: one who only has a telephone and
the second one has both a telephone and a fax. Rob must contact a
customer who has also has a telephone and a fax. Ian's customer can
be reached by fax or by computer. Suppose that Alice contacts her
customers the one after the other while, during the same time, Rob
and Ian are communicating with their customers.
Task 2: Write a second function extremities2 that returns the same result without using let.
Problem 7: conditional instruction cond
COND can be thought as a generalization of a sequence of the IF.. THEN..
ELSE statements: CONS allows us to express a set of alternatives
Task 1: Write a function traffic-light to represent the behavior of a driver. The function takes two arguments: the first one is the state of the traffic light (red, yellow, green) and the second parameter is a Boolean stating whether there is a camera or not at the traffic light (common in Europe!). This function must return the atom:
Task 2: Write a second function traffic-light-or
using or.
Problem 8: list processing using dolist
Write a function count-elements that takes two arguments: a
list of numbers and a number (bound) and that returns a list of two numbers:
the first of which is the number of elements in the list that are strictly
less than the bound and the second the number of elements greater than
or equal to the bound. Scroll through the list using dolist.
Hint: use let to store intermediate results.
Problem 9: conditional instructions with when et unless
The goal is to write a function that returns the list of squares of
the elements of a list given as argument without using any loops.
Task 1: Write a recursive function list-squarres-unless
using unless to test if the end of the list has been reached.
Task 2: Write a second recursive functions list-squares-when
using when to test if the end of the list has been reached
Hint: use cons in both cases.
Problem 10: general loop instruction do
Although there is a LISP function to compute exponential (i.e.,
expt), you are asked to write a function my-expt that
computes exponential given a number and a positive integer exponent, using
the lisp loop construct: do.
Example:
(my-expt 2 4)
-> 16