CMSC 471

Artificial Intelligence -- Fall 2009

HOMEWORK ONE
out 9/1/09 due 9/15/09

http://www.cs.umbc.edu/courses/undergraduate/471/fall09/hw/hw1.html


Pretest (10 pts.)

You will receive 10 points of extra credit towards this homework for turning in a completed pretest on time (regardless of your score on the pretest).

PART I.  What is AI? (20 pts)

READING: Read John McCarthy's paper, "What is AI? (http://www-formal.stanford.edu/jmc/whatisai.html)"

ASSIGNMENT:  Does McCarthy see the primary goal of AI as modeling human intelligence?  Does he think that this goal is achievable?  Why or why not?  Summarize some of the key challenges in achieving human-level intelligence.

PART II. Why Lisp? (20 pts.)

READING:  Read the article "Beating the Averages" by Paul Graham.

ASSIGNMENT:  Describe three of the key features of Lisp that, according to Graham, make it a good language for developing applications. Explain what Graham means when he says that "Lisp has no syntax."

PART III.  Lisp Programming (60 pts.)

ASSIGNMENT: These problems are intended to help you become familiar with the basic programming concepts in the Lisp language. Documentation and error checking are essential in this class, so although these problems are simple, your code must be documented, and error cases must be handled.  (For example, in problem #2, what happens if the argument isn't a list? What if it is a list, but is less than three elements long?)

1. Writing simple functions (10 pts.)

(a) 5 pts. Write a function (lesstwo n) to return the the number that is two less than its integer argument n. For example, (lesstwo 2) should return 0; (lesstwo 5) should return 3.

(b) 5 pts. Write a function (fact n) to return the factorial of the argument n.  (The factorial of an integer is the product of all integers from 1 to that integer.) For example, (fact 3) should return 6; (fact 10) should return 3628800. (What do you think (fact 'hello) should return?) You should use recursion to write this function.

2. Operating on lists (35  pts.)

(a) 5 pts. Write the function (my-third l) which returns the third element of the list l. Do not use the built-in function (third). You can define this function either recursively or non-recursively.

(b) 10 pts each. There are often many different ways to solve the same problem in Lisp. In this problem, you will need to use your creativity and knowledge of Lisp functions to write the same function in several different ways. The function (posint l) should take a list l and return a list containing only the positive integers in the list. For example, (posint '(a 2.3 -1 5 hello 3 (1 2)))) should return (5 3 1 2). You can use the built-in function integerp in your solutions.

  1. Implement the posint function using mapcar.
  2. Implement the posint function using the loop macro.
  3. Implement the posint function recursively.

3. Flattening a nested list (15 pts.)

Write a function (flatten-list l) that takes an arbitrarily deeply nested list of atoms, and returns a flattened list of these atoms (in the same order they appear in the original list). For example, (flatten-list '(((1) 2) ((3 (4)) 5) 6)) should return (1 2 3 4 5 6).