UF CAP 4621 Artificial Intelligence Homework

Homework 1

As an individual living in our modern world, you are all familiar with blue jeans. Everyone wears them and every year tons of old jeans end up in landfills. I want you to brainstorm and list 40 possible uses for blue jeans, other than their intended use of clothing. Note: the solutions that you generate should all be SIGNIFICANTLY different from each other. BE CREATIVE!!

Homework 2

Consider the decanting problem: 3 jugs are capable of holding 12, 7, and 5 liters of liquid. The largest jug is entirely filled with wine, the other two jugs are empty. Using the process of decanting, we want to divide the wine into two equal parts (leaving the smallest jug empty). The jugs are not calibrated, so we can do nothing but pour wine from one jug to another until the first jug is entirely empty, or the second jug entirely full. We assume that this process is performed accurately with no wine spilled. What is the least number of decantings required to achieve this goal.
Using a state-space representation:

Create a representation for the states of this problem. Show at least 3 of the states (other than those described in 3 and 4) and describe what they represent.
Describe the operators. Show four and describe what they represent.
What is the starting state?
What is the ending state?
Show a path through the state-space representation that will solve this problem. You do NOT need to draw the entire state-space representation of the problem.
Solution

Homework 3

The graph shown below represents a network of cities (labeled A through J) with distances between each pair of cities given as the value on each arc. A table is given for each of the nodes identifying its heuristic estimated distance from the goal. You are to determine the shortest path between A and J. You can drop nodes from the tree that you grow that are elsewhere in the tree with a lower cost. NOTE: For your answers you should draw a SERIES of partial solution trees showing the expansion of the search space. DO NOT DRAW YOUR ANSWER AS A SINGLE TREE!

Find a solution using Uniform cost search.
Find a solution using Best-First Search.
Use the A* algorithm to determine the shortest path.
Is the solution found by A* the best solution? Why or why not?
Solution

Homework 4

Apply minimax to the tree below assuming that:

1. a maximum is desired at the top of the tree.
2. a minimum is desired at the top of the tree.

Apply Alpha-Beta pruning to the tree below. UNDERLINE or CIRCLE all leaf nodes which are evaluated and draw diagonal lines through all branches that are pruned.

1. Assume that a maximum is desired at the top of the tree.
2. Assume that a minimum is desired at the top of the tree

Homework 5

Evaluate each of the following S-expressions: (CONS '(A B) '(D F))
(NULL ())
(NULL (CDR '((A B C))))
(CONS 'A '(B))
(ATOM (CDR (CDR '(X Y))))
(CONS '(A B) NIL)
(CADAR '((A (B C) D) E))
(CONS NIL 'A)
(CAAADR '(A ((C D) C) R))
(NULL (LIST 'A))
(ATOM (CADR '(A (B) C)))
(CONS 'A NIL)
(ATOM (CAR (CONS '(A) '(B C))))
(CAR 'A)
(LIST '(A) '(B) '(C))
(APPEND 'A '(B))
(CDR (CONS (CAR '(B D)) NIL))
(LIST 'A (CONS '(B) '((D E))) '(CAR '(S)))
(APPEND '((A)) (ATOM (CDR (CONS 'X '(Y)))))
(APPEND (LIST (EQUAL 'A (CADDR '(C A T)))) '(C D))

Homework 6

Write a nested CAR-CDR expression which will find the A in each of the following: (()(A))
(((B) C) D (A))
(((A) (B)))
((H (D) (A)) B)
((B (D A) E))
((C ((G D) A) B) H)
(E F T ((A) F))
(B ((N (J G) A)))
((((B A))))
((B (C (A))) D)
((((B) C) (D A)))
((C ((G) A)) H)

Evaluate each of the following S-expressions (assume that your Lisp interpreter can evaluate long combinations of CARs and CDRs): (CAADR '(A ((B) C) D))
(CDR '(((A) B)))
(CADR '(((A B) C) D E))
(CAAR '(B ((D E))))
(CADDADR '(A (B C (D) E)))
(CAR '(AB (CD)))
(CADDADAR '((A (B C (D) ((E) F)))))
(CADR '(A B (C)))

Homework 7

Given the following set of clauses:

C v ~D

B

A v ~C v ~D

A v B v ~C v ~D

A v B v ~C

A v ~C ^ ~D

A v B => C ^ D

~A v B => ~C ^ D

Convert each of these statements into Horn Clauses.

Homework 8

Given the following set of rules and facts compute the likelihood that Tim's car was stolen by Mike or that John stole the car:

Rule 1: IF the defendant has a motive AND the defendant has an opportunity THEN the defendant is guilty of the crime (CF = 0.6) Rule 2: IF the defendant has an alibi THEN the defendant is guilty (CF = -0.80) Rule 3: IF the defendant's fingerprints are found on the car THEN the defendant is guilty (CF = 0.4) Rule 4: IF the keys are left in the car THEN the defendant has an opportunity (CF = 0.9) Rule 5: IF the defendant does not like Tim THEN the defendant has a motive (CF = 0.5) Rule 6: IF the defendant needed transportation THEN the defendant has a motive (CF = 0.9) Rule 7: IF the defendant's fingerprints are found on the keys THEN the defendant is guilty (CF = 0.7)

The Facts:

1. Mike's car is broken (therefore, he needed transportation) (CF = 1.0)
2. John's car is not broken (therefore, he did not need transportation) (CF = 1.0)
3. Mike's fingerprints are on the car (CF = 1.0)
4. John's fingerprints are not on the car (CF = 1.0)
5. Mike's fingerprints are not on the keys (CF = 1.0)
6. John's fingerprints are on the keys (CF = 1.0)
7. Tim's keys were left in the car (CF = 1.0)
8. Mike does not like Tim (CF = 0.6)
9. John likes Tim (CF = 0.8)
10. Mike was watching TV when the crime was committed (therefore, he has an alibi) (CF = 0.85)
11. John was sleeping when the crime was committed (therefore, he has a weak alibi) (CF = 0.2)

Homework 9

Label the following diagram using the Guzman labels as discussed in class

Homework 10

Label the following diagram using the Huffman-Clowes labels as discussed in class. Create two distinct labelings.,

Homework 11

Read 3 of the short student papers on the web. If you have written a paper, a maximum of one of these should be on the same topic on which you wrote your paper. For each paper complete the following information:

Paper Name: ________________________________________

Overall Structure: Excellent Good Fair Poor

Writing Style: Excellent Good Fair Poor

Clarity: Excellent Good Fair Poor

General Comments:

Paper Name: ________________________________________

Overall Structure: Excellent Good Fair Poor

Writing Style: Excellent Good Fair Poor

Clarity: Excellent Good Fair Poor

General Comments:

Paper Name: ________________________________________

Overall Structure: Excellent Good Fair Poor

Writing Style: Excellent Good Fair Poor

Clarity: Excellent Good Fair Poor

General Comments:

Internal Links

Parent Article: UF_CAP_4621_Artificial_Intelligence