CMSC 671

Artificial Intelligence -- Fall 2001

HOMEWORK ONE
out 8/30/01 due 9/11/01

http://www.cs.umbc.edu/671/Fall01/hw1.shtml



PART I.  What is AI? (30 pts.)

READING: Read Chapter 1 of Russell & Norvig and John McCarthy's paper, "What is AI? (http://www-formal.stanford.edu/jmc/whatisai.html)"

ASSIGNMENT: R&N (p. 5) characterize AI approaches by two dimensions: human-like vs. rational/ideal and thinking vs. behaving.

(a) 15 pts. Two additional dimensions for characterizing AI systems and methods are theoretical vs. practical and "strong AI" (consciousness as an objective) vs. "weak AI" (makes no claims about whether systems are self-aware). Characterize the eight definitions on page 5 of R&N and the seven following definitions according to these four dimensions. Some definitions may be neutral with respect to a particular dimension, or fall in the middle of a continuum. Credit will be given for well thought out explanations, even if your answer disagrees with the "official" answer, so you are encouraged to state your reasons.

Artificial intelligence is...
  1. "a collection of algorithms that are computationally tractable, adequate approximations of intractably specified problems" (Partridge, 1991)
  2. "the enterprise of constructing a physical symbol system that can reliably pass the Turing Test" (Ginsberg, 1993)
  3. "the field of computer science that studies how machines can be made to act intelligently" (Jackson, 1986)
  4. "a field of study that encompasses computational techniques for performing tasks that apparently require intelligence when performed by humans" (Tanimoto, 1990)
  5. "a very general investigation of the nature of intelligence and the principles and mechanisms required for understanding or repicating it" (Sharples et al., 1989)
  6. "the getting of computers to do things that seem to be intelligent" (Rowe, 1988)
(b) 15 pts. Where along these dimensions would you characterize your own interests?  That is, in the four-dimensional space defined by these four dimensions, what point, line, plane, or region do you fall into? Write an essay of 200 words (or more) discussing your perception of what's interesting and exciting about AI, and where in this space your interests lie.

PART II. What is Lisp? (20 pts.)

READING: Read Chapter 1 of Norvig and the article by Paul Graham, "Beating the Averages" (http://www.paulgraham.com/paulgraham/avg.html)

ASSIGNMENT: Give five reasons why Lisp is a cool language (besides the fact that you have to learn it for this course). Compare Lisp's basic constructs and the Lisp programming methodology to two other programming langauges/environments with which you are familiar. How are they similar? How are they different? What problems might be easier (or more difficult!) to solve in Lisp?

PART III.  Lisp introduction (50 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 (5 pts.)

(a)  Write a function (square n) to return the square of its argument n. For example, (square 2) should return 4; (square .5) should return .25.

(b) 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 (20 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 iteratively.

(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 (all-odds l) should take a list l of integers and returns a list containing only the odd integers in the list. For example, (all-odds '(1 2 3 4 5 6 7 8 9 10)) should return (1 3 5 7 9). You can use the built-in function oddp in your solutions.

Find (and turn in) at least three distinctly different ways to implement the all-odds function. At least one of the implementations should use mapcar or a related construct, such as mapcan. (Hint: try looking at the built-in functions dolist, do, cond, and loop.)

3. Conditionals and strings (10 pts.)

Write a function (case? s) that returns the symbol 'upper if the characters in the string s are all upper case, 'lower if the characters are all lower case, and 'mixed if there are some lower case and some upper case letters. Hint: first write two subroutines, upper? that tests to see if a string is upper case and lower? that tests to see if a string is lower case. Then use cond with these subroutines to test for which case to return. Useful built-in functions for solving this problem include char, upper-case-p, and lower-case-p.
 

4. Flattening a tree (15 pts.)

Write a function (flatten-tree 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-tree '(((1) 2) ((3 (4)) 5) 6)) should return (1 2 3 4 5 6).