CS607-Artificial Intelligence

Final Term Paper

SEMESTER FALL 2005
www.vujannat.ning.com
a) (5 marks) You are given the following statements:

1.U
2.¬V
3.(V → X ) → Y
4.(Y ∧ U ) → Z

Prove E using resolution refutation. Show all steps. ¬

b) (3+3+5 marks) The family tree below represents the relationships of a family:

A B
C D

E F G

The dotted circles correspond to female family members, while the solid circles correspond to
male family members. The arrows represent the parent-of relationship, e.g. A is a parent of F.
You can see that A is the father of F while B is the mother of F.

In a predicate logic representation of a family, we have the following predicate format:

Spouse (Symbol a, Symbol b) Arguments: a is the spouse of b
Mother (Symbol a, Symbol b): Arguments: a is the mother of b
Gender (Symbol a, Symbol b: Female/Male): b is the gender of a
 (i) What constants would you define corresponding to the tree given?
(ii) What predicates would you define for the above tree.

(iii) Give formulae using existential and universal quantifiers for the following
relationships (You can use defined predicates in subsequent formulae, e.g. you can
use the predicate father in the defining the formula daughter). All the predicates take
two arguments read as (arg1, arg2): arg1 is the <> of arg2
a. Father
b. Husband
c. Step-Father
d. Maternal Aunt (Khaala)
e. Maternal Grand Father (Naana)
f. Grand Child, by son
g. Paternal Aunt (Phopho)
c) (3+3+3 Marks) Define the following terms. Give examples to support your definitions:

2. Operator:

3. Static Evaluation

Question2
Waist is a fuzzy variable with universe of discourse 16 - 54 inches. The membership functions of
Waist are Fat, Medium and Thin. Draw these membership functions on three separate graphs.

Q#3

Your problem is to generate a 32-bit word containing all 1's. Formulate the solution as a GA.

(i) Clearly write your GA steps.

(ii) Identify the initial population, fitness function, mutation and

crossover steps.
(iii) Can we find the solution word with only using crossover
operation? Support your answer with arguments?
Q#4

a) (5 marks) List and explain briefly the 5 steps of fuzzy inference.

b) (10 marks) Given the fuzzy system below, perform the inference graphically just like Matlab
for input A=0 and B=100. Briefly explain the steps you followed and how the output value of
variable Y is obtained in no more than 10 sentences. Clearly state any assumption that you take in
the inference.

Q#5
Consider the graph showing a road map for distances between cities. The values on the edges are
the distance between two adjacent cities. The values on the nodes are the under-estimates
(heuristics) of the remaining distance. Construct a tree from the given graph and find the solution
using the A* procedure considering A as the initial node, J as the destination node, and 12 as the
bound value. Eliminate the bounded subtree(s) from your solutions and only show the resultant
tree.

2
7
8 6 B 2 H
A
1
G
2 3
2 1
E
3 3
0
6C J
8 1
F
2
1
D
5
 WWW.VUjannat.ning.COM
Connecting VU Students

Final Fall 2007

Artificial Intelligence –CS607

Q#1 Fuzzy system in the inherence method. 15 marks

Rule 1 Newspaper is simple, but does not cover all newspaper is below average
Rule 2 Newspaper is harder to understand, but newspaper is average
Rule 3 Newspaper is simple, And cover all newspaper average is above.
Draw graph and write down steps.
Note: Don’t use Matlab and just perform on exams software text area.

Q #2 15 marks
1-Is a computer vision possible without AI techniques?
2-Is here AI brain exists?
3-Intelligence increases by age? Write comments.

Q#3 10 marks
Prove E by using of PONENS, TOLENS, INTRODUCTION, ELIMINATION Methods
(AvB) Æ (C^-D)
-EÆ D
AvB

Prove E by using Refutation Method.

(A vE) Æ (-D)
-EÆ D

Q# 4 15 marks
Find S and G and Candidate Elimination Method.

D A B C YES/NO
D1 G I W 1
D2 F I W 1
D3 F J V 0
D4 G K V 1
D5 F K W 1
 vujannat.ning.Com
Connecting VU Students

CS607
Final Term Examination – Spring 2006
Time Allowed: 150 Minutes

Question No. 1 Marks : 1

At the end of a Candidate Elimination run, the sets G and S are given as:

G = {(?, X, ?, ?)},
S = {(?, X, ?, ?)},

Answer the following by giving arguments in support of your answers.

a) Are these sets possible together?

b) Which one of the following is the correct interpretation of the state of learning?

(i) All concepts between (?, X, ?, ?) and (P, X, M, ?) inclusive, in the generalization
hierarchy of all concepts of the particular problem.

(ii) (P, X, M, T) is the final concept.

(iii) Learning has converged to the single concept (?, X, ?, ?).

(iv) Candidate Elimination will not converge in learning i.e. would fail.

(v) G and S are empty.

Question No. 2 Marks : 3

a) How many hypothesis (concepts) are possible if we have two attributes that can take 7
values each if we are using conjunctive (AND) logic.

b) If we are using “?” and “Φ” (phi) as two values then reduce the number we will get in
part “a” as much as possible.
Question No. 3 Marks : 3

Suppose we have the following:

We have to prove Z

a) Solve the above Inference problem using the following inference rules: Modus Ponens,
Modus Tolens, And-Introduction and And-Elimination.
b) Solve the same Inference problem above using resolution refutation. Show all steps.

Question No. 4 Marks : 1

Suppose we want to build some preliminary rules for “Robot Motion Guidance System”

Robot Motion Guidance System

Rule I If Distance of object in front is less than 15 meters

Then look right or left

Rule II If In right direction the distance of front object is less then 50 meters
Then move left

Rule III If In left direction the distance of front object is less then 50 meters
Then move right

Rule IV If In left direction the distance of front object is less then 50 meters
AND In right direction the distance of front object is less then 50 meters
AND Distance of object in front is less than 15 meters
Then move backward

Suppose we know the following facts,

i. There is a wall in front of robot at the distance of 10 meters.

ii. There are two big hurdles in left and right directions of robot at the distances of
less than 50 meters.

a) Show that the robot will stop using forward and backward chaining.
b) Implement this expert system using CLIPS code.
 CS607- Artificial Intelligence
Midterm Fall2005
http://vujannat.ning.com
BEST SITE TO HELP STUDENTS
(7+7 marks). Let us define the following propositions: A=x hates studying B=x wastes
time watching movies C=x attends VU lectures D=x gets a good grade in the AI
course
i. Modus Ponens, Modus Tolens, AndElimination and AndIntroduction We know that
if a person hates studying, they waste time watching movies. We also know that if a
person does not hate studying and attends VU lectures, they will get a good grade in the
AI course. There is a student who does not waste time watching movies and attends VU
lectures, prove that this student will get a good grade in AI, using
ii. Resolution refutation. Also state, why do you think resolution refutation is a better
strategy in practical theorem provers? (6 marks). Early man discovers fire in a
simplified chemistry world:

. • IF dry stones strike each other

. • Then a spark is produced
. • Conclusion
. • When there is a spark, dry leaves and oxygen is present in the
atmosphere, then there is fire.
. • Encode the problem using propositions and rules.
. • One day, early man Fred rubbed dry stones together near a bunch of dry
leaves (of coarse there was oxygen, or Fred would not be alive).

•Prove using resolution refutation that Fred created a fire. (5+5+5 marks). Discuss
the three strategies of problem solving briefly. Give examples to support your argument
in each case.
i. Blind/UnInformed Searches
ii. Informed/Heuristic Searches
iii. Optimal Searches (8+2 marks). Run the Alpha Beta Procedure on the following
tree clearly indicating the pruned branches. Calculate the percentage of nodes on which
the static evaluation has to be computed.
 vujannat.ning.com

CS607 Artificial Intelligence

Mid Term Examination – Spring 2006
Time Allowed: 90 Minutes

Please read the following instructions carefully before

attempting any of the questions:
1. Attempt all questions. Marks are written adjacent to each
question.
2. Do not ask any questions about the contents of this
examination from anyone.
a. If you think that there is something wrong with any of the
questions, attempt it to the best of your understanding.
b. If you believe that some essential piece of information is
missing, make an appropriate assumption and use it to solve
the problem.
c. Write all steps, missing steps may lead to deduction of
marks.

**WARNING: Please note that Virtual University takes serious

note of unfair means. Anyone found involved in cheating will get
an `F` grade in this course.

Question No. 1 Marks : 10

Apply the Depth First Search on the tree given below to reach to the goal F
(Highlighted)
Show all the steps you will perform using the table, showing the nodes in Open and
Visited queue.

Question No. 2 Marks : 5

Gives the short answer of the following:

Describe how CNF (Conjunctive Normal Form) helps us in getting truth values of the
logical expressions in an efficient way.

Question No. 3 Marks : 10

Suppose,

U=x hates cooking

V=x wastes time watching movies
X=x reads a lot of cook books
Y=x makes a great healthy meal everyday

We know that if a person hates cooking, he waste time watching movies. We also
know that if a person does not hate cooking and reads a lot of cook books, he will
make a great healthy meal everyday. Ali does not waste time watching movies and
reads a lot of cook books, prove that Ali will make great healthy meals everyday,
using

i. Modus Ponens, Modus Tolens, And-Elimination and And-Introduction

Resolution refutation.

Question No. 4 Marks : 10

Given the two points in the x, y plane represented by (x, y) pairs as under

(x, y) : {(3,8) (7, 10)}

Find the parameters m and c for the line y = mx+c using a GA starting with the two
individuals in the initial population for [m c] as given below.

[1 6] [2 7]

Show at least two iterations (or few if the solution is found in fewer than two
iterations). Clearly show your working for each step. Use both crossover and
mutation. If you don’t get the desired result in two iterations, then output the [m c]
pair that gives the best solution after two iterations.

Question No. 5 Marks : 5

Question No. 6 Marks : 5

Question No. 7 Marks : 5

Question No. 8 Marks : 6

Question No. 9 Marks : 6

Question No. 10 Marks : 11

Question No. 11 Marks : 2

Question No. 12 Marks : 2

Question No. 13 Marks : 10

Question No. 14 Marks : 12

Question No. 15 Marks : 2

Question No. 16 Marks : 2

Question No. 17 Marks : 5

Question No. 18 Marks : 2

Question No. 19 Marks : 5

Question No. 20 Marks : 5

Question No. 21 Marks : 5

Question No. 22 Marks : 6

Question No. 23 Marks : 6

Question No. 24 Marks : 11

Question No. 25 Marks : 2

Question No. 26 Marks : 2

Question No. 27 Marks : 10

Question No. 28 Marks : 12

Question No. 29 Marks : 11

Question No. 30 Marks : 2

Question No. 31 Marks : 2

Question No. 32 Marks : 10

Question No. 33 Marks : 12