COMP 221 Assignment 1 - Fall 2010

Fall 2010, COMP 221 Fundamentals of Artificial Intelligence [3-1-0:3]
Lecture 1, TuTh 15:00-16:20, Rm 5583
Prof. Dekai WU, Rm 3539, 2358-6989, dekai@cs.ust.hk

Due: 2010.10.08 at 23:00 by CASS

Assignment page: http://www.cs.ust.hk/~dekai/221/assignments/a1.html

Part 1

Implement a Scheme function permute to print all permutations of a given list of any length.

For example:

> (permute '(a e d))
(a e d)
(a d e)
(e a d)
(e d a)
(d a e)
(d e a)
#f
> (permute '())
#f
> (permute '(a))
(a)
#f
>

Notice that permute always returns #f. The permutations must be displayed to standard output, not returned. This is to avoid building enormous lists in memory (consider how many permutations there are of a list of length 10).

Part 2

Implement a Scheme function to compute path lengths (distances) in weighted directed graphs.

Scheme/Lisp lists, or s-expressions, give us a very easy way to represent a directed graphs. We'll use the association list convention here (but in general, you could also use other simple conventions).

We'll do the following to represent a weighted graph using incidence lists. A graph is an association list of (nodename . out-edges) pairs. Each nodename is just any unique symbol that identifies a node. Each out-edge is another association list of incident outgoing-edges, each of which is represented by a (destination-nodename . weight) pair. Each destination-nodename is a symbol that identifies the destination node. Each weight is a number.

For example:

(define g
  '((a . ((b . 5) (c . 8) (d . 3)))
   (b . ((a . 4) (c . 7)))
   (c . ((a . 2) (b . 6) (c . 2) (d . 9)))
   (d . ((b . 1) (c . 4)))))

We'll use weights that are positive integers representing the length or distance between any two points.

Write a function path-length that calculates the total sum of weights along any given path represented as a list of nodenames. Also write a convenient variation distance that lets you pass paths as a variable number of nodename arguments.

For example:

> (path-length g '(a c d b c))
25
> (distance g 'a 'c 'd 'b 'c)
25
> (distance g 'c 'c)
2
> (distance g 'd 'a)
#f

Notice that cycles are allowed, and distance must return #f if the path does not exist in the graph.

Important reminders

Your final submitted version must run on the version of Chicken Scheme in Lab 2. You may only use any SRFIs that were taught in lecture.

Place your entire assignment in one well-organized and documented file named a1.scm.

Your proper software engineering skills are being graded. Your programming style (how clearly and how well you speak Scheme) is what will be graded. Correct functioning of your program is necessary but not sufficient!

You must write the final version of the program on your own. Sophisticated plagiarism detection systems are in operation, and they are pretty good at catching copying! If you worked in study groups, you must also acknowledge your collaborators in the write-up for each problem, whether or not they are classmates. Other cases will be dealt with as plagiarism. Re-read the policy on the course home page, and note the University's tougher policy this year regarding cheating.

---

dekai@cs.ust.hk
Last updated: 2010.09.30