SJCIT Assignment

Estd: 1986

Department of Computer Science & Engineering

ASSIGNMENT
SUBJECT TITLE ARTIFICIAL INTELLIGENCE

SUBJECT TYPE Professional Elective

SUBJECT CODE BCS515B

ACADEMIC YEAR 2024-25 BATCH 2022

SCHEME 2022

SEMESTER V
FACULTY NAME and
Prof. Ajay N, Assistant Professor
DESIGNATION

Module -1

Q. Questions Bloom’s COs

No. LL
To what extent are the following computer systems instances of artificial
intelligence:
• Supermarket bar code scanners.
1 • Web search engines. L3 CO1
• Voice-activated telephone menus.
• Internet routing algorithms that respond dynamically to the state of the
network.
Examine the AI literature to discover whether the following tasks can
currently be solved by computers:
a. Playing a decent game of table tennis (Ping-Pong).
b. Playing a decent game of bridge at a competitive level.
2 c. Discovering and proving new mathematical theorems. L3 CO1
d. Writing an intentionally funny story.
e. Translating spoken English into spoken Kannada in real time.
f. Performing a complex surgical operation.
For the currently infeasible tasks, try to find out what the difficulties are
and predict when, if ever, they will be overcome.
Suppose that the performance measure is concerned with just the first T
3 time steps of the environment and ignores everything thereafter. Show L3 CO1
that a rational agent’s action may depend not just on the state of the
environment but also on the time step it has reached.
4 Write pseudo code agent programs for the goal-based and utility-based agents L4 CO1
5 Implement a simple reflex agent for the vacuum environment L5 CO1

Module -2

Q. Questions Blooms COs

Page | 1
SJCIT Assignment

No. LL
Which of the following are true and which are false? Explain your
answers.
a. Depth-first search always expands at least as many nodes as A∗ search
with an admissible heuristic.
b. h(n) = 0 is an admissible heuristic for the 8-puzzle.
c. A∗ is of no use in robotics because percepts, states, and actions are
1 continuous. L3 CO2
d. Breadth-first search is complete even if zero step costs are allowed.
e. Assume that a rook can move on a chessboard any number of squares
in a straight line, vertically or horizontally, but cannot jump over other
pieces. Manhattan distance is an admissible heuristic for the problem of
moving the rook from square A to square B in the smallest number of
moves.
Write a program that will take as input two Web page URLs and find a
2 path of links from one to the other. What is an appropriate search L3 CO2
strategy? Is bidirectional search a good idea? Could a search engine be
used to implement a predecessor function?
3 Prove that if a heuristic is consistent, it must be admissible. Construct an L3 CO2
admissible heuristic that is not consistent.
Show that the 8-puzzle states are divided into two disjoint sets, such that
any state is reachable from any other state in the same set, while no state
4 is reachable from any state in the other set. Devise a procedure to decide L4 CO2
which set a given state is in, and explain why this is useful for generating
random states.
Your goal is to navigate a robot out of a maze. The robot starts in the
center of the maze facing north. You can turn the robot to face north, east,
south, or west. You can direct the robot to move forward a certain
distance, although it will stop before hitting a wall.
a. Formulate this problem. How large is the state space?
b. In navigating a maze, the only place we need to turn is at the
intersection of two or more corridors. Reformulate this problem using this
5 observation. How large is the state space now? L5 CO2
c. From each point in the maze, we can move in any of the four directions
until we reach a turning point, and this is the only action we need to do.
Reformulate the problem using these actions. Do we need to keep track of
the robot’s orientation now?
d. In our initial description of the problem we already abstracted from the
real world, restricting actions and removing details. List three such
simplifications we made.
Module -3

Q. Questions Bloom’s COs

No. LL
Prove each of the following assertions:
a. α is valid if and only if True |= α.
1 b. For any α, False |= α. L3 CO3
c. α |= β if and only if the sentence (α ⇒ β) is valid.
d. α ≡ β if and only if the sentence (α ⇔ β) is valid.
e. α |= β if and only if the sentence (α ∧ ¬β) is unsatisfiable.
2 Prove, or find a counter example to, each of the following assertions: L3 CO3
a. If α |= γ or β |= γ (or both) then (α ∧ β) |= γ

Page | 2
SJCIT Assignment

b. If α |= (β ∧ γ) then α |= β and α |= γ.
c. If α |= (β ∨ γ) then α |= β or α |= γ (or both).
Consider a vocabulary with only four propositions, A, B, C, and D. How
many models are there for the following sentences?
3 a. B ∨ C. L3 CO3
b. ¬A∨¬B ∨¬C ∨ ¬D.
c. (A ⇒ B) ∧ A∧ ¬B ∧ C ∧ D.
Consider the following sentence:
[(Food ⇒ Party) ∨ (Drinks ⇒ Party)] ⇒ [(Food ∧ Drinks) ⇒ Party] .
a. Determine, using enumeration, whether this sentence is valid,
4 satisfiable (but not valid), or unsatisfiable. L4 CO3
b. Convert the left-hand and right-hand sides of the main implication into
CNF, showing each step, and explain how the results confirm your
answer to (a).
c. Prove your answer to (a) using resolution.
5 Write a successor-state axiom for the Locked predicate, which applies to L5 CO3
doors, assuming the only actions available are Lock and Unlock.
Module -4

Q. Questions Bloom’s COs

No. LL
Which of the following are valid (necessarily true) sentences?
1 a. (∃x x=x) ⇒ (∀ y ∃z y =z). L3 CO4
b. ∀x P(x) ∨¬P(x).
c. ∀ x Smart(x) ∨ (x=x).
Consider a version of the semantics for first-order logic in which models
with empty domains are allowed. Give at least two examples of sentences
2 that are valid according to the standard semantics but not according to the L3 CO4
new semantics. Discuss which outcome makes more intuitive sense for
your examples.
Consider a vocabulary with the following symbols:
Occupation(p, o): Predicate. Person p has occupation o.
Customer (p1, p2): Predicate. Person p1 is a customer of person p2.
Boss(p1, p2): Predicate. Person p1 is a boss of person p2.
Doctor , Surgeon, Lawyer , Actor : Constants denoting occupations.
Emily, Joe: Constants denoting people.
3 Use these symbols to write the following assertions in first-order logic: L3 CO4
a. Emily is either a surgeon or a lawyer.
b. Joe is an actor, but he also holds another job.
c. All surgeons are doctors.
d. Joe does not have a lawyer (i.e., is not a customer of any lawyer).
e. Emily has a boss who is a lawyer.
f. There exists a lawyer all of whose customers are doctors.
g. Every surgeon has a lawyer.
Write in first-order logic the assertion that every key and at least one of
every pair of socks will eventually be lost forever, using only the
4 following vocabulary: Key(x), x is a key; Sock(x), x is a sock; Pair (x, y), L4 CO4
x and y are a pair; Now, the current time; Before(t1, t2), time t1 comes
before time t2; Lost (x, t), object x is lost at time t.
5 Write a general set of facts and axioms to represent the assertion L5 CO4
“Wellington heard about Napoleon’s death” and to correctly answer the

Page | 3
SJCIT Assignment

question “Did Napoleon hear about Wellington’s death?”

Module -5

Q. Questions Bloom’s COs

No. LL
The set-level heuristic (see page 382) uses a planning graph to estimate
1 the cost of achieving a conjunctive goal from the current state. What L3 CO5
relaxed problem is the set-level heuristic the solution to?
Examine the definition of bidirectional search in Module 2.
a. Would bidirectional state-space search be a good idea for planning?
b. What about bidirectional search in the space of partial-order plans?
2 c. Devise a version of partial-order planning in which an action can be L3 CO5
added to a plan if its preconditions can be achieved by the effects of
actions already in the plan. Explain how to deal with conflicts and
ordering constraints. Is the algorithm essentially identical to forward
state-space search?
We contrasted forward and backward state-space searchers with
partial-order planners, saying that the latter is a plan-space searcher.
3 Explain how forward and backward statespace search can also be L3 CO5
considered plan-space searchers, and say what the plan refinement
operators are.
This exercise considers the implementation of search algorithms in
Prolog. Suppose that successor(X,Y) is true when state Y is a successor of
state X; and that goal(X) is true when X is a goal state. Write a definition
4 for solve(X,P), which means that P is a path (list of states) beginning with L4 CO5
X, ending in a goal state, and consisting of a sequence of legal steps as
defined by successor. You will find that depth-first search is the easiest
way to do this. How easy would it be to add heuristic search control?
Write down logical representations for the following sentences, suitable
for use with Generalized Modus Ponens:
a. Horses, cows, and pigs are mammals.
5 b. An offspring of a horse is a horse. L5 CO5
c. Bluebeard is a horse.
d. Bluebeard is Charlie’s parent.
e. Offspring and parent are inverse relations.
f. Every mammal has a parent.

Page | 4