Assignments
CSE 415: Introduction to Artificial Intelligence
The University of Washington, Seattle, Spring 2002
Assignment 1: Log into INFACT-FORUM, using your UW C and C general access account name as your username, and your student number as your password. Read the message named "Intelligence for the Husky Helper". Post your own personal answer to this question. Deadline: Tuesday, April 2 at noon. After that deadline has passed, you'll be able to see the answers of other people in your group. Work online with your group discussing the pros and cons of different people's ideas, and come up with a group-consensus solution by Friday at 5:00 PM.
Also, read Chapter 1 in The Elements of Artificial Intelligence Using Common Lisp


Assignment 2: The reading for this week is Chapter 2 in The Elements of Artificial Intelligence Using Common Lisp.
Part A. Do exercises 1 through 4 on page 87. Post your answers on INFACT-FORUM as a reply to the message, "Assignment 2, Part A." When doing exercise 4, you may assume that the argument list does not have any sublists, and so a one-way recursion will suffice.
It's recommended that you complete Part A before Part B, which has an initial post deadline of Tuesday at noon. However, there will not be a points penalty until Friday.
Part B. Using INFACT-FORUM, do the following. As a group, write Lisp function definitions for all four* of the following requirements. For your individual post, due Tuesday at noon, choose any two, describe an implementation strategy, and give definitions of them.

1. (times-3-list '(2 5 1.5 100))  ->  (6 15 4.5 300)

2. (3-times-list '(2 5 fun yes))  ->  (2 2 2 5 5 5 FUN FUN FUN YES YES YES)

3. (parenthesize-each '(a b 2 3)) ->  ((A)(B)(2)(3))

4. (nest-deeply '(a b 2 3))       ->  (A (B (2 (3))))
By the end of the week, provide two different solutions for each of the functions, and discuss their pros and cons.
Provide your individual posting by replying to this message.
The group solutions are due on INFACT-FORUM on Friday, April 12, at 5:00 PM.
*If your group has fewer than four active contributors, then you only have to turn in solutions for any three of the functions.


Assignment 3: The reading for this week consists of portions of Chapter 3 in The Elements of Artificial Intelligence Using Common Lisp. Read pages 93-99, look over pages 100-107, and read pages 108-113.
Part A. Do exercise 2 on page 131. Post your answer on INFACT-FORUM, using CSE 415 (Sp'02 Forum B), as a reply to the message, "Assignment 3, Part A."
It's recommended that you complete Part A before Part B, which has an initial post deadline of Tuesday at noon. However, there will not be a points penalty until Friday.
Part B. Using INFACT-FORUM, do the following. As a group, take the SHRINK.CL code and modify it to create a program that simulates some specific person, type of person, or other conversational agent. For your individual post, due Tuesday at noon, choose any two of the following features, describe an implementation strategy, and give the new code needed to make these features work with the SHRINK program.

  • The agent will have a special response to user sentences that mention LISP, ARTIFICIAL INTELLIGENCE, or AI.
  • The agent will have the "memory" capability described in Exercise 10 on page 132 of the text.
  • The agent will be able to answer the questions "WHAT", "WHAT?", "WHAT DID YOU SAY?", "HOWS THAT?" by first outputting "I SAID " and then printing its previous output again.
  • The agent will respond to any sentence containing a number by saying "I DONT UNDERSTAND NUMBERS".

  • Provide your individual posting by replying to the Assignment 3 Part B message.
    The group solutions are due on INFACT-FORUM on Saturday, April 20, at 7:00 PM. (Note this is a change!)
    There should be three final postings for your group: one with subject "Assignment 3B: Final Design", another with subject "Assignment 3B: Final Sample Session", and a third with subject "Assignment 3B: Final Code". The design should include a description of the character being simulated, an explanation of each of the key features, an explanation of the Lisp code used to implement each of those features, and an indication of which group members were responsible for each feature.


    Assignment 4: The reading for this week consists of approximately the first half of Chapter 4 in The Elements of Artificial Intelligence Using Common Lisp. Read pages 135-160.
    Part A. Do exercises 1-4 on page 194. Post your answers on INFACT-FORUM, using CSE 415 (Sp'02 Forum B), as a reply to the message, "Assignment 4, Part A."
    It's recommended that you complete Part A before Part B, which has an initial post deadline of Tuesday at noon. However, there will not be a points penalty until Friday.
    Part B. Using INFACT-FORUM, do the following. For your individual post, due Tuesday, April 23 at noon, first answer exercise 14 on page 197. Also for your individual post, choose either exercise 9, 10, or 11, and explain how you could make the new feature(s) work (but don't implement anything yet). As a group, do two things. First, discuss the answers that were given by your group members (in the initial posts) to exercise 14. Then come up with a summary statement that reviews the differences in your answers and proposes a best, final answer. The second thing to do is to choose, as a group, either exercise 9, 10, or 11, and implement the feature(s) by extending the LINNEUS.CL program. As in assignment 3, make three final posts, with one for design, one for sample session, and one for the source code (with comments describing the new parts). Explain which group member(s) worked on each feature. Provide your individual posting by replying to the Assignment 4 Part B message.
    The group solutions are due on INFACT-FORUM on Friday, April 26, at 5:00 PM.


    Assignment 5: The reading for this week consists of part of Chapter 4 and approximately the first half of Chapter 6 in The Elements of Artificial Intelligence Using Common Lisp. Read pages 160-168 and 271-292. Also read pages 302-312 to get familiar with Horn clauses and how Prolog-style resolution works.
    Part A. Do exercises 15a (i-iv) and 17 on pages 197-198. Also do exercise 15 on page 326. Post your answers on INFACT-FORUM, using CSE 415 (Sp'02 Forum B), as a reply to the message, "Assignment 5, Part A."
    It's recommended that you most of Part A before Part B, which has an initial post deadline of Tuesday at midnight. However, there will not be a points penalty until Sunday.
    Part B. Using INFACT-FORUM, do the following. For your individual post, due Tuesday, April 30 at midnight, choose a restaurant, store, or club, list 3 facts about it, and encode them in the predicate calculus. At least one of your formulas should include a universal quantifier and an implication, and at least one should include an existential quantifier. Also make a restaurant, shop, or club suggestion to the rest of your group.

    As a group, do problem 26 on page 328. This problem has two parts. In Part a, you are to develop a list of Horn clauses that provide knowledge about a collection of restaurants or other entertainment venues. With this knowledge, it should be possible to state some facts about a particular need, such as to take a vegetarian guest out for dinner at a quiet place that charges under $12 per person for the entrees. The example Horn clauses on page 305 with Lisp encodings on pages 311-312 give an idea of what some of your Horn clauses might look. Basically you are to come up with the knowledge for something like a restaurant advisor, and you need to express that knowledge in Horn-clause form. In Part b, you'll use the Lisp program called PROLOG.CL, with you own minor modifications, to make your restaurant advisor (or bar advisor or whatever) really work.

    As in assignment 4, make three final posts, with one for design, one for sample session, and one for the source code (with comments describing the new parts). Explain which group member(s) worked on each feature. Provide your individual posting by replying to the Assignment 5 Part B message.
    The group solutions are due on INFACT-FORUM on Sunday, May 5, at midnight.


    Assignment 6: The reading for this week consists of most of Chapter 5 in The Elements of Artificial Intelligence Using Common Lisp. Read pages 201-250.

    Individual Posts Due Wednesday, May 8, at midnight. Choose one of the following puzzles and describe a state space for it. Give the form of each state, the initial state and describe a predicate Goal(s) that will return True if s is a goal state. Describe how each kind of legal move transforms a state.

    The puzzle options are:
    (1) Equilibrium puzzle given in the text on p.264.
    (2) The N-queens puzzle on a given m by m chessboard containing "forbidden squares." (A forbidden square is one where a queen is not allowed to be put; however, queens can still attack through forbidden squares.)
    (3) The missionaries and cannibals puzzle (described in Exercise 10, p.263).
    (4) Just added, by request: Towers of Hanoi (described in Exercise 11, p.265).

    Post your answers on INFACT-FORUM, using CSE 415 (Sp'02 Forum B), as a reply to the message, "Assignment 6".

    Group Work. Critiques: Using INFACT-FORUM, each group member should post a critique of at least one other person's state-space formulation. It should be for a different puzzle than that of the critiquer. The critique should identify at least one strength and one possible weakness of the proposed formulation and propose a fix.

    Programming: Each team is responsible for four working programs. However, the programs should share code for state-space search. Each team member should take responsibility for one of the four programs. There should be one program for each of the three types of puzzles listed in Part A, and there should also be a program solving the Towers of Hanoi puzzle. The common state-space search code should provide both depth-first and breadth-first search options. Each team member should make two separate final posts. One should contain a description of the design, and a sample session. The other should contain the source code. The shared portion of the code should be clearly marked with comments.

    Provide your individual posting by replying to the Assignment 6 Part B message.
    The programs are due on INFACT-FORUM on Sunday, May 12, at midnight.


    Projects: Information about the projects is available on a separate page.