CMSC 671: Introduction to Artificial Intelligence
Fall 2010

Home News Schedule Homework Grading Useful Links Final Project

Homeworks can be submited by email or in paper to Prof. Zavala after the class.
If emailed, please send them to

Extensions and late homework penalty

A penalty for late homework will be applied as follows:
Download the pdf file for the pretest from here.

You may use written reference materials. You may not work on or discuss the pretest with anyone else. This pretest will be graded for your information (and mine), but will not count towards your final course grade, nor will it make any difference on how you are evaluated on your tests and assignments. The primary intent is for you to identify prerequisite material that you are expected to know for CMSC 671. If you have trouble with this pretest, you may want to put in some time now reviewing basic concepts.

The pretest is due on Tue, Sep. 7. Submit by email or bring it printed to the class.
Homework 1 (due Sat, Sep. 18)

Problem 1, 20 points

Russell & Norvig, exercise 3.11 (page 115)

Problem 2, 20 points

Russell & Norvig, exercise 3.12 (page 115)

Problem 3, 60 points: 15 points for (a); 15 points for (c); 30 points for (b)

Russell & Norvig, exercise 3.9 (page 115) For the implementation (b) part, solutions are expected in Lisp, Python, or any other functional programming language. Implementations in a non functional programming language will be given 50% credit (15 points).
You need to submit your code as well as a Readme file explaining your solution and how to run it.

Problem 4, 10 points

You can choose one of the following two tasks to get 10 extra points for Homework 1

Check the Introduction and Section 1 (Turing (1950) and the Imitation Game) of Turing Test.
Write a 200-400 word discussion reflecting your opinion about the points discussed in section 5: The Turing Test is Too Hard; The Turing Test is Too Narrow; The Turing Test is Too Easy; Should the Turing Test be Considered Harmful?

Choose one of the papers from the following list and write a 200-400 word summary of the main points in your chosen paper:

The homework is due on Sat, Sep. 18. Submit by email ( or bring it printed to the class.

Homework 2 (due Sat, Oct. 16, midnigth)

Note: You have to submit the homework by the deadline to Additionally, you have to bring me a printed copy of your report (and the extra credit problem if submitting) to class on Tue, Oct. 19.

In this assignment, we'll explore the search space of the game Sudoku. I've provided some Lisp infrastructure (data structures, basic variables, and some helpful macros and functions). You do not have to use the code I have provided, as long as you provide working Lisp code with the specified functionality.

VERY IMPORTANT: You need to pace yourself with this assignment. You have three weeks, in order to give you some flexibility in managing your time and designing your software. I strongly suggest that you use this time wisely. For example, you may want to allocate the first week to implementing the basic form of the search algorithnm, which should be able to apply BFS and DFS to at least *test1* and ideally *test2*, and should be able to do repeated state checking. Use the second week to finish your implementation (record the appropriate data, implement queue/time limits, and implement queue ordering), testing on the larger problem. Use the third week to analyze your data and write your summary report. Be sure you do leave enough time to write the report, since it is worth 25% of the assignment.

1. Implementation (75 points)

Implement a generic uninformed search function, along the lines of the algorithm from the course slides. Write a wrapper function that invoke this generic search function to perform breadth-first, depth-first, and best-first search in the Sudoku search space. Your best-first search should sort the queue of nodes using a "maximally constrained" heuristic. That is, actions that fill empty cells where there is only one legal choice remaining should be tried first; next, try actions that fill empty cells for which there are two legal choices; and so on.

Include mechanisms to limit the length of the queue and/or computation time and to test for repeated states. (You will probably need to do a bit of experimentation to find reasonable values for the queue and time limits. Don't make them too low or you won't be able to solve many of the problems.) Test your code thoroughly, and make sure it's sufficiently well documented for us to read it and understand what it's doing.

Very important: Some of the search spaces will grow quite large, and I don't necessarily expect your implementation to be able to solve all of the problems.

2. Results and Discussion (25 points)

Run breadth-first, depth-first, and best-first search, with and without repeated-state checking, on the test cases *test1* through *test9* (given in the sudoku-basics.lisp file).  (In total, you should have 3 searches * 2 options * 9 test cases = 54 runs.)  Submit a well-organized report that summarizes your findings, and that discusses the questions below.  (Note that the tests have different array sizes.  The only function for which this should matter is the BLOCK-GROUPS function, which I've provided.  However, you'll need to reset XBLOCKS and YBLOCKS appropriately before invoking your solver.)

At a minimum, you should show, for each of the 54 runs, the number of nodes generated, number of nodes expanded, and CPU time consumed. You may present this data in a graph, chart, or table -- whichever you think will be most understandable and most effectively support your conclusions. (You will probably want to write a "wrapper" function to run all of the experiments and gather the statistics together.)

Your report should answer the following questions (though it does not need to be organized in this order, and you are certainly welcome to include additional observations, experiments, or ideas):

  1. Did the algorithms find a solution in all cases?  If not, why not?
  2. How did the various measures of run time (nodes generated/expanded and CPU time) compare for breadth-first search and depth-first search?
  3. How did checking repeated states affect the various measures of run time?  Was this effect different for the different algorithms (BFS vs. DFS)?  Why or why not?
  4. In this domain, what does it mean for a search to be optimal?  What does it mean for a search to be efficient?
  5. How did you find a reasonable queue limit and/or time limit?  How would the algorithms behave if you increased or removed these limits?
  6. How did queue ordering affect the various measures of run time? Was this effect different for the different algorithms?  Why or why not?
  7. I didn't mention the possibility of using a depth limit, or iterative deepening search.  Would either of these be helpful?  Why or why not?

Additional background, description of the problem, and design guidance can be found here.

Extra credit problem (10 points)

You can optionally submit a solution for Russell & Norvig, exercise 5.21 (page 201) to get 10 extra points for Homework 2.

The homework is due on Tue, Oct. 16, midnight. Submit your modified owl file and answers by email ( Bring printed copy to next class (Do not print your modified owl file. Submit printed copy only for the answers to the questions below).

Homework 3 (due Tue, Oct. 26, 2:15pm)

Problem 1, 40 Points: 20 points for (a); 20 points for (b)

Russell&Norvig, exercise 5.8 (page 197)
Some notes that might help you:
  1. The initial state on the figure is (1,4), that means A is on 1, B is on 4
  2. The winning state for A is (4,3), whose value is +1
  3. The first move down from the root of the ree has only one branch (and so does the next move too)
  4. Looking at question (c), which is not part of the homework, might help when solving (b)
  5. In the minimax algorithm there are no such things as ? values. You need to decide what to do when choosing the value to be backed up to a parent node when one of its children has a ? value

Problem 2, 60 Points: 30 points for (b); 10 points for each option from (c) to (e)

Russell&Norvig, exercise 5.9 (page 197-198)
Here are some notes that might help you:
  1. The three should have an empty board as the root node and 2 more levels down the root
  2. Option (b) asks you to take symetry into account in order to reduce the search space, that is, the number of nodes you will expand. As an example, on the first level you only need to expand the first of the following two nodes:
  3. For the second level, as an example, you only need to expand the first of the following two nodes

Problem 3, 10 Points

Russell&Norvig, exercise 6.9 (page 232)
Tips: Thinking of the sudoku (HW2) and the best-first search using a "maximally-constrained" heuristic might be of help. Check also the slides 38-41 for the class of Sep. 16 (Constraint Satisfaction).

Homework 4 (due Tue, Nov. 9, 2:15pm)

In this homework you will do some basic stuff with ontologies. Specifically, you will use Protégé, an existing ontology editor to do a few changes to the ontology that you will be provided, as well as to observe the results of a reasoner.


Download and install Protégé 4.x. Protégé is a powerful ontology editor with many features. So many features that many users have not found most of them. I will provide you here with a quick walkthrough on how to browse our small Pizza ontology and do some basic changes and reasoning. If you have any problems following the instructions here, or if you are interested in more details, you can run through the much more substantial Protege OWL tutorial. That tutorial is intended to teach you more details about OWL and Protégé. This notes are to show how to use Protégé efficiently for basic functionality.

Download the pizza ontology file that I have provided for this homework. This file is a short version of the original pizza ontology, which is a well-known ontology in the semantic web community. It is developed for educational purposes by the University of Manchester, which is a leading university in the development of semantic technologies.

Just as a reference, the original pizza ontology (bigger than the one I have supplied) can be found at


  1. Open the pizzaCMSC671.owl file with Protégé. The Active Ontology tab that shows up initially give you a summary of the information contained in the ontology (number of classes, relations, properties, axioms, etc.)
  2. Go to the Classes tab and take a look at the "Asserted Class Hierarchy" (in the tab with that name). This is the hierarchy that has been asserted by us as users or ontology engineers (as opposed to infered by a reasoner).
    As you select a class (clicking on it) you can see its properties, restrictions, etc. on the right side ("Usage" pane)
  3. PROBLEM 1. Ontology graph

    Draw a graph of the ontology that contains the classes Food, Pizza, PizzaBase, and PizzaTopping, and the relations among them. Here are the guidelines to do it:
  4. You will now perform reasoning on the ontology. Before you do that, check again the "Asserted Class Hierarchy" and notice we have some Pizzas defined as subclasses of the NamedPizza class. This are particular examples of pizzas. I have explicitly decided to put them here as opposed as instances (or individuals). Also, notice that all the other sublcasses of Pizza (CheeseyPizza, InterestingPizza, etc) do not have subclasses.
  5. Make sure you have a reasoner installed with Protégé. Select the "Reasoner" option on the main menu and you should have some reasoner there (Pellet, Fact++, Hermit, or other). I have particularly tried Pellet for this exercise, but you can use any other.
    If you do not see any Reasoner under that option, you need to install one. You can find instructions to install Pellet directly from Protégé here (look for the Installation section).

    PROBLEM 2. Inference results

    Run the reasoner and go to the "Inferred Class Hierarchy" tab (right next to "Asserted Class Hierarchy").
  6. Can you figure out why TomatoTopping is inconsistent? Regardless, delete it (go back to the "Asserted Class Hierarchy" tab, select it and click on the X button) and run the Reasoner again.

    PROBLEM 3. Inference results iteration 2

    Go back to the results ("Inferred Class Hierarchy") and tell what was different this time.
  7. CheeseyVegetableTopping is still inconsistent, can you figure out why? Lets get rid of it too ... Delete it the same way you deleted TomatoTopping.
  8. Finally, come up with a couple of pizzas of your own creation ...

    PROBLEM 4. Define your favorite pizzas (at least two)

    Back in the "Asserted Class Hierarchy", create a subclass of NamedPizza.

The homework is due on Tue, Nov.9, 2:15pm. Submit by email ( and bring printed copy to class.

Homework 5 (due Tue, Nov. 30, midnight)

Problem 1, 40 Points: 20 points for (a); 20 points for (b)

Russell&Norvig, exercise 14.4 (page 559)

For option a, answer the question (if no evidence is observed, are Burglary and Earthquake independent?) from what you see in the network (Fig. 14.2), that is, the topology of the network or topological semantics. Then compute the probability P(Burglary, Earthquake).

For option b, we want to show whether P(B,E|A) and P(B|A)P(E|A) are equal. Use Bayes Theorem to solve for them. That is:

Problem 2, 40 Points

Russell&Norvig, exercise 18.6 (page 764)

Problem 3, 30 Points

  1. [15 points] Draw the bayesian belief network that represents the conditional independence assumptions of the Naive Bayes classifier for the PlayTennis problem discussed in class. Slides 17-19 from Nov. 18 class and slides 59-62 from Nov. 16 class.
  2. [15 points] Give the conditional probability table associated with the node Wind

Hint: The following general bayesian network represents the Naive Bayes (conditional independence) assumptions.

naive bayes assumptions

The homework is due on Tue, Nov. 30, midnight. Submit by email ( and bring printed copy to next class (Thu, Dec. 2nd).