Q1.

Trace the operation of A∗ search applied to the problem of getting to

Bucharest from Lugoj using the straight-line distance heuristic. That is,
show the sequence of nodes that the algorithm will consider and the f, g, and
h score for each node.
A.
Q2. To what extent are the following computer systems instances of artificial
intelligence:
a. Supermarket bar code scanners.
A. These are generally not considered instances of artificial intelligence. Bar
code scanners read and process information from barcodes, they typically
follow predefined rules and don't exhibit learning or adaptive capabilities.
b. Web search engines.
A. Web search engines often use elements of artificial intelligence,
particularly in the form of machine learning algorithms. Search engines
use complex algorithms to understand what a user wants, in this way they
improve search relevance, and even provide personalized
recommendations.
c. Voice-activated telephone menus.
A. These systems may use basic forms of AI, such as natural language
processing (NLP) or speech recognition, to understand and respond to
user inputs.
d. Internet routing algorithms that respond dynamically to the state of the
network
A. Internet routing algorithms that respond dynamically to the state of the
network are generally not considered instances of AI. They typically use
protocols and algorithms, like BGP (Border Gateway Protocol), to make
routing decisions based on network conditions.

4 3
Q3. Apply SVD for the following matrix: [ ]
1 2
A.
Q4. Use the following table for
S.No. Horns Tail Tusks Paws Fur Color Hooves Size Elephant
1 No Short Yes No No Black No Big Yes
2 No Short No No No Brown No Medium Yes
3 Yes Short No No No Brown Yes Medium No
4 No Short Yes No No Black No Medium Yes
5 No Long No Yes Yes White No Medium No
6 No Short Yes Yes Yes Black No Big Yes

a. Find-S algorithm
A.
• Step 1: Initialize 'h' to the most specific hypothesis. There are 9
attributes, so for each attribute,we initially fill ' Ø ' in the initial
hypothesis 'h'.
h = <Ø, Ø, Ø, Ø, Ø, Ø, Ø, Ø, Ø>
• Step 2: Generalize the initial hypothesis for the first positive instance. I1
is a positive instance, so generalize the most specific hypothesis 'h' to
include this positive instance. Hence,
I1 = <No, Short, Yes, No, No, Black, No, Big, Yes>
h = <No, Short, Yes, No, No, Black, No, Big, Yes>
•Step 3: Scan the next instance I2, since I2 is a positive instance.
Generalize 'h' to include positive instance I2. For each of the non-
 matching attribute value in 'h' put a '?' to include this positive instance.
The third, sixth and eight attributes values are mismatching in 'h' with
I2, so put a '?'.
I2= < No, Short, No, No, No, Brown, No, Medium, Yes >
h = <No, Short, ?, No, No, ?, No, ?, Yes>
• Now, scan I3. Since it is a negative instance, ignore it. Hence, the
hypothesis remains the same without any change after scanning I3.
I3= < Yes, Short, No, No, No, Brown, Yes, Medium, No >
h = <No, Short, ?, No, No, ?, No, ?, Yes>
• Now scan I4. Since it is a positive instance, check for mismatch in the
hypothesis 'h' with I4.The 8th attribute value Is mismatched, so add '?'
to h at the 8th position.
I4 = <No, Short, Yes, No, No, Black, No, Medium, Yes>
h = <No, Short, ?, No, No, ?, No, ?, Yes>
• Now, scan I5. Since it is a positive instance, check for mismatch in the
hypothesis 'h' with I5.The 2nd attribute value IS mismatched, so add '?'
to this attributes in 'h'.
I5= < No, Long, No, Yes, Yes, White, No, Medium, No >
h = <No, ?, ?, No, No, ?, No, ?, Yes>
• Now scan I6. Since it is a positive instance, check for mismatch in the
hypothesis 'h' with I6.The 3rd 4th attribute values are mismatched, so
add '?' to this attributes in 'h'.
I6= < No, Short, Yes, Yes, Yes, Black, No, Big, Yes >
h = <No, ?, ?, ?, ?, ?, No, ?, Yes>

• Now, the final hypothesis generated with Find-S algorithm is:

h = <No, ?, ?, ?, ?, ?, No, ?, Yes>

b. Candidate Elimination algorithm:

• Step 1: Initialize 'G' boundary to the maximally general hypotheses,
g = <?, ?, ?, ?, ?, ?, ?, ?, ?>
• Step 2: Initialize 'S' boundary to the maximally specific hypothesis.
There are 6 attributes, so foreach attribute, we initially fill 'o' in the
hypothesis 'S'.
s = <Ø, Ø, Ø, Ø, Ø, Ø, Ø, Ø, Ø>
• Generalize the initial hypothesis for the first positive instance. I1 is a
positive instance so generalize the most specific hypothesis 'S' to
include this positive instance. Hence,
I1=< No, Short, Yes, No, No, Black, No, Big, Yes >
s1=< No, Short, Yes, No, No, Black, No, Big, Yes >
g1=<?, ?, ?, ?, ?, ?, ?, ?, ?>
•Step 3:
o Iteration 1
Scan the next instance I2. Since I2 is a positive instance,
generalize 'S1' to include positive instance I2. For each of the
non-matching attribute value in 's1', put a '?' to include this
positive instance. The third attribute value is mismatching in 's1'
with I2, so put a '?'.
I2= <No, Short, No, No, No, Brown, No, Medium, Yes >
s2=< No, Short, ?, No, No, ?, No, ?, Yes >
g2=<?, ?, ?, ?, ?, ?, ?, ?, ?>
o Iteration 2
Scan the next instance I3. Since it is a negative instance,
specialize G2 to exclude the negative example but stay
consistent with S2. Generate hypothesis for each of the non-
matching attribute value in S2 and fill with the attribute value of
S2. In those generated hypotheses, for all matching attribute
values, put a '?'. The first, 3rd,6th,7th,8th,9th attribute values do not
match, hence '3' hypotheses are generated in G3.
There is no inconsistent hypothesis in S2 with the negative
instance, hence S3 remains the
same.
I3= < Yes, Short, No, No, No, Brown, Yes, Medium, No >
s3=< No, Short, ?, No, No, ?, No, ?, Yes >
g3=<No, ?, ?, ?, ?, ?, ?, ?, ?>
<?, ?, Yes, ?, ?, ?, ?, ?, ?>
<?, ?, ?, ?, ?, Black, ?, ?, ?>
<?, ?, ?, ?, ?, ?, No, ?, ?>
<?, ?, ?, ?, ?, ?, ?, Medium, ?>
<?, ?, ?, ?, ?, ?, ?, ?, Yes>
o Iteration 3
Now Scan I4. Since it is a positive instance, check for mismatch
in the hypothesis 'S3' with I4. The 8th attribute value Is
mismatched, so add '?' to h at the 8th position..
I4 = <No, Short, Yes, No, No, Black, No, Medium, Yes>
s4 = <No, Short, ?, No, No, ?, No, ?, Yes>
g4=<No, ?, ?, ?, ?, ?, ?, ?, ?>
<?, ?, Yes, ?, ?, ?, ?, ?, ?>
<?, ?, ?, ?, ?, Black, ?, ?, ?>
<?, ?, ?, ?, ?, ?, No, ?, ?>
<?, ?, ?, ?, ?, ?, ?, Medium, ?>
<?, ?, ?, ?, ?, ?, ?, ?, Yes>
 o Iteration 4
Now Scan I5. Since it is a positive instance, check for mismatch
in the hypothesis 'S4' with I4. The 2nd attribute value IS
mismatched, so add '?' to this attributes in 'S4'.
I5= < No, Long, No, Yes, Yes, White, No, Medium, No >
s5 = <No, ?, ?, No, No, ?, No, ?, Yes>
g5=<No, ?, ?, ?, ?, ?, ?, ?, ?>
<?, ?, Yes, ?, ?, ?, ?, ?, ?>
<?, ?, ?, ?, ?, Black, ?, ?, ?>
<?, ?, ?, ?, ?, ?, No, ?, ?>
<?, ?, ?, ?, ?, ?, ?, Medium, ?>
<?, ?, ?, ?, ?, ?, ?, ?, Yes>

o Iteration 5
Now scan I6. Since it is a positive instance, check for mismatch in
the hypothesis 'h' with I6.The 3rd 4th attribute values are
mismatched, so add '?' to this attribute in 'h'.
I6= < No, Short, Yes, Yes, Yes, Black, No, Big, Yes >
s6 = <No, ?, ?, ?, ?, ?, No, ?, Yes>
g6=<No, ?, ?, ?, ?, ?, ?, ?, ?>
<?, ?, Yes, ?, ?, ?, ?, ?, ?>
<?, ?, ?, ?, ?, Black, ?, ?, ?>
<?, ?, ?, ?, ?, ?, No, ?, ?>
<?, ?, ?, ?, ?, ?, ?, Medium, ?>
<?, ?, ?, ?, ?, ?, ?, ?, Yes>

• Now, the final hypothesis generated with Find-S algorithm is:

s = <No, ?, ?, ?, ?, ?, No, ?, Yes>
g=<No, ?, ?, ?, ?, ?, ?, ?, ?>
<?, ?, Yes, ?, ?, ?, ?, ?, ?>
<?, ?, ?, ?, ?, Black, ?, ?, ?>
<?, ?, ?, ?, ?, ?, No, ?, ?>
<?, ?, ?, ?, ?, ?, ?, Medium, ?>
<?, ?, ?, ?, ?, ?, ?, ?, Yes>