COMP 3211 Programming Assignment 1 - Spring 2016

Spring 2016, COMP 3211 Introduction to Artificial Intelligence [3-0-1:3]
Lecture 1, MoWe 09:00-10:20, Rm 2304 at L17/18
Prof. Dekai WU, Rm 3539, 2358-6989, dekai@cs.ust.hk

Due: 2016.04.01 at 23:00 by CASS

Assignment page: http://www.cs.ust.hk/~dekai/3211/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

Extend your Scheme function permute from Part 1, to implement a new function anagram that takes an additional argument consisting of a list of symbols representing legal words. Your new function will print all permutations of a given list of any length, such that appending the symbols in the permuted list gives a legal word.

For example:

> (define dictionary '(a act ale at ate cat eat etc tea))
> (anagram dictionary '(a e t))
(a t e)
(e a t)
(t e a)
#f
> (anagram dictionary '(a t c))
(a c t)
(c a t)
#f
> (anagram dictionary '(a))
(a)
#f
> (anagram '() '(a e t))
#f
>

(Hint: You may wish to recall some potentially useful standard functions like symbol->string, string->symbol, string-append, etc.)

Notice that anagram always returns #f. The legal 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).

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: 2016.03.23