## COMP 4221 Assignment 1 - Fall 2015

**Fall 2015, COMP 4221 Introduction to Natural Language Processing**

Lecture 1, MW 10:30-11:50, LTF

**Prof. Dekai WU**, Rm 3539,
2358-6989, dekai@cs.ust.hk

**Due:** 2015.11.24 at 23:00 by CASS

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