CS 63

Artificial Intelligence

HOMEWORK ONE
due 9/15/09

 

*Don't forget to put the statement of sources at the top of your homework! You don't need to cite the McCarthy article.

Part I should be turned in to me in hardcopy on the due date. Part II will be submitted electronically using the handin63 program, as described below.

 

PART I.  What is AI? (35 pts)

READING: Read "What is AI?" by John McCarthy.

ASSIGNMENT:  Describe in your own words what you think AI is all about, and why you decided to take this class. Did your view of AI change after reading McCarthy's paper? Tell me what you think is most interesting or exciting about AI. Describe your own opinion for the ultimate goal of AI and the major challenges of achieving that goal. Real-world applications go a long way to motivating important research. Describe one real-world application that motivates your goal for AI (try to be creative and pick an application that hasn't been mentioned yet in the text and class).

 

PART II.  Lisp Programming (65 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?) I will be testing your code.

Put each of these functions in a single file and submit it for grading using the handin63 program. Details on how to use handin are forthcoming. Be sure to list the problem number in the comments before each function.

 

1. Writing simple functions (5 pts.)

(a)  2pts. Write a function (nextint n) to return the the number that is one more than its integer argument n. For example, (nextint 2) should return 3; (nextint 5) should return 6.

(b) 3pts. 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?) Even though there are more efficient methods, you should use recursion to write this function.

 

2. Operating on lists (25  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) 5 pts. Write the function (scale-by-two l) which takes a list of integers l and returns a list of integers where each element is double the corresponding element in l. Your solution should use a lambda expression. For example, (scale-by-two '(1 2 3 4)) should return (2 4 6 8) and (scale-by-two '(-1 0 1)) should return (-2 0 2).

(c) 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.

UPDATE 2009-09-09: Your posint function only needs to handle single-level lists l to receive full credit; however, I will give you 3 bonus points if your implementation can return a list of all positive integers within nested sublists as well (e.g., (posint '(a 2.3 (-1 (5)) hello 3 (1 2)))) returns (5 3 1 2)).

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

 

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