CMSC 471

Artificial Intelligence -- Spring 2014

HOMEWORK ONE
out Tuesday 1/28/14, due Tuesday 2/18/14 Thursday 2/13/14

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

All parts must be submitted as hardcopy at the beginning of class on Thursday, February 13.

Please submit Parts I and II together.

Please submit Part III as a separate hardcopy. (Be sure your name is on both Parts I/II and on Part III!)

Part III (Lisp Programming) should be prepared as a single Lisp file, named "hw1.lisp". This Lisp file must be printed and submitted in hardcopy and must also be submitted online using the submit facility on the gl machines, using the project "hw1" (lower case): submit cmsc471 hw1 hw1.lisp

PART I. What is AI? (20 pts)

READING: Read John McCarthy's paper, "What is AI? (http://innovation.it.uts.edu.au/projectjmc/articles/whatisai/whatisai.pdf)"

ASSIGNMENT: Answer the following questions in a short essay (1 - 2 pages but if you want to write more, that's fine too):

What did you think "artificial intelligence" was about before reading this paper? Did the paper change your mind?
Does McCarthy see the primary goal of AI as modeling human intelligence?
Does McCarthy think that this goal is achievable? Why or why not?
Do you agree with McCarthy's views on what the primary goal of AI should be, and whether it is achievable?
Summarize some of the key challenges in achieving human-level intelligence.

PART II. Why Lisp? (10 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.

PART III. Lisp Programming (70 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, (twoless 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 (45 pts.)

(a) 5 pts. Write the function (my-third l) which returns the third element of the list l. Use only car and cdr (i.e., you may not use built-in functions like third or caddr).

(b) 15 pts. 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. All three implementations should be recursive. Your solutions should not call flatten-list() (see #4) or a similar function to flatten the list before extracting the positive integers -- the posint functions should only "walk through" the lists ONCE, collecting the positive integers WITHOUT calling other helper functions. Calling flatten-list() defeats the intention of this exercise.

Implement posint1, a version of the posint function using mapcar or another built-in map function such as mapcan.
Implement posint2, a version of the posint function using the loop macro.
Implement posint3, a version of the posint function that operates recursively but does not use mapcar or any other built-in map function or loop.

For extra credit (5 pts), you may also implement posint4, a version of the posint that is not recursive. This is actually much harder because of the arbitrary nesting. My solution uses the loop macro and a local variable to build up the answer. I found it rather tricky to write.

3. Flattening a nested list (15 pts.)

Write a function (flatten-list l) that takes an arbitrarily deeply nested list of atoms (possibly including dotted pairs), 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).