CMSC 671

Artificial Intelligence -- Fall 2003

HOMEWORK ONE
out 8/27/03 due 9/15/02

http://www.cs.umbc.edu/671/fall03/hw/hw1.html



PART I.  What is AI? (14 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. 2) characterize AI approaches by two dimensions: human-like vs. rational/ideal and thinking vs. acting.

Here are seven alternative definitions of artificial intelligence. No one definition is "correct"; they all reflect different perspectives on what AI is, or what is important about AI. Write a short essay of 1/2 to one page summarizing the key differences among these definitions. Be specific.

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)

PART II. AI scavenger hunt (36 pts.)

ASSIGNMENT: You will need to browse around the AI Topics website, http://aaai.org/AITopics/aitopics.html, to answer the following questions. This is a great site produced by AAAI that has a lot of introductory information on artificial intelligence, as well as pointers to many useful resources.

Very Short Answer Questions (2 pts each):

  1. Who said, "Ever since computers were invented, it has been natural to wonder whether they might be able to learn"?
  2. Are genetic algorithms used for (a) planning, (b) learning, (c) creating artificial life forms, or (d) machine vision?
  3. What do you call the evaluation function used by a genetic algorithm?
  4. In July 2002, the Los Angeles Times reported that someone is building an enormous distributed program to play chess. What is this person's name, and what is his system's name?
  5. According to Katie Hafner, how good is the best computer Go player?
    1. Barely as good as a novice player
    2. As good as a casual player
    3. As good as a strong player
    4. Almost as good as the world champion
    5. Able to beat the world champion
  6. Who first introduced the term "robot," and in what year?
  7. What is Isaac Asimov's First Law of Robotics?
  8. Fill in the blank: "Qualitative reasoning is the area of AI which creates representations for __________ aspects of the world." (--Ken Forbus)
  9. Who said, "LISP has jokingly been called `the most intelligent way to misuse a computer.' I think that description is a great compliment because it transmits the full flavor of liberation: it has assisted a number of our most gifted fellow humans in thinking previously impossible thoughts," and in what year?
  10. Who first invented the term "artificial intelligence," and when?
Short Answer Questions (4 pts each): (Note that there are no right answers to these questions, only more and less coherent and complete discussions! Your answers should not be more than a couple of sentences each.)
  1. What's the difference between cognitive science and AI?
  2. What's an ontology?
  3. What's an agent?
  4. List three interesting facts you learned from the AI Topics website.

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 #1(a), what happens if the argument isn't a list? What if it is a list, but k > 0 or k < (length l)?)

1. Operating on lists (20 pts.)

(a) 10 pts. Write the function (nth k l) that returns the kth element of the list l. Do not use the built-in function (nth). You may define this function either recursively or iteratively.

(b) 10 pts. The function (pos-numbers l) should take a list l and return a list containing only the positive numbers at the top level of the list. For example, (pos-numbers '(.3 -1 0 (a) symbol 2 (3 4)) should return (.3 2). Your solution should use mapcar or a related construct, such as mapcan, and should be order-preserving.

3. Conditionals and strings (15 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 (or if the string contains any non-letter characters). 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 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-tree '(((1) 2) ((3 (4)) 5) 6)) should return (1 2 3 4 5 6).