Ai Summer 2022 Previous Year Paper Solutions 3161608

Q1

(a) What is artificial intelligence? Define the different task domains of artificial intelligence.. (3 marks)

Articial Intelligence is the branch of computer science, whose objective is to develop machine which can think and behave like human.

Artifical Intelligence is one of the most named technology nowadays.

Artificial Intelligence is used in education, healthcare, social media, ecommerce.

Types:

1. Weak AI
2. General AI
3. Strong AI

Task of Domain of artificial intelligence

Therre are mainly three task domain in AI

1. Mundane Task :

   :- Perceptions - Speech, Computer Vision

2. Formal Task :

   :- Game Theory

   :- Subjective Task

3. Expert Task :

   :- Engineering

   :- Understanding

   :- Effective task

(b) Explain the production system. (4 marks)

Production system is the set of production rules which are applied to problem for solving the problem.

Production system provide mechanism for applying that rules.

These are three components in production system.

1. Global Database

   Global Database contain all data about problem and rules are created from global database.

2. A set of rules

   Set of rules are a condition based rules. if condition satisfied then we can apply the rule otherwise we can’t apply the rule.

3. Central system

   Central system helps to apply production rules.

Example: Water Jug problem.

Supposem, we have three jugs 12 litre, 8 litre, and 3 litre, we are ablt to pour water on surface but can’t able to fill that jug with water and goal is to achieve 2 litre in 12 litre jug.

Production system

• A = 12 , B = 8, C = 3
• Fill B from A
• Fill C from A
• pour water from C
• fill C from B
• pour water from C
• pour water from A
• fill A from B with remaining water.

(c) Explain the State space search with the use of 8 Puzzle Problem (7 marks)

State space is the tree with all the possible solution

suppose initial state and goal state for 8 puzzle problem

Ans :

State Space is the tree with all the possible solution.

suppose initial state and goal state for 8 puzzle problem.

Q2

(a) Explain: 1) Local maximum 2) Plateau 3) Ridge. (3 marks)

1. Local Maximum: is higher state that it’s neighbours, but actually there might be much higher state than local maximum.

   

2. Plateau: is a region of state space landscape where all the neighbours have same value or height.

   

3. Ridges: is a region where there is higher than its value state present but itself has slope.

   

(b) Explain depth first search algorithm. (4 marks)

Depth First search is one of the searching algorithm which is used in tree or graph.

Depth First Search is uninformed search that means there is no knowledge about goal state, and how close from goal state.

DFS start with root node and traverse its adjacent node and going to the depth.

Left Node → Root Node → Right Node

Depth First Search (DFS) is recursive and backtracking algorithm for traversing a graph or tree.

Working:

The working of Depth First Search is similar to the Breadth First Search.

Search Order:

DFS is implemented using stack data-structure, it uses FIFO (First in First out) strategy, so the search order is FIFO.

DFS Traverses the graph by fully exploring the node by expanding its children recursively until the end is reached only after then moving to the next node.

Advantages:

The main advantage of Depth First Search is to require less memory because it only needs to store stack of nodes.

It also requires less time so that it is faster than BFS.

Disadvantages:

The disadvantage of Depth-First Search is that there is a possibility that it may down the left-most path forever. Thus it may get stuck in infinite loop.

It does not give the gaurantee of finding the optimal solution.

Time Complexity:

O (b^d)

where b is current state of node, d is depth of tree.

Space Complexity:

O (b^d)

where b is current state of node, d is depth of tree.

Example:

Solution Search Order:

A B D E C

(c) Explain A* algorithm in detail. (7 marks)

• A* Algorithm is most important and commonly known special form of Best First Search (BFS) Algorithm.
• It finds the solution as shortest path by finding the state space tree by heuristic problem.
• A* Algorithm is similar as UTS because it uses f(n) + g(n) instead of using only f(n).

Working of A* Algorithm

• working of A* Algorithm can be described as follows:

Algorithm

1. Starting by placing the start node in open list.
2. Check whether openlist is empty or not if it is empty then returns.
3. select the node from openlist which has the smallest value of evaluation function and if it is goal state then returns.
4. expand the node in to its successors and they are part of openlist and close list then return and place the node in closed list.
5. Calculate the evaluation function of successor ni, and place in to open list.
6. repeat from step 2.

Advantages

• It is complete and optimal.
• It can solve any complex problem easily.
• A* Algorithm is best algorithm from all searching strategies.

Diadvantages

• Main drawback of A* is memory requirement.
• A* Algorithm does not give gaurantee of finding the optimal solution.
• A* algorithm has some complexity issues.

OR

(c) Solve the following Cryptarithmetic Problem.

SEND

+MORE

MONEY (7 marks)

Here we can take value from 0 - 9 and if we take S=8, M=9 then carry will be one that’s why M=1

Now for generate carry using S and M we can use S + M ≥ 10

We have S=1 then only one which can satisfy condition is 9

Thats why S = 9 and O = 0

Now E+O = N if we takes E than it become E = N thats not true that’s why we need carry.

M = 1, S = 9, O = 0

Now, suppose E=5, as then N = 6 (5+carry)

now we need carry+N+R=15

1+6+R=15 , thus R = 8

E=5

we need to find which given carry

that means we need to select ≥ 6

6 is not possible

then 7 is perfect for E

Hence, 9 5 6 7 +1 0 8 5 ———— 1 0 6 5 2

Q3

(a) Explain AND-OR graphs. (3 marks)

AND-OR graph problem is divided into subproblem and than solve individually that subproblem and combine together to get the solution of that problem.

It is also called problem reducing AO*

AND - OR Graphs:

AO* Algorithm is used for complex problems that can be decomposible in to smaller subproblems and that can be easily solved by AND-OR graphs.

AND OR Graphs are specialized graphs that is used for complex problems to make them more manageable in order to find the solution.

AND OR Graphs are specialized graphs in which AND portion of graph represents the set of tasks for achieving the goals, OR portion of graph represents the different methods for accomplishing the same goal.

In the above example statement ‘steal a car’ includes the OR portion. AND Portion includes two statements and they are ‘buy a car with own money’ and ‘get a car’.

Working of AO* Algorithm:

Explanation :

F(n) = g(n) + h(n)

where g(n) is actual cost, h(n) is estimated cost.

[ Evaluation function ]

(b) Differentiate declarative and procedural knowledge. (4 marks)

Declarative Knowledge	Procedural Knowledge
It contain object function	It contain reasoning, process.
It represent to simple knowledge which are available	It refers how to represent knowledge
can’t represent using prolog	represent using prolog
simple to understand	hard to understand

(c) Consider the following sentences:

• Raj likes all kinds of food.
• Apples are food.
• Anything anyone eats and isn’t killed by is food.
• Sachin eats peanuts and is still alive.
• Vinod eats everything Sachin eats.

Attempt following:

1. Translate these sentences into formulas in predicate logic
2. Use resolution to answer the question, “What food does Vinod eat?”

(7 marks)

1. • Food (X) ∧ Likes (Raj, X) where x is any food
   • Food (Apples)
   • ⩝x⩝y EAT(X,Y) ∧ ¬ Killed (X) → Food(X) X = Food Y = Anyone
   • Eat (Peanuts, Sachin ) ∧ Alive (Sachin)
   • Eat (X, Vinod) → Eat (X, Sachin)

2. Represent in ocnjuctive normal form and remove quantifier.

   • Food (x) ∧ Likes (Raj, X)
   • Food(Apple)
   • ( EAT(X,Y) ∨ Kiled(X) ) ∨ Food (X)
   • EAT (Peanuts, Sachin) ∧ Alive (Sachin)
   • ¬EAT(X, Vinod) ∨ EAT(X, Sachin)

   Then from the sentence

   Sachin eats peanuts and vinod eats everything sachine eats then we can say vinod eats peanuts

   then suppose vinod eats peanuts and negate the sentence

   TODO : Insert a diagram here

OR

Q3

(a) Explain Unification. (3 marks)

Unification is a process where two logical expressions are made identical by finding a substitution for variables.

It involves recursively matching corresponding components of the expressions, allowing variables to be instantiated with terms, and determining if the expressions can be unified.

Unification is fundamental in languages like Prolog for pattern matching, goal resolution, and constraint solving, enabling the execution of programs by determining if goals can be satisfied based on the available knowledge.

(b) Differentiate forward chaining and backward chaining. (4 marks)

Sr.	Forward Chaining	Backward Chaining
1.	Forward chaining starts from known facts and applies inference rule to extract more data unit it reaches to the goal.	Backward chaining starts from the goal and works backward through inference rules to find the required facts that support the goal.
2.	It is a bottom-up approach	It is a top-down approach
3.	Forward chaining is known as data-driven inference technique as we reach to the goal using the available data.	Backward chaining is known as goal-driven technique as we start from the goal and divide into sub-goal to extract the facts.
4.	Forward chaining reasoning applies a breadth-first search strategy.	Backward chaining reasoning applies a depth-first search strategy.
5.	Forward chaining tests for all the available rules	Backward chaining only tests for few required rules.
6.	Forward chaining is suitable for the planning, monitoring, control, and interpretation application.	Backward chaining is suitable for diagnostic, prescription, and debugging application.
7.	Forward chaining can generate an infinite number of possible conclusions.	Backward chaining generates a finite number of possible conclusions.
8.	It operates in the forward direction.	It operates in the backward direction.
9.	Forward chaining is aimed for any conclusion.	Backward chaining is only aimed for the required data.

(c) Discuss the different approaches to knowledge representation. (7 marks)

There are mainly four approaches to knowledge representation, which are givenbelow:

1. Simple relational knowledge:

• It is the simplest way of storing facts which uses the relational method, and each fact about a set of the object is set out systematically in columns.
• This approach of knowledge representation is famous in database systems where the relationship between different entities is represented.
• This approach has little opportunity for inference.

Example: The following is the simple relational knowledge representation.

Player	Weight	Age
Player1	65	23
Player2	58	18
Player3	75	24

2. Inheritable knowledge:

• In the inheritable knowledge approach, all data must be stored into a hierarchy of classes.
• All classes should be arranged in a generalized form or a hierarchal manner.
• In this approach, we apply inheritance property.
• Elements inherit values from other members of a class.
• This approach contains inheritable knowledge which shows a relation between instance and class, and it is called instance relation.
• Every individual frame can represent the collection of attributes and its value.
• In this approach, objects and values are represented in Boxed nodes.
• We use Arrows which point from objects to their values.
• Example:

3. Inferential knowledge:

• Inferential knowledge approach represents knowledge in the form of formal logics.
• This approach can be used to derive more facts.
• It guaranteed correctness.
• Example: Let's suppose there are two statements:
  1. Marcus is a man
  2. All men are mortal, then it can represent as man(Marcus) ∀x = man (x) ----------> mortal (x)s

4. Procedural knowledge:

• Procedural knowledge approach uses small programs and codes which describes how to do specific things, and how to proceed.
• In this approach, one important rule is used which is If-Then rule.
• In this knowledge, we can use various coding languages such as LISP language and Prolog language.
• We can easily represent heuristic or domain-specific knowledge using this approach.
• But it is not necessary that we can represent all cases in this approach.

Q4

(a) Explain Propositional logic. (3 marks

Propositional logic (PL) is the simplest form of logic where all the statements are made by propositions. A proposition is a declarative statement which is either true or false. It is a technique of knowledge representation in logical and mathematical form.

Propositional logic is also called Boolean logic as it works on 0 and 1.

In propositional logic, we use symbolic variables to represent the logic, and we can use any symbol for a representing a proposition, such A, B, C, P, Q, R, etc.

Propositions can be either true or false, but it cannot be both.

A proposition formula which is always true is called tautology, and it is also called a valid sentence. A proposition formula which is always false is called Contradiction.

Example :

a. It is Sunday.

b. The Sun rises from West (False proposition)

c. 3+3= 7(False proposition)

d. 5 is a prime number.

(b) Write a short note on statistical learning. (4 marks)

Statistical Learning is Artificial Intelligence is a set of tools for machine learning that uses statistics and functional analysis. In simple words, Statistical learning is understanding from training data and predicting on unseen data.

Statistical learning is used to build predictive models based on the data.

Statistical learning can be used to build applications for computer vision, text analytics, voice recognition, etc.

Benefits

• The primary advantage of statistical learning is its ability to predict outcomes accurately, making it invaluable in decision-making processes across various domains.
• It offers models that can be tailored to both linear and nonlinear relationships, accommodating a wide array of data types and structures.
• Furthermore, statistical learning emphasizes model validation and the avoidance of overfitting, ensuring that predictions are both reliable and generalizable to new data.

How It Is Used

• Statistical learning involves several steps, starting from gathering and preparing data, selecting appropriate models (parametric or non-parametric), and employing techniques like cross-validation and regularization to refine these models. The choice of algorithm—whether regression, decision trees, or more sophisticated ensemble methods—depends on the specific requirements of the dataset and the prediction task at hand.

Example : In healthcare, statistical learning plays a pivotal role in predicting disease outbreaks. By analyzing trends and patterns from historical health data, models can forecast the likelihood of future outbreaks.

(c) Explain Alpha-Beta cutoff procedure in game playing with example.

The Alpha-beta cutoff procedure is an optimization technique used with the Minimax algorithm in game playing. It significantly reduces the number of nodes explored while maintaining the optimal solution. Here's how it works:

Concepts:

• Minimax Algorithm: This algorithm explores all possible game states for a given depth and chooses the move that maximizes its own score (minimizes the opponent's score).
• Alpha (α): Represents the best guaranteed score the maximizing player can achieve from that point onwards.
• Beta (β): Represents the best guaranteed score the minimizing player can achieve from that point onwards.

Alpha cutoffs are applied by the maximizing player, cuts off moves at minimizing level. Similarly Beta cutoffs are applied by minimizing player (the opponent) cuts of moves at maximizing ply.

Cutoff means the underlying nodes will not be explored as the player has already got better moves (options).

It is also important to note that alpha and beta cutoffs are not applied together but at alternative plies (levels).

Consider a simplified Tic-Tac-Toe game with 3 levels (depth).

• At the root level (Maximizing player):
  • Explore all possible moves (9 child nodes).
  • For each move, calculate the potential score at the next level (minimizing player).
  • Let's say move A leads to a score of 5 (α = 5).
  • If another move B leads to a score of 3 (β = 3), prune the remaining moves since the opponent won't choose a move worse than 3.
• Choose move A as it guarantees the best outcome (score of 5).

By pruning unnecessary branches, Alpha-beta significantly reduces the number of nodes explored, making the search more efficient and allowing for deeper analysis within the same time frame.

OR

Q4

(a) Explain Quantifier. ( 3 marks )

Quantifier used in predicate or first order logic to represent some special sentences like some, all.

There are two quantifier

1. Universal Quantifier

   It is used for represent sentences like all, everything, anything

   For ⩝x are can say that

   for all X

   for every X

   ex. All boys like watch :- ⩝x LIKE (x, watch) , where x represent boys

2. Extential Quantifier

   It is used to represent sentence like some, someone ,..

   for ∃x we can say that for some x

   ex. some boys like watch

   ∃x LIKE (X, watch), where x represent boys

(b) Discuss Bayesian network and its application. (4 marks)

Bayesian Network is used to solve problem which contain uncertainty.

Bayesian Network is probabilistic because it is built from probability distribution and it use probability to predict.

Bayesian Network is graphical representation of set of variable and their conditional dependency using directed acrylic graph.

Bayesian Network is build from nodes and edges.

edges represent the child node is dependent on parent node.

here we can say that B is child node of A.

Applications of Bayesian network :

• Anomaly Detection It is used for find anomaly in problem like uncertainty
• Decision Making It is based on probability and using probability max decision
• To solve problem which contain lack of knowledge

(c) Explain minimax procedure for game playing with example. (7 marks)

Minmax algorithm is mainly used in game theory.

This algorithm is used in two player game

In this algorithm one player is min and other is max.

Both player playing to find optimal solution

Min is trying to achieve minimum value, and max is trying to achieve maximum value to win.

this algorithm used in chess palying, go etc.

In this algorithm, min choose minimum value and max choose maximum values.

MinMax algorithm has some limitation like for chess, playing there is lots of move so we cannot presume that moves. It takes more space more time to execute.

A→E→L

• Max player tries to choose the maximum benifit from the underlying options, while the Min player tries to get the minimum possible value which will have the most benifit on min. Both players tried to get the best option available.

Q5

(a) Discuss Bay’s theorem. (3 marks)

Bay’s theorem is base of bayesian network.

It is combination of conditional and marginal probabilities.

suppose there is two event A and

Porbability of A when B is already camed.

$P(A+B) = \frac{P(A ∩ B)}{P(B)} ∴P(A∩B) = P(A+B) P(B)$ ——-1

Probability B when A is already occured

(b) Discuss Goal Stack Planning. (4 marks)

Planning is the process of ordering action and when we perform those action it will lead to the solution.

Goal stack planning is linear planning in which we are solving task one by one.

we work backwards from the goal state to the initial state.

We start at the goal state and we try fulfilling the preconditions required to achieve the initial state. These preconditions in turn have their own set of preconditions, which are required to be satisfied first. We keep solving these “goals” and “sub-goals” until we finally arrive at the Initial State.

We make use of a stack to hold these goals that need to be fulfilled as well the actions that we need to perform for the same.

Apart from the “Initial State” and the “Goal State”, we maintain a “World State” configuration as well. Goal Stack uses this world state to work its way from Goal State to Initial State. World State on the other hand starts off as the Initial State and ends up being transformed into the Goal state.

Algorithm:

Push the Goal state in to the Stack

Push the individual Predicates of the Goal State into the Stack

Loop till the Stack is empty

    Pop an element E from the stack

    IF E is a Predicate

        IF E is True then

            Do Nothing

        ELSE

            Push the relevant action into the Stack

            Push the individual predicates of the Precondition of the action into the Stack

    Else IF E is an Action

        Apply the action to the current State.

        Add the action ‘a’ to the plan

Example

(c) Explain CUT, FAIL and REPEAT predicates in PROLOG. ( 7 marks )

predicates like CUT, FAIL, and REPEAT play crucial roles in controlling the flow of logic programs.

These are built-in predicates that help manage how Prolog searches for solutions to queries.

CUT (!)

• The CUT predicate is used in Prolog to control backtracking. When Prolog encounters a CUT in a clause, it commits to all the choices made since the parent goal was invoked and removes all other choices that were available at the point where CUT was encountered. This is often referred to as "pruning" the search tree.
• CUT is useful for improving efficiency by preventing Prolog from exploring unnecessary paths after a solution is found, or to enforce determinism in parts of the program. flow max(X, Y, X) :- X >= Y, !. max(X, Y, Y).
• In this example, if X >= Y succeeds, the ! prevents Prolog from considering the second clause of the max predicate if backtracking occurs.

FAIL (fail)

• FAIL is a predicate that always fails whenever it is called. In Prolog, failing means that the current path does not provide a solution, and Prolog should backtrack to try other possibilities.
• FAIL is often used to force backtracking or to signal that the logic has reached a state that should not produce a result. flow delete_all(_, [], []). delete_all(X, [X|T], R) :- !, delete_all(X, T, R). delete_all(X, [H|T], [H|R]) :- delete_all(X, T, R).
• In this case, fail can be used in conditions to ensure the correct elements are filtered out without producing output.

REPEAT

• REPEAT is a predicate that succeeds repeatedly indefinitely.
• It is useful when you need to generate multiple solutions or when you want to keep a goal alive for repeated attempts. Each time Prolog backtracks to REPEAT, it succeeds again. flow repeat. repeat :- repeat.
• This simple definition shows that REPEAT will always succeed and, upon backtracking, will succeed again, effectively creating an infinite loop unless controlled by other conditions.

OR

Q5

(a) Explain Predicate logic. (3 marks)

Predicate Logic deals with predicates, which are propositions, consist of variables.

Predicate Logic - Definition

• A predicate is an expression of one or more variables determined on some specific domain. A predicate with variables can be made a proposition by either authorizing a value to the variable or by quantifying the variable. The following are some examples of predicates.
  • Consider E(x, y) denote "x = y"
  • Consider X(a, b, c) denote "a + b + c = 0"
  • Consider M(x, y) denote "x is married to y."

(b) Explain Hierarchical Planning. (4 marks)

• Hierarchical planning is an approach to planning in artificial intelligence that involves breaking down complex planning problems into smaller, more manageable subproblems. This is achieved by decomposing the overall planning problem into a hierarchy of subproblems, where each subproblem is easier to solve than the overall problem.
• At each level of the hierarchy, there are a set of goals to be achieved and a set of actions that can be taken to achieve those goals. The lower-level subproblems correspond to more specific and concrete goals and actions, while higher-level subproblems correspond to more abstract and general goals and actions.
• The hierarchical planning approach allows planners to focus on the details of the lower-level subproblems without worrying about the higher-level goals, and to work on the higher-level goals without worrying about the details of the lower-level subproblems. This makes the overall planning process more efficient and effective.
• Hierarchical planning has been applied to a wide range of planning problems in artificial intelligence, including robot navigation, task planning, and game-playing.

(c) Write a PROLOG program to find the sum of elements of a list. ( 7 marks )

% sum_list(List, Sum) - Sums all elements of List into Sum.

% Base case: The sum of an empty list is 0.
sum_list([], 0).

% Recursive case: Add the head of the list to the sum of the tail.
sum_list([Head|Tail], Sum) :-
    sum_list(Tail, TailSum),
    Sum is Head + TailSum.

Explanation

1. Base Case (sum_list([], 0)):

   This clause handles the simplest case where the list is empty ([]). The sum of an empty list is defined as 0. This is the stopping condition for the recursion.

2. **Recursive Case (sum_list([Head|Tail], Sum)):

   This clause is used when the list is not empty. It deconstructs the list into its head (Head) and tail (Tail):

   • Head is the first element of the list.
   • Tail is a sublist containing the rest of the elements after Head.
   • The predicate first recursively calls sum_list(Tail, TailSum) to find the sum of the tail.
   • Once the sum of the tail (TailSum) is computed, it adds Head to TailSum to get the total sum, which is unified with Sum.