CS4341 Introduction to Artificial Intelligence. C2000
Exam 1 - February 4, 2000

Prof. Carolina Ruiz
Department of Computer Science
Worcester Polytechnic Institute

Instructions

NAME: Weiyang Lin _________________________________________

Problem I. Search (40 points)

Suppose that you need to find a path between S and G in the following graph. The number attached to each edge in the graph represents the COST of traversing the edge.

Assume also that the ESTIMATED distances to the goal are given by the following table:

Node: S B C D E F G
Estimated Distance to G: 6 1 3 2 5 4 0

For EACH of the following search methods list the nodes in the order in which they are EXPANDED by the search method while looking for a solution. As an illustration, the solution for Depth 1st search is provided below.

  1. Depth 1st Search

    List: [S, B, D, E, C, F, G]

  2. (5 points) Breadth 1st Search

    List: [S, B, C, D, E, F, G]

  3. (5 points) Depth-limited Search (depth-limit = 2)

    List: [S, B, C]
    An alternative answer would be [S, B, D, E, C, F, G] if you use the convention that depth-limited search expands nodes that are in the "depth-limit level".

  4. (5 points) Iterative Deepening Search

    List for depth-limit = 0: []

    List for depth-limit = 1: [S]

    List for depth-limit = 2: [S, B, C]

    List for depth-limit = 3: [S, B, D, E, C, F, G]

    An alternative answer would be the one below if you use the convention that depth-limited search expands nodes that are in the "depth-limit level".

    List for depth-limit = 0: [S]

    List for depth-limit = 1: [S, B, C]

    List for depth-limit = 2: [S, B, D, E, C, F, G]

    List for depth-limit = 3: [S, B, D, E, C, F, G]

  5. (5 points) Branch-and-Bound (= Uniform Cost Search)

    List: [S, B, C, E, F, D, G]

  6. (5 points) Greedy Search (= Best 1st Search)

    List: [S, B, D, C, G]

  7. (5 points) A*

    List: [S, B, C, G]

  8. (5 points) Hill-climbing

    List:

  9. (5 points) Beam Search (m = 2)

    List: [S, B, C, D, G]

NAME: Kannan Gangadharan __________________________________

Problem II. Game Playing (20 points + 10 EXTRA points)

Suppose you and a friend of yours are playing a board game. It is your turn to move, and the tree below represents your situation. The values of the evaluation function at the leaf nodes are shown in the tree. Note that in this tree not all leaf nodes are at the same level.

  1. (20 points) Use the minimax procedure to select your next move. Show your work on the tree below.

    You select the second child of the root node as your next move since that child produces the highest gain.

  2. (10 EXTRA points) Use the minimax procedure TOGETHER WITH ALPHA-BETA PRUNING to select your next move. Mark with an "X" the nodes that don't need to be evaluated. Show your work on the tree below and explain your answer.

    Nodes marked with an "X" are not evaluated when alpha-beta pruning is used. None of the nodes in the subtree rooted at the node marked with an "X" in the third level of the tree are evaluated.

NAME: Weiyang Lin _________________________________________

Problem III. Rule-Based Systems (20 points)

Consider the following set of rules that describe when a person can vote in a presidential election.

Assume that the operator ">=" (greater than or equal) is a basic operator implemented in the inference engine.
The working memory contains the following assertions:

Solve the following problems. Show your work.

  1. (10 points) Use backward chaining to determine whether or not Bill can vote. Construct a tree showing the steps followed by backward chaining and show when and how the working memory is updated during the depth 1st search. 
     
			Bill can vote		 
			     | (Using R4)
			     |
		     Bill is an American
		     / (Using R1)      \ (Using R2)
		    /		        \
     Bill was born in the US          Bill receives US citizenship
	| (succeeds!)
	| WM <- {Bill is an American.}		Fails!
     Bill is an adult
	| (Using R3)
	|
     Bill's age >= 18

         Fails!

     So, Bill cannot vote!

  2. (10 points) Use forward chaining to derive ALL assertions that are derivable from this knowledge base (that is, from the set of rules together with the assertions in the working memory). Construct trees showing the steps followed by forward chaining and show when and how the working memory is updated during the process. 
      Using R1
			|	?x was born in the US
			| 
		Bill was born in the US 				

		     Succeeds!
		WM <- { Bill is an American.}

  Using R2
			|	?x received US citizenship
			|
		Sue received US citizenship

		     Succeeds!
		WM <- { Sue is an American.}

  Using R3
			|	?x's age >= 18
			|
		Sue's age >= 18
		      
		     Succeeds!
		WM <- { Sue is an adult.}

  Using R4
		              /\       ?x is an American
			  /	   \
		       /	      \ 
     Bill is an American.           Sue is an American
	      |  ?x is an adult		     |  ?x is an adult
	      |				     |
     Bill is an adult	            Sue is an Adult

	  Fails!			Succeeds!
				    WM <- { Sue can vote.}

NAME: Kannan Gangadharan __________________________________

Problem IV. Frame Systems (20 points)

Consider the following hierarchy of frames. 
                   COMPUTER USERS
                   /           |   
                  /            |   
              ako/             | ako
                /              |    
               /               |    
     UNIX USERS             PC USERS           MICROSOFT
                                               CUSTOMERS	
               \           /        \           /
                \         /          \         /
              ako\       /ako      ako\       /ako
                  \     /              \     /
                   \   /                \   /
               LINUX USERS            WINDOWS98
                                        USERS
                         \           /   
                          \         /   
                      is-a \       /is-a
                            \     /   
                             \   /   
                              AMY

  1. (15 points) Give the class-precedence list for Amy that would be obtained by applying the topological-sorting algorithm to the previous graph. (You don't need to show the steps of the topological sorting algorithm.)

    Node
    Fish-hook pairs
    Amy Amy-Linux Users, Linux Users-Windows98 Users
    Linux Users Linux Users-Unix Users, Unix Users-PC Users
    Windows98 Users Windows98 Users-PC Users, PC Users-Microsoft Customers
    Unix Users Unix Users-Computer Users
    PC Users PC Users-Computer Users

    Class Precedence list :

    Amy
    Linux Users
    Unix Users                                -  Use C
    Windows98 Users
    PC Users                                  - Use C++
    Computer Users                        - Use Fortran
    Microsoft Customers

  2. (5 points) Suppose that each of the classes Unix users, PC users and Computer Users contains a favorite programming language slot. The default value for this slot is:

    What is the value obtained for Amy's favorite programming language according to the class-precedence list you constructed above? Explain you answer.

    Amy's favorite programming language is C