[CS logo]

CMSC 25000 - Artificial Intelligence
Winter 2007
Assignment #1: Due January 11, 2007

Note: Please include the names of any collaborators in the submitted homework.

Note 2: The chalk site for the course is now up and all registered students have been added. Solutions for this and all other coding assignments should be submitted on-line through the student drop-box for the course. Please refer to the on-line help system for chalk to resolve any difficulties with homework submission.

The goals of this assignment are to refresh your skills with Scheme, and to serve as a diagnostic. Most of the subsequent assignments in this course will require a solid foundation in Scheme programming, such as is required to complete the problems below. If you have trouble with this assignment, you will likely have trouble in the rest of the course as well.

Problem 1:

Implement a simple Scheme program to count the number of atoms in an arbitrary Scheme expression. An atom is anything which does not satisfy the pair? or cons? predicate. The final null () or empty in a list should be counted as a separate atom. For example,

Problem 2:

In this problem you will implement a subroutine required to implement a game of hangman with words of arbitrary length. This problem is taken from How to Design Programs. Exercise 17.6.2; additional details about the hangman game can be found there.

Provide a data definition for representing words of arbitrary length with lists. A letter is represented with the symbols 'a through 'z plus '_.

Develop the function reveal-list. It consumes three arguments:

  1. the chosen word, which is the word that we have to guess;

  2. the status word, which states how much of the word we have guessed so far; and

  3. a letter, which is our current guess.

It produces a new status word, that is, a word that contains ordinary letters and '_. The fields in the new status word are determined by comparing the guess with each pair of letters from the status word and the chosen word:

  1. If the guess is equal to the letter in the chosen word, the guess is the corresponding letter in the new status word.

  2. Otherwise, the new letter is the corresponding letter from the status word.

Test the function with the following examples:

  1. (reveal-list (list 't 'e 'a) (list '_ 'e '_) 'u)

  2. (reveal-list (list 'a 'l 'e) (list 'a '_ '_) 'e)

  3. (reveal-list (list 'a 'l 'l) (list '_ '_ '_) 'l)

First determine what the result should be.