Ans: Artificial Intelligence is the branch of computer science concerned with building rational agents — systems that perceive their environment through sensors and act through actuators so as to maximise their expected performance measure. It covers thinking/acting humanly (cognitive modelling, Turing Test) and thinking/acting rationally (logic- and utility-based decision making).

Ans: The Turing Test (Alan Turing, 1950) is a test of a machine's ability to exhibit intelligent behavior indistinguishable from that of a human through natural language text interaction.

Ans: An Intelligent Agent is anything that perceives its environment through sensors and acts upon it through actuators, defined abstractly by an agent function \(f : P^{*} \to A\) mapping every percept sequence to an action. It is rational if, for each percept sequence, it selects the action expected to maximise its performance measure given its built-in knowledge.

Ans: PEAS is the standard specification of a task environment written before designing an agent: Performance measure, Environment, Actuators and Sensors. For an automated taxi — performance: safe, fast, legal, comfortable trip; environment: roads, traffic, pedestrians; actuators: steering, accelerator, brake, horn; sensors: cameras, GPS, speedometer.

Ans: The Environment is everything external to the agent that it perceives through its sensors and can alter through its actuators; together with the performance measure it forms the task environment. Environments are classified as fully/partially observable, deterministic/stochastic, episodic/sequential, static/dynamic, discrete/continuous and single-agent/multi-agent.

Ans: An environment is Fully Observable if the agent's sensors give it access to the complete state of the environment at each point in time, so it need not maintain any internal state to keep track of the world. Example: chess with a visible board.

Ans: An environment is Partially Observable when noisy, inaccurate or incomplete sensors leave part of the state hidden, so the agent must maintain an internal belief state of the world. Example: an automated taxi that cannot sense what other drivers intend, or poker with hidden cards.

Ans: An environment is Deterministic if the next state is completely determined by the current state and the action executed by the agent, i.e. \(s' = T(s,a)\) with no element of chance. Example: the 8-puzzle or the simple vacuum-cleaner world.

Ans: An environment is Stochastic when the same action taken in the same state may lead to different next states, so outcomes must be described by a probability distribution \(P(s' \mid s, a)\). Example: taxi driving, where a tyre may burst or traffic may behave unpredictably.

Ans: The State Space is the set of all states reachable from the initial state by any legal sequence of actions. It forms a graph whose nodes are states and whose directed edges are actions, and a solution to the problem is a path in this graph from the initial state to a goal state.

Ans: The Initial State \(s_0\) is the state in which the agent begins problem solving, while a Goal State is any state satisfying the goal test. There may be many goal states, specified either explicitly (a listed configuration) or by an abstract property, e.g. "checkmate" in chess.

Ans: Path Cost is a function \(g(n)\) that assigns a numeric cost to a path from the initial state to node \(n\). It is normally additive, being the sum of the individual step costs, \(g(n) = \sum_i c(n_{i-1}, a_i, n_i)\), and an optimal solution is a path of minimum path cost.

Ans: Uninformed (Blind) Search uses only the information contained in the problem definition — it can generate successors and test whether a state is a goal, but has no domain-specific estimate of how close a state is to the goal. Examples: BFS, DFS, Depth-Limited Search, Uniform Cost Search and Iterative Deepening (IDDFS).

Ans: Informed (Heuristic) Search uses problem-specific knowledge in the form of a heuristic \(h(n)\) that estimates the cost from node \(n\) to the goal, and expands nodes in order of that estimate, so it reaches the goal far more efficiently than blind search. Examples: Greedy Best-First Search and A\(^{*}\) Search.

Ans: A Heuristic Function \(h(n)\) is a problem-specific function that estimates the cheapest cost of a path from node \(n\) to a goal state, with \(h(n) = 0\) at every goal node. It injects domain knowledge into an informed search — e.g. straight-line distance for route finding, or number of misplaced tiles / Manhattan distance for the 8-puzzle.

Ans: An Admissible Heuristic \(h(n)\) never overestimates the true minimal cost of reaching the goal from node \(n\): \(h(n) \le h^{*}(n)\) for all nodes \(n\), i.e. it is always optimistic. Admissibility is the condition that guarantees A\(^{*}\) tree search returns an optimal solution.

Ans: A Consistent (Monotonic) Heuristic obeys the triangle inequality \(h(n) \le c(n, a, n') + h(n')\) for every node \(n\) and every successor \(n'\) generated by action \(a\), with \(h(g) = 0\) at a goal. Consistency makes \(f(n) = g(n) + h(n)\) non-decreasing along any path and implies admissibility, so it is the stronger condition, guaranteeing optimality of A\(^{*}\) graph search.

Ans: Breadth-First Search expands the shallowest unexpanded node first, using a FIFO queue as its frontier. It is complete and is optimal when every step cost is equal, but requires time and space \(O(b^{d})\), where \(b\) is the branching factor and \(d\) the depth of the shallowest goal — memory is its limiting factor.

Ans: Depth-First Search expands the deepest unexpanded node first, using a LIFO stack (or recursion). Its advantage is linear space \(O(bm)\), but it is neither complete (it can loop forever in cyclic or infinite spaces) nor optimal, with worst-case time \(O(b^{m})\).

Ans: Uniform Cost Search expands the frontier node with the lowest path cost \(g(n)\), using a priority queue ordered by \(g\) and applying the goal test when a node is selected for expansion rather than when generated. It is complete and optimal for non-negative step costs bounded below by some \(\epsilon > 0\), and is exactly A\(^{*}\) with \(h(n) = 0\).

Ans: A\(^{*}\) Search is a best-first search that always expands the node with the smallest evaluation \(f(n) = g(n) + h(n)\), where \(g(n)\) is the cost already incurred to reach \(n\) and \(h(n)\) the estimated cost from \(n\) to the goal. It is complete and optimal when \(h\) is admissible (tree search) or consistent (graph search), and is optimally efficient — no other optimal algorithm expands fewer nodes for the same heuristic.

Ans: Greedy Best-First Search expands the node that appears nearest the goal, ordering the frontier by the heuristic alone, \(f(n) = h(n)\), and ignoring the cost \(g(n)\) already spent. This makes it fast but neither optimal nor complete (it can follow a false trail or loop) — precisely the difference from A\(^{*}\), which adds \(g(n)\).

Ans: Hill Climbing is a local search that keeps only the current state and repeatedly moves to the neighbour with the best objective value, halting when no neighbour is better. It maintains no search tree and never backtracks ("greedy local search"), so although it uses very little memory it can become stuck at local maxima, plateaux and ridges.

Ans: A Local Maximum is a state whose objective value is higher than that of all its neighbours but lower than the global maximum. Hill climbing terminates there because every available move leads downhill, so it returns a sub-optimal solution.

Ans: A Plateau is a flat region of the state space in which all neighbouring states have the same objective value, so there is no gradient for the search to follow and it wanders aimlessly. A plateau is either a flat local maximum, from which no escape exists, or a shoulder, from which progress uphill is still possible.

Ans: A Ridge is a narrow ascending crest of successively higher states whose slope cannot be followed by the available moves, because every single legal move from a point on the ridge steps downwards. Hill climbing therefore oscillates from side to side and stalls, even though the ridge as a whole slopes upward towards the goal.

Ans: Simulated Annealing is a stochastic local search that picks a random neighbour each iteration: an improving move is always accepted, while a worsening move of size \(\Delta E < 0\) is accepted with probability \(p = e^{\Delta E / T}\). The temperature \(T\) is reduced by a cooling schedule so that bad moves grow rarer, and if \(T\) is lowered slowly enough the algorithm reaches a global optimum with probability approaching 1.

Ans: A Constraint Satisfaction Problem is defined by a set of variables \(X = \{X_1, \ldots, X_n\}\), a domain \(D_i\) of allowed values for each variable, and a set of constraints \(C\) restricting the permissible combinations of values. A solution is a complete assignment to all variables that is consistent with every constraint — e.g. map colouring, N-Queens or cryptarithmetic.

Ans: Backtracking Search is the basic uninformed algorithm for CSPs: a depth-first search that assigns a value to one variable at a time and, whenever a variable has no value left consistent with the current partial assignment, undoes the most recent assignment and tries an alternative. Its efficiency is greatly improved by the MRV and degree heuristics, least-constraining-value ordering and forward checking.

Ans: A Game Tree is a tree whose root is the initial game position, whose nodes are game states, whose edges are legal moves, and whose successive plies alternate between the MAX and MIN players. Its leaves are terminal states labelled with a utility value evaluated from MAX's point of view (e.g. \(+1, 0, -1\)).

Ans: The Minimax Algorithm computes MAX's optimal move under the assumption that MIN also plays optimally, by backing terminal utilities up the game tree — taking the maximum of the children at MAX nodes and the minimum at MIN nodes. It performs a complete depth-first exploration, with time \(O(b^{m})\) and space \(O(bm)\).

Ans: Alpha-Beta Pruning is an adversarial search optimization for minimax game trees that prunes subtrees when \(\alpha \ge \beta\), where \(\alpha\) is max's best guaranteed choice and \(\beta\) is min's best choice.

Ans: In alpha-beta pruning, \(\alpha\) is the value of the best (highest) choice found so far for MAX anywhere along the current path — a lower bound that can only increase — and \(\beta\) is the value of the best (lowest) choice found so far for MIN — an upper bound that can only decrease. They are initialised to \(\alpha = -\infty\), \(\beta = +\infty\), and the remaining branches of a node are cut off as soon as \(\alpha \ge \beta\).

Ans: Knowledge Representation is the sub-field of AI concerned with encoding facts about the world in a formal symbolic form that a machine can store in a knowledge base and reason over by inference. A good scheme must have representational and inferential adequacy plus inferential and acquisitional efficiency; the main schemes are logic, production rules, semantic networks and frames.

Ans: A Knowledge Base is a set of sentences expressed in a knowledge representation language, each asserting some fact about the world (its axioms). A knowledge-based agent uses two operations on it: TELL, which adds a new sentence, and ASK, which queries what follows from it by entailment, \(KB \models \alpha\).

Ans: Propositional Logic is the simplest declarative logic, in which atomic propositions are either true or false and are combined using the connectives \(\neg, \wedge, \vee, \Rightarrow, \Leftrightarrow\), their meaning fixed by truth tables. It is declarative and compositional, but has no objects, variables or quantifiers, so it cannot concisely express facts about classes of objects.

Ans: First-Order Logic (First-Order Predicate Logic) extends propositional logic with an ontology of objects, relations (predicates) and functions, together with variables and the quantifiers \(\forall\) and \(\exists\). It is therefore far more expressive: a single sentence \(\forall x \, (Man(x) \Rightarrow Mortal(x))\) states a rule about every object in the domain.

Ans: The Universal Quantifier \(\forall\) asserts that a sentence holds for every object in the domain — \(\forall x \, P(x)\) is true iff \(P\) is true for every substitution of an object for \(x\). Its natural companion connective is implication, as in \(\forall x \, (King(x) \Rightarrow Person(x))\); using \(\wedge\) instead would wrongly claim that everything is a king.

Ans: The Existential Quantifier \(\exists\) asserts that a sentence holds for at least one object in the domain — \(\exists x \, P(x)\). Its natural companion connective is conjunction, as in \(\exists x \, (Crown(x) \wedge OnHead(x, John))\), and it is dual to the universal quantifier: \(\exists x \, P(x) \equiv \neg \forall x \, \neg P(x)\).

Ans: A sentence is in Conjunctive Normal Form when it is written as a conjunction of clauses, each clause being a disjunction of literals: \((l_{11} \vee \cdots \vee l_{1k}) \wedge \cdots \wedge (l_{n1} \vee \cdots \vee l_{nm})\). Every sentence can be converted into a logically equivalent CNF, and CNF is the required input form for the resolution inference rule.

Ans: Resolution Refutation is proof by contradiction: to establish \(KB \models \alpha\) one converts \(KB \wedge \neg \alpha\) into CNF and repeatedly applies the resolution rule to clause pairs containing complementary literals. Deriving the empty clause \(\square\) shows \(KB \wedge \neg \alpha\) is unsatisfiable and hence proves \(\alpha\); resolution is refutation-complete.

Ans: Unification is the process of finding a substitution \(\theta\) that makes two logical expressions syntactically identical: \(UNIFY(p, q) = \theta\) such that \(p\theta = q\theta\). For example \(UNIFY(Knows(John, x),\, Knows(y, Jane)) = \{x/Jane,\ y/John\}\); the algorithm returns the Most General Unifier (MGU), the unifier that commits to the fewest variable bindings.

Ans: A Horn Clause is a disjunction of literals containing at most one positive literal, e.g. \(\neg P_1 \vee \neg P_2 \vee Q\), which is equivalent to the implication \(P_1 \wedge P_2 \Rightarrow Q\). A clause with exactly one positive literal is a definite clause, and entailment over definite clauses can be decided by forward or backward chaining in time linear in the size of the knowledge base.

Ans: Forward Chaining is data-driven, bottom-up inference: beginning from the known facts in the KB it repeatedly fires every rule whose premises are all satisfied and adds the conclusion as a new fact, until the query is derived or no further fact can be inferred. It is sound and complete for definite clauses, but may generate many conclusions irrelevant to the goal.

Ans: Backward Chaining is goal-driven, top-down inference: it starts from the query, finds rules whose conclusion unifies with it, and recursively proves each premise of those rules as a sub-goal until known facts are reached. It touches only goal-relevant facts and is the inference mechanism underlying logic programming (Prolog).

Ans: A Semantic Network is a graphical knowledge representation in which nodes denote objects, concepts or events and labelled directed arcs denote binary relations between them, chiefly IS-A (subclass/instance) and HAS-A (property) links. Properties are obtained by inheritance down the IS-A links, e.g. Sparrow IS-A Bird inherits "can fly".

Ans: A Frame (Minsky, 1975) is a structured record that represents a stereotyped object or situation as a collection of named slots with their fillers — values, defaults, constraints or procedural attachments (IF-NEEDED / IF-ADDED demons). Frames are organised in an is-a hierarchy so that a child frame inherits the slots of its parent, e.g. a Car frame with Wheels = 4, Fuel = Petrol.

Ans: Bayes' Theorem relates the posterior probability of a hypothesis to its prior and the likelihood of the evidence: \(P(H \mid E) = \dfrac{P(E \mid H)\, P(H)}{P(E)}\). It lets an agent convert the causal probability \(P(E \mid H)\), which is easy to obtain, into the required diagnostic probability \(P(H \mid E)\), and is the foundation of reasoning under uncertainty.

Ans: A Bayesian (Belief) Network is a directed acyclic graph whose nodes are random variables and whose edges denote direct conditional dependence, each node carrying a Conditional Probability Table \(P(X_i \mid Parents(X_i))\). Because every variable is conditionally independent of its non-descendants given its parents, it represents the full joint distribution compactly as \(P(x_1, \ldots, x_n) = \prod_{i=1}^{n} P(x_i \mid parents(X_i))\).

Ans: Fuzzy Logic (Zadeh, 1965) is a many-valued logic in which the truth of a proposition is a degree in the continuous interval \([0,1]\) instead of a crisp \(\{0,1\}\). It therefore models vague linguistic terms such as "tall", "hot" or "very dirty", with the standard operations \(\mu_{A \cap B} = \min(\mu_A, \mu_B)\), \(\mu_{A \cup B} = \max(\mu_A, \mu_B)\) and \(\mu_{\bar{A}} = 1 - \mu_A\).

Ans: A Membership Function \(\mu_A(x) : X \to [0,1]\) assigns to each element \(x\) of the universe of discourse \(X\) its degree of membership in the fuzzy set \(A\), where 0 denotes no membership and 1 full membership. Typical shapes are triangular, trapezoidal, Gaussian and sigmoidal; a crisp set is the special case in which \(\mu_A(x) \in \{0,1\}\).

Ans: An Expert System is an AI program that emulates the decision-making ability of a human expert within a narrow domain, built from a knowledge base of domain rules and facts plus an inference engine that applies them, supported by a user interface and an explanation facility. Classic examples are MYCIN (diagnosis of blood infections) and DENDRAL (molecular structure).

Ans: An Expert System Shell is an expert system with its domain knowledge removed — it supplies the ready-made inference engine, user interface, explanation facility and knowledge-base editor, so a developer need only add the domain-specific rules. This sharply reduces development effort; the classic example is EMYCIN, the shell derived from MYCIN.

Understanding the PEAS Model

The PEAS (Performance, Environment, Actuators, Sensors) model is a formal specification used to design and define an intelligent agent's task environment before constructing the agent itself. A clearly defined task environment ensures that the agent can make rational decisions to maximize its performance measure.

• Performance Measure (P): The objective criterion used to evaluate the agent's success or behavior.
• Environment (E): The external conditions and entities the agent interacts with and operates within.
• Actuators (A): The mechanisms or effectors the agent uses to perform actions and alter the environment.
• Sensors (S): The devices or inputs through which the agent perceives the state of the environment.

Examples of PEAS Specifications

Classification of Agent Task Environments

An intelligent agent's design is heavily influenced by the properties of the environment it operates in. These properties dictate the complexity of the algorithms required for perception, reasoning, and action.

• Fully Observable vs. Partially Observable:
  • Fully Observable: The agent's sensors give it access to the complete state of the environment at each point in time (e.g., Chess, Checkers). The agent doesn't need internal state to keep track of the world.
  • Partially Observable: The agent cannot sense the complete state of the environment due to noisy/inaccurate sensors or parts of the state being hidden (e.g., Poker, Automated Taxi).
• Deterministic vs. Stochastic:
  • Deterministic: The next state of the environment is completely determined by the current state and the exact action executed by the agent (e.g., Sudoku, Chess).
  • Stochastic: The next state involves randomness or uncertainty, meaning an action doesn't guarantee a single specific outcome (e.g., Ludo (due to dice), Automated Taxi (due to unpredictable traffic)).
• Static vs. Dynamic:
  • Static: The environment does not change while the agent is deliberating or computing its next action (e.g., Crossword puzzle, Medical Diagnosis).
  • Dynamic: The environment changes continuously even while the agent is thinking. The agent must make decisions in real-time (e.g., Automated Taxi, Multiplayer Action Games).
  • Semi-Dynamic: The environment itself doesn't change, but the agent's performance score decreases over time (e.g., Timed Chess).

Uninformed Search Algorithms

Uninformed Search (Blind Search) algorithms have no domain-specific knowledge about how far a state is from the goal. They solely use the problem definition (initial state, actions, transition model, and goal test) to systematically explore the state space.

• Breadth-First Search (BFS):
  • Mechanism: Expands the shallowest unexpanded node first. Implemented using a FIFO queue.
  • Properties: Complete (always finds a solution if one exists) and Optimal (finds the shallowest goal if step costs are uniform).
  • Complexity: Time \(O(b^d)\), Space \(O(b^d)\) — where \(b\) is branching factor, \(d\) is depth. Huge memory requirement is its main drawback.
• Depth-First Search (DFS):
  • Mechanism: Expands the deepest unexpanded node first along the current path. Implemented using a LIFO stack (or recursion).
  • Properties: Not complete (can get stuck in infinite loops) and Not optimal (might find a deeper solution first).
  • Complexity: Time \(O(b^m)\), Space \(O(bm)\) — where \(m\) is max depth. Very memory efficient compared to BFS.
• Depth-Limited Search (DLS):
  • Mechanism: A variant of DFS where a predetermined depth limit \(l\) is imposed to prevent the algorithm from traversing infinite paths.
  • Properties: Complete only if the goal depth \(d \le l\). Not optimal.
• Iterative Deepening DFS (IDDFS):
  • Mechanism: Repeatedly applies Depth-Limited Search, incrementing the depth limit \(l\) (\(l = 0, 1, 2, \dots\)) until a goal is found.
  • Properties: Combines the benefits of BFS and DFS. It is Complete and Optimal (like BFS) but has the low memory footprint of DFS (\(O(bd)\)).

A* Search Algorithm

A* Search is the most widely known form of Best-First Search. It is an informed (heuristic) search algorithm that efficiently finds the optimal path from the start node to a goal node by combining the actual cost reached so far with the estimated cost to the goal.

The core of A* is its Evaluation Function \(f(n)\):

• \(g(n)\): The exact path cost from the start node to the current node \(n\).
• \(h(n)\): The heuristic function; the estimated cheapest cost from node \(n\) to the goal.
• \(f(n)\): The estimated total cost of the cheapest solution path that passes through node \(n\).

Mechanism & Optimality: A* maintains an Open List (priority queue sorted by \(f(n)\)) and a Closed List. It always expands the node with the lowest \(f(n)\) value. A* is guaranteed to be Complete (will find a goal if one exists) and Optimal (will find the shortest/cheapest path) provided that the heuristic function \(h(n)\) is admissible (never overestimates the cost) and consistent.

Heuristic Conditions: Admissibility and Consistency

For heuristic search algorithms like A* to guarantee finding the optimal (cheapest) path, the heuristic function \(h(n)\) must satisfy specific mathematical properties.

1. Admissibility

A heuristic \(h(n)\) is admissible if it never overestimates the actual minimal cost to reach the goal state from node \(n\). Formally, if \(h^*(n)\) is the true optimal cost from \(n\) to the goal, then:

Admissible heuristics are inherently optimistic because they assume the cost of solving the problem is less than or equal to the actual cost. If \(h(n)\) is admissible, A* search is optimal for tree search.

2. Consistency (Monotonicity)

A heuristic \(h(n)\) is consistent (or monotonic) if, for every node \(n\) and every successor \(n'\) generated by an action \(a\), the estimated cost of reaching the goal from \(n\) is no greater than the step cost of getting to \(n'\) plus the estimated cost from \(n'\) to the goal. Formally, obeying the triangle inequality:

Where \(c(n, a, n')\) is the actual cost of the action. Furthermore, the heuristic value of the goal node must be zero (\(h(Goal) = 0\)).

Relationship: Every consistent heuristic is strictly also admissible. If a heuristic is consistent, the \(f(n)\) values along any path are non-decreasing, making A* optimal even when using graph search (with a closed list) without needing to reopen closed nodes.

Hill Climbing Search and Its Pitfalls

Hill Climbing is a local, informed search algorithm that continuously moves in the direction of increasing value (or decreasing cost). It is a greedy approach that only looks at the immediate neighbors of the current state and selects the one that improves the objective function the most. It does not maintain a search tree, making it highly memory efficient, but it can easily get stuck.

Because it only makes local improvements, Hill Climbing frequently fails to find the global optimum due to the following landscape topologies (pitfalls):

• Local Maxima (or Minima): A state that is better than all of its immediate neighbors, but is strictly worse than the global maximum. The algorithm gets stuck here because every valid move leads to a worse state.
• Plateau (Flat Local Maximum): A flat area of the state-space landscape where a set of neighboring states have exactly the same objective value. The algorithm loses its gradient and performs a random walk, often failing to make progress.
• Ridge: A sequence of local maxima that are connected, forming a sharp elevation. Single-axis moves (typical in hill climbing) cause the algorithm to zig-zag inefficiently back and forth across the ridge without moving along its crest.

Solutions: Random-restart hill climbing, Stochastic hill climbing, or Simulated Annealing can help escape these pitfalls.

Simulated Annealing Search

Simulated Annealing is a probabilistic local search algorithm used to find the global optimum in a large search space while avoiding getting trapped in local maxima. It draws an analogy from metallurgy, where a material is heated to a high temperature and slowly cooled to minimize its thermodynamic free energy (creating a strong crystalline structure).

Unlike standard hill climbing which strictly only accepts moves that improve the state, Simulated Annealing sometimes accepts worse moves to escape local maxima. The probability of accepting a bad move depends on two factors:

1. The magnitude of the bad move (\(\Delta E\)): How much worse the new state is compared to the current state.
2. The current Temperature (\(T\)): A control parameter that decreases over time.

If the new state improves the objective (\(\Delta E > 0\)), it is always accepted. If it is worse (\(\Delta E < 0\)), it is accepted with a probability defined by the Boltzmann distribution:

The Temperature Schedule

The cooling schedule dictates how the temperature \(T\) decreases over time. Initially, \(T\) is high, meaning \(P(\text{accept})\) is close to 1, allowing the algorithm to freely explore the state space (like a random walk) and jump out of local maxima. As time progresses, \(T\) drops towards zero. When \(T\) is very low, the algorithm behaves exactly like strict hill climbing, converging onto the nearest peak.

Constraint Satisfaction Problems (CSP)

A Constraint Satisfaction Problem (CSP) is a mathematical problem defined by a set of variables whose states must satisfy a number of constraints or rules. A CSP is formally defined by three components: \((X, D, C)\).

• \(X\): A set of variables \(\{X_1, X_2, \dots, X_n\}\).
• \(D\): A set of domains \(\{D_1, D_2, \dots, D_n\}\), where \(D_i\) contains the permissible values for variable \(X_i\).
• \(C\): A set of constraints that specify allowable combinations of values for subsets of variables.

A solution to a CSP is a complete, consistent assignment of values to all variables such that no constraint is violated.

N-Queens Problem as a CSP

The objective of the N-Queens problem is to place \(N\) queens on an \(N \times N\) chessboard such that no two queens attack each other (horizontally, vertically, or diagonally).

• Variables (\(X\)): Let \(Q_1, Q_2, \dots, Q_N\) represent the \(N\) queens, where \(Q_i\) is the queen in the \(i\)-th column.
• Domain (\(D\)): The row index where the queen can be placed. \(D_i = \{1, 2, \dots, N\}\).
• Constraints (\(C\)): For any two queens \(Q_i\) and \(Q_j\) (where \(i \neq j\)):
  1. \(Q_i \neq Q_j\) (No two queens in the same row).
  2. \(|Q_i - Q_j| \neq |i - j|\) (No two queens on the same diagonal).

CSP Backtracking Search and Arc Consistency (AC-3)

1. Backtracking Search

Backtracking Search is a specialized Depth-First Search (DFS) algorithm used for solving CSPs. Instead of generating complete states, it assigns values to variables one at a time. After assigning a value to variable \(X_i\), it checks the constraints. If the assignment violates any constraint with previously assigned variables, it abandons the path (backtracks) and tries the next value in \(X_i\)'s domain. This early pruning significantly reduces the search space compared to brute-force generate-and-test methods.

2. Arc Consistency (AC-3 Algorithm)

Constraint propagation techniques are used to reduce the domain of variables before or during search. The most common form is Arc Consistency.

A variable \(X_i\) is arc-consistent with respect to variable \(X_j\) if, for every value \(x\) in the domain of \(X_i\), there exists at least one value \(y\) in the domain of \(X_j\) that satisfies the binary constraint between \(X_i\) and \(X_j\).

The AC-3 Algorithm enforces arc consistency across the entire CSP network:

1. Initialize a queue with all directed arcs \((X_i, X_j)\) in the CSP graph.
2. Pop an arc \((X_i, X_j)\) from the queue and make \(X_i\) arc-consistent with \(X_j\) by removing unsupported values from the domain of \(X_i\).
3. If the domain of \(X_i\) is modified, add all arcs \((X_k, X_i)\) (where \(X_k\) is a neighbor of \(X_i\)) back into the queue because the reduced domain of \(X_i\) might now invalidate previous consistencies.
4. Repeat until the queue is empty. If any domain becomes empty, the CSP has no solution.

Game Playing and the Minimax Algorithm

In AI, game playing is typically modeled as a deterministic, fully observable, zero-sum environment where two agents compete (adversarial search). Examples include Chess, Tic-Tac-Toe, and Checkers. The two players are traditionally called MAX and MIN. MAX attempts to maximize the game score, while MIN attempts to minimize it.

The Minimax Algorithm

The Minimax Algorithm computes the optimal move for MAX by exploring the entire game tree down to the leaf/terminal nodes, assuming MIN plays optimally to oppose MAX.

Steps of Minimax:

1. Generate Tree: Expand the game tree from the current state down to the terminal states (or a depth limit).
2. Evaluate Leaves: Apply a utility function (or heuristic evaluation function) to the terminal nodes to get their scores.
3. Back-propagate Values:
   • If the parent node is a MIN node, it selects the minimum utility value of its children.
   • If the parent node is a MAX node, it selects the maximum utility value of its children.
4. Decision: The root node (MAX's current turn) makes the move associated with the maximum backed-up value.

While Minimax is optimal, its time complexity is \(O(b^m)\), which is impractical for complex games without depth limiting and Alpha-Beta pruning.

Alpha-Beta Pruning in Game Trees

Alpha-Beta Pruning is an optimization for the Minimax algorithm. It dramatically reduces the number of nodes evaluated in the search tree, allowing search to go much deeper within the same time limit.

The Pruning Rules

• Alpha (\(\alpha\)): The best (highest-value) choice found so far at any choice point along the path for MAX. Initialized to \(-\infty\).
• Beta (\(\beta\)): The best (lowest-value) choice found so far at any choice point along the path for MIN. Initialized to \(+\infty\).
• Pruning Condition: Search is pruned (stopped) at a MIN node if its value \(\le \alpha\). Search is pruned at a MAX node if its value \(\ge \beta\). Simply put, prune when \(\alpha \ge \beta\).

Propositional Logic

Propositional Logic (Boolean Logic) is the simplest logic system. It deals with propositions—declarative sentences that are either true (T) or false (F).

Syntax and Logical Connectives

Sentences are built using atomic propositions (e.g., \(P\), \(Q\)) and logical connectives:

• Negation (\(\neg P\)): "Not P". True if \(P\) is false.
• Conjunction (\(P \land Q\)): "P and Q". True only if both \(P\) and \(Q\) are true.
• Disjunction (\(P \lor Q\)): "P or Q". True if at least one of \(P\) or \(Q\) is true.
• Implication (\(P \implies Q\)): "If P then Q". False only when \(P\) is true and \(Q\) is false.
• Biconditional (\(P \iff Q\)): "P if and only if Q". True if \(P\) and \(Q\) have the same truth value.

Truth Table Example

First-Order Logic (FOL)

Unlike Propositional Logic which only sees facts as whole truths, First-Order Logic (FOL) breaks facts down into objects and their relations, making it far more expressive.

Syntax Components

• Constants: Specific objects (e.g., John, Apple).
• Variables: Placeholders for objects (e.g., \(x\), \(y\)).
• Predicates: Relations or properties returning true/false (e.g., \(\text{Loves}(John, Mary)\), \(\text{IsRed}(Apple)\)).
• Functions: Returns an object rather than a truth value (e.g., \(\text{FatherOf}(John)\)).

Quantifiers

FOL introduces two quantifiers to express properties over collections of objects:

1. Universal Quantifier (\(\forall\)): "For all". Used to state that a property holds for every object in the universe.
   Example: "All humans are mortal" \(\implies \forall x (\text{Human}(x) \implies \text{Mortal}(x))\).
2. Existential Quantifier (\(\exists\)): "There exists". Used to state that a property holds for at least one object.
   Example: "Someone loves Mary" \(\implies \exists x (\text{Loves}(x, Mary))\).

Conversion to Conjunctive Normal Form (CNF)

To use automated inference rules like Resolution, FOL sentences must be standardized into Conjunctive Normal Form (CNF), where a sentence is an AND of ORs (a conjunction of clauses).

9-Step Conversion Process

1. Eliminate Implications: Replace \(A \implies B\) with \(\neg A \lor B\).
2. Move Negations Inwards: Apply De Morgan's laws so negations only apply to atomic predicates (e.g., \(\neg \forall x P(x) \rightarrow \exists x \neg P(x)\)).
3. Standardize Variables: Rename variables so each quantifier uses a unique variable name.
4. Skolemization: Eliminate existential quantifiers (\(\exists\)). Replace the existential variable with a Skolem constant or a Skolem function (if it depends on a universal quantifier).
5. Drop Universal Quantifiers (\(\forall\)): Since all remaining variables are universally quantified, simply drop the \(\forall\) symbols.
6. Distribute \(\lor\) over \(\land\): Convert into a conjunction of disjunctions.
7. Flatten Nested Connectives: \((A \land B) \land C \rightarrow A \land B \land C\).
8. Separate Clauses: Break the conjunctions into separate independent clauses.
9. Standardize Variables in Clauses: Rename variables in different clauses to ensure they do not share variables.

Unification in First-Order Logic

Unification is a core algorithmic process in FOL used to find a substitution that makes two different logical expressions structurally identical. It is essential for applying inference rules like Resolution.

A substitution \(\theta\) is called a unifier if \(Expression1\theta = Expression2\theta\). We always seek the Most General Unifier (MGU), which imposes the fewest possible restrictions (substitutions) on the variables.

Examples of Unification

• Example 1 (Constants and Variables):
  Unify \(\text{Knows}(John, x)\) and \(\text{Knows}(y, Mary)\).
  Substitution \(\theta = \{x / Mary, y / John\}\). Result: \(\text{Knows}(John, Mary)\).
• Example 2 (Functions):
  Unify \(\text{Loves}(x, \text{FatherOf}(x))\) and \(\text{Loves}(John, y)\).
  Substitution \(\theta = \{x / John, y / \text{FatherOf}(John)\}\). Result: \(\text{Loves}(John, \text{FatherOf}(John))\).
• Example 3 (Failure):
  Unify \(\text{Knows}(John, x)\) and \(\text{Knows}(x, Mary)\).
  Fails because \(x\) cannot simultaneously be \(John\) and \(Mary\).

Resolution Refutation Principle

Resolution is a sound and complete inference rule used in automated theorem proving. The Resolution Refutation principle proves a theorem by contradiction.

The Refutation Workflow

1. Formulate Knowledge Base (KB): Convert all given facts and axioms into Conjunctive Normal Form (CNF) clauses.
2. Negate the Goal: Take the theorem/goal you want to prove, negate it (\(\neg Goal\)), and convert it to CNF.
3. Add to KB: Add the negated goal to the set of clauses.
4. Resolve: Repeatedly apply the Resolution Rule: if two clauses contain complementary literals (e.g., \(P\) in one and \(\neg P\) in another), resolve them to create a new resolvent clause (combining the rest of the literals).
5. Contradiction (Empty Clause): If the resolution process eventually derives the empty clause (\(\emptyset\) or NIL), it means a contradiction has been found. Therefore, the negated goal is false, proving that the original goal must be True.

Forward vs Backward Chaining

Inference engines in Knowledge-Based (KB) Expert Systems primarily use two reasoning strategies to deduce conclusions from rules (IF-THEN clauses):

Semantic Networks

A Semantic Network is a graphical knowledge representation technique where knowledge is represented as a directed graph.

• Nodes: Represent concepts, objects, or classes (e.g., "Bird", "Penguin", "Wings").
• Edges (Arcs): Represent the semantic relationships between the nodes.

Key Relationships

• IS-A (Inheritance): Represents class hierarchies. E.g., Penguin \(\xrightarrow{\text{IS-A}}\) Bird.
• HAS-A (Possession): E.g., Bird \(\xrightarrow{\text{HAS-A}}\) Wings.
• Action/Property: E.g., Bird \(\xrightarrow{\text{CAN}}\) Fly.

Semantic networks are highly intuitive for humans but lack formal logical semantics, making automated reasoning tricky without strict rules.

Frames and Inheritance

A Frame is a highly structured, object-oriented approach to knowledge representation introduced by Marvin Minsky. A frame represents a stereotyped concept, object, or situation (similar to a 'class' in OOP).

Structure of a Frame

A frame consists of a collection of attributes called Slots. Each slot can have:

• Values: Data assigned to the slot (e.g., Color: Red).
• Facets: Metadata about the slot, such as constraints, default values, or attached procedures (e.g., if-needed, if-added demons).

Inheritance in Frames

Frames are organized into hierarchical taxonomies. A sub-frame inherits slots and default values from its parent frame. For example, a Mammal frame might have a slot Legs: 4. A child frame Dog inherits this slot automatically. However, inheritance can be overridden if a specific child violates the default (e.g., overriding a default inherited property).

Conceptual Dependency (CD) Theory

Conceptual Dependency (CD), developed by Roger Schank, is a theory of Natural Language Processing that represents the underlying semantic meaning of sentences independently of the specific words or syntax used. Two sentences with the same meaning map to the exact same CD structure.

Primitive Actions (ACTs)

CD breaks down all human actions into a small set of foundational primitive actions. Some key ACTs include:

• ATRANS: Transfer of abstract relationship (e.g., give, buy, take).
• PTRANS: Transfer of physical location of an object (e.g., go, fly).
• PROPEL: Application of physical force to an object (e.g., push, pull).
• MTRANS: Transfer of mental information (e.g., tell, hear, read).
• MBUILD: Construction of new information from old (e.g., decide, conclude).
• INGEST / EXPEL: Organism taking in or expelling something (e.g., eat / sweat).
• GRASP: Grasping an object physically.

By mapping sentences to these primitives, the system can draw deep inferences (e.g., if John ATRANS a book to Mary, Mary now possesses the book).

Handling Uncertainty using Bayes' Theorem

In real-world AI, agents rarely have complete and certain knowledge. To handle uncertainty systematically, AI employs probability theory, with Bayes' Theorem at its core. It provides a mathematical framework for updating our belief in a hypothesis given new evidence.

The Mathematical Formula

• \(P(H)\): Prior Probability. The initial degree of belief in hypothesis \(H\) before observing any evidence.
• \(P(E | H)\): Likelihood. The probability of observing evidence \(E\) assuming the hypothesis \(H\) is true.
• \(P(E)\): Marginal Probability. The total probability of observing the evidence under all possible hypotheses. Often calculated using the Law of Total Probability: \(P(E) = P(E | H)P(H) + P(E | \neg H)P(\neg H)\).
• \(P(H | E)\): Posterior Probability. The updated probability of the hypothesis \(H\) after the evidence \(E\) has been observed.

Example: In medical diagnosis, \(H\) is a disease (e.g., Cancer) and \(E\) is a test result. Bayes' theorem allows us to calculate the probability a patient actually has cancer given a positive test result, considering the baseline cancer rate and the test's false-positive rate.

Bayesian Belief Networks (BBN)

A Bayesian Belief Network (or Bayesian Network) is a probabilistic graphical model that represents a set of variables and their conditional dependencies via a Directed Acyclic Graph (DAG).

• Nodes: Represent random variables (discrete or continuous).
• Directed Edges: Represent direct causal influence from parent to child node (e.g., \(A \rightarrow B\) means A directly affects B).

Conditional Probability Tables (CPTs)

Every node in a BBN has an associated Conditional Probability Table (CPT). The CPT quantifies the effect of the parents on that node.

• If a node has no parents (a root node), its CPT simply lists its prior probabilities (e.g., \(P(\text{Burglary})\)).
• If a node has parents, its CPT lists the probability of the node taking on each possible value given every possible combination of values of its parent nodes (e.g., \(P(\text{Alarm} | \text{Burglary}, \text{Earthquake})\)).

Joint Probability: BBNs simplify complex probability distributions. The full joint probability of the network is just the product of the individual CPT entries:

Dempster-Shafer Theory of Evidence

The Dempster-Shafer (D-S) Theory is a mathematical theory of evidence that provides an alternative to traditional probability for handling uncertainty, ignorance, and the fusion of evidence from multiple sources.

Core Concepts

• Frame of Discernment (\(\Theta\)): The set of all possible mutually exclusive hypotheses. E.g., \(\Theta = \{A, B, C\}\).
• Basic Probability Assignment (\(m\)): A mass function that assigns a probability mass to every subset of \(\Theta\). Unlike standard probability, we can assign mass to combinations of hypotheses (e.g., \(m(\{A, B\}) = 0.4\)), representing ignorance between A and B.

Belief and Plausibility

D-S theory bounds the true probability of a hypothesis \(H\) within an interval \([\text{Bel}(H), \text{Pl}(H)]\).

1. Belief (Bel): The lower bound. The sum of the masses of all subsets that are strictly entirely contained within \(H\). It represents the minimum guaranteed support for \(H\).
2. Plausibility (Pl): The upper bound. The sum of the masses of all subsets that intersect with \(H\). It represents the maximum possible support for \(H\).

Example: If \([\text{Bel}(H), \text{Pl}(H)] = [0.2, 0.8]\), it means there is 20% direct evidence for \(H\), but up to 80% could be true if the unknown evidence aligns with \(H\).

Fuzzy Sets vs Crisp Sets

Standard set theory and logic operate on strict binary boundaries. Fuzzy logic introduces degrees of truth.

• Crisp Sets (Classical Logic): An element either entirely belongs to a set or it does not. The membership function \(\mu(x)\) is strictly 0 or 1. (e.g., "Tall" means \(\ge 6\) ft. 5.99 ft is completely NOT tall).
• Fuzzy Sets: An element can partially belong to a set. The membership function \(\mu(x)\) returns a continuous value between 0.0 and 1.0. (e.g., 5.9 ft might have a "Tall" membership degree of 0.8).

Fuzzy Membership Functions

A Membership Function mathematically defines how input values are mapped to a degree of membership between 0 and 1. Common shapes include:

1. Triangular: Peaks at 1.0 and linearly slopes down to 0 on both sides.
2. Trapezoidal: Has a flat top where membership is 1.0, then slopes down to 0.
3. Gaussian (Bell Curve): A smooth curve used for continuous, smooth transitions without sharp edges.

Fuzzy Inference Systems (Mamdani Model)

A Fuzzy Inference System (FIS) maps crisp inputs to crisp outputs using fuzzy logic. The most widely used architecture is the Mamdani Model, which follows a four-step pipeline:

1. Fuzzification: Crisp input values (e.g., Temperature = 32°C) are mapped to degrees of membership in fuzzy sets (e.g., "Hot" = 0.7, "Warm" = 0.2) using membership functions.
2. Rule Evaluation (Inference): Fuzzy IF-THEN rules are evaluated. Fuzzy AND/OR operators are applied (usually MIN for AND, MAX for OR) to calculate the firing strength of the rule. The THEN part is truncated (clipped) by this firing strength.
3. Aggregation: The truncated output fuzzy sets from all triggered rules are combined (usually via a MAX operation) into a single, unified output fuzzy set.
4. Defuzzification: The aggregated output fuzzy set is converted back into a single crisp, numerical value. The most common method is the Centroid (Center of Gravity) method.

Inductive Learning and ID3 Decision Trees

Inductive Learning

Inductive Learning is a supervised machine learning paradigm where an algorithm observes a set of training examples (input-output pairs) and induces a generalized hypothesis or rule that can accurately predict the output for unseen inputs.

Decision Trees & ID3

A Decision Tree is a tree-based classification model where internal nodes represent tests on attributes, branches represent the outcomes of tests, and leaf nodes represent final class labels.

The Iterative Dichotomiser 3 (ID3) algorithm builds decision trees top-down using a greedy approach. It selects the "best" attribute at each node to split the dataset. The best attribute is the one that best separates the data into distinct classes, measured using a metric called Information Gain. ID3 stops splitting when all instances in a branch belong to the same class or there are no more attributes to split on.

Entropy and Information Gain

In decision trees (like ID3), Entropy and Information Gain are mathematical metrics used to decide which feature should be the root or internal node.

1. Entropy \(H(S)\)

Entropy measures the degree of impurity, disorder, or uncertainty in a dataset \(S\). If a dataset is 50/50 split between two classes, entropy is at its maximum (1.0 bits). If all samples belong to one class, entropy is 0.0.

Where \(p_i\) is the proportion (probability) of samples belonging to class \(i\).

2. Information Gain \(IG(S, A)\)

Information Gain measures the expected reduction in entropy (uncertainty) caused by partitioning the dataset \(S\) based on a specific attribute \(A\). We select the attribute that yields the highest Information Gain to split the tree.

Where \(S_v\) is the subset of \(S\) for which attribute \(A\) has value \(v\). It essentially calculates: Original Entropy - Weighted Average Entropy of subsets after splitting.

5 Phases of Natural Language Processing (NLP)

The processing of natural language by AI systems is typically broken down into a pipeline of five distinct phases, moving from raw characters to deep meaning.

1. Lexical / Morphological Analysis: Breaks raw text into smaller tokens (words, paragraphs). It involves stemming and identifying prefixes/suffixes to determine the base word structure.
2. Syntactic Analysis (Parsing): Analyzes the sequence of words to ensure it obeys the grammatical rules of the language. It generates a hierarchical Parse Tree showing relationships between words (e.g., Subject-Verb-Object).
3. Semantic Analysis: Determines the exact dictionary meaning of the sentence. It checks for meaningfulness (e.g., rejecting grammatically correct but nonsensical sentences like "The green idea sleeps furiously") and handles word sense disambiguation.
4. Discourse Integration: Analyzes the meaning of a sentence in the context of the preceding sentences. It resolves anaphoric references (e.g., determining what the pronoun "He" refers to based on the previous sentence).
5. Pragmatic Analysis: Extracts the intended, real-world meaning or intent behind the text, going beyond literal meaning to capture sarcasm, idioms, or contextual implications.

Syntactic Analysis (Parsing) in NLP

Syntactic Analysis, also known as parsing, is the second phase of NLP. It focuses on analyzing the grammatical structure of a sentence to establish the relationships between constituent words.

The parser uses a set of formal grammar rules (usually a Context-Free Grammar (CFG)) to verify if the sentence is grammatically valid. If valid, the output is a hierarchical Parse Tree.

Parsing Approaches

• Top-Down Parsing: Starts at the root symbol (S for Sentence) and expands downward, applying grammar rules to derive the specific words of the input sentence. (Can struggle with left-recursion).
• Bottom-Up Parsing: Starts with the actual input words at the leaves and tries to build the tree upwards by grouping words into phrases (like Noun Phrases and Verb Phrases) until it reaches the root symbol (S).

Parsing is crucial because determining the grammatical subject and verb is a prerequisite for extracting semantic meaning.

Expert System Architecture

An Expert System is an AI application designed to emulate the decision-making ability of a human expert in a specific, narrow domain (e.g., MYCIN for medicine). It structurally separates domain knowledge from the reasoning logic.

Core Components

• Knowledge Base (KB): The heart of the system. It contains the high-quality, domain-specific facts and heuristic rules (often encoded as IF-THEN rules) extracted from human experts.
• Inference Engine: The software "brain" that processes the Knowledge Base. It applies reasoning strategies (like Forward Chaining or Backward Chaining) to deduce new information, solve problems, or provide diagnoses.
• User Interface (UI): The mechanism through which the end-user queries the system, answers questions, and receives the final expert advice.
• Knowledge Acquisition Facility: Tools used by Knowledge Engineers to extract and encode rules from human experts into the KB.

Expert System Shells

An Expert System Shell is a software development environment that contains all the core components of an expert system (inference engine, user interface, explanation facility) except the domain-specific Knowledge Base (KB). It provides a ready-made framework, allowing developers to create an expert system simply by plugging in rules and facts.

Primary Benefits

• Rapid Prototyping and Development: Developers save thousands of hours because they do not have to program the complex inference algorithms (like Rete algorithm) from scratch.
• Domain Focus: Allows Knowledge Engineers to focus entirely on extracting and formatting rules from human experts, rather than debugging software infrastructure.
• Built-in Tools: Shells often come with debugging tools, knowledge acquisition facilities, and conflict-resolution strategies built-in.
• Cost-Effective: Significantly lowers the financial barrier to entry for organizations building specialized AI systems. Examples include CLIPS and JESS.

The Perceptron Model

The Perceptron is the simplest mathematical model of a biological neuron, forming the foundation of Artificial Neural Networks. It acts as a linear binary classifier.

Mathematical Model

Given input signals \(x_1, x_2, \dots, x_n\), the perceptron computes a weighted sum and adds a bias \(b\):

This sum \(z\) is then passed through an Activation Function \(f(z)\) to determine the final output (whether the neuron "fires" or not).

Activation Functions

Activation functions introduce non-linearity, allowing networks to learn complex patterns.

• Step Function: Outputs 1 if \(z \ge 0\), else 0. Used in classical perceptrons.
• Sigmoid: \(\sigma(z) = \frac{1}{1 + e^{-z}}\). Smoothly maps values to a (0, 1) range.
• ReLU (Rectified Linear Unit): \(f(z) = \max(0, z)\). Extremely fast and solves the vanishing gradient problem in deep networks.

Backpropagation Algorithm

Backpropagation (Backward Propagation of Errors) is the fundamental learning algorithm for training Multi-Layer Perceptrons (MLPs). It is an application of the calculus Chain Rule to compute the gradient of the loss function with respect to every weight in the network.

The Three-Phase Workflow

1. Forward Pass: Input data is passed through the network, layer by layer, until an output prediction is generated.
2. Error Computation: The prediction is compared against the actual true target label using a Loss Function (e.g., Mean Squared Error). The difference represents the network's error.
3. Backward Pass (Weight Update):
   • The algorithm calculates the partial derivative (gradient) of the error with respect to the output layer weights.
   • Using the Chain Rule, the error is propagated backward to the hidden layers to calculate their respective gradients.
   • All weights are updated in the opposite direction of the gradient to minimize the error: \(w_{\text{new}} = w_{\text{old}} - \eta \cdot \frac{\partial E}{\partial w}\) (where \(\eta\) is the learning rate).

Genetic Algorithms (GAs)

Genetic Algorithms are heuristic search algorithms inspired by Charles Darwin's theory of natural evolution. They are used to solve optimization and search problems by evolving a population of candidate solutions (chromosomes) over generations.

Core Evolutionary Operators

1. Selection: The process of choosing the fittest individuals (parents) from the current population to breed the next generation. Fitter solutions (determined by a Fitness Function) have a higher probability of being selected (e.g., Roulette Wheel Selection).
2. Crossover (Recombination): The genetic material (bits) of two parent chromosomes is combined to create one or more offspring. E.g., in Single-Point Crossover, a random point is chosen, and the tails of the two parents are swapped. This exploits existing good genes.
3. Mutation: Randomly flipping one or more bits in a child chromosome's sequence with a very low probability. Mutation is crucial because it maintains genetic diversity and prevents the algorithm from converging prematurely on a local maximum.

Reinforcement Learning: Q-Learning

Reinforcement Learning (RL) is a paradigm where an agent learns to behave in an environment by performing actions and observing the resulting rewards/penalties, aiming to maximize cumulative long-term reward.

Q-Learning is a model-free, value-based RL algorithm. The agent maintains a "Q-Table" that stores the Quality (Q-value) of taking a specific action \(a\) in a specific state \(s\).

The Q-Learning Update Rule (Bellman Equation)

• \(Q(s_t, a_t)\): Current Q-value.
• \(\alpha\): Learning Rate (how much new information overrides old).
• \(r_{t+1}\): Immediate reward received after taking action \(a_t\).
• \(\gamma\): Discount Factor (how much future rewards are valued vs immediate rewards).
• \(\max_{a} Q(s_{t+1}, a)\): Estimate of optimal future value from the next state.

The agent balances Exploration (trying random actions to discover rewards) and Exploitation (choosing the action with the highest Q-value) using strategies like \(\epsilon\)-greedy.

Wumpus World and KB Reasoning

The Wumpus World is a classic AI grid-based environment used to demonstrate Knowledge-Based (logical) agents. It is a partially observable, deterministic, and static cave represented as a 4x4 grid.

The Environment

• Threats: The Wumpus (a monster that eats the agent) and Bottomless Pits.
• Goal: Find the Gold and climb out of the cave alive.
• Sensors (Percepts):
  • Stench: Felt in squares adjacent to the Wumpus.
  • Breeze: Felt in squares adjacent to a Pit.
  • Glitter: Seen when in the same square as the Gold.

Knowledge Base Reasoning

The agent navigates using Propositional Logic. It maintains a Knowledge Base (KB) of rules (e.g., \(B_{1,1} \iff (P_{1,2} \lor P_{2,1})\)). If the agent moves to (1,1) and perceives NO breeze (\(\neg B_{1,1}\)), the inference engine applies Modus Tollens to definitively deduce that there is NO pit in (1,2) or (2,1) (\(\neg P_{1,2} \land \neg P_{2,1}\)), marking them as safe to explore.

STRIPS Planning Representation

STRIPS (Stanford Research Institute Problem Solver) is a foundational automated planning system format. It models actions as operators that transition the world from one state to another using sets of logical literals.

Operator Components

Each action schema consists of three strict lists:

1. Preconditions: What must be strictly true in the current state for the action to be legally executed. (e.g., To pick up block A, it must be CLEAR(A) and the robot arm must be EMPTY).
2. Delete List: The facts that become false after the action is executed and must be removed from the state description. (e.g., After picking up A, EMPTY is deleted, and ON(A, Table) is deleted).
3. Add List: The new facts that become true and are added to the state. (e.g., HOLDING(A) is added).

The successor state is calculated purely symbolically: \(S_{\text{new}} = (S_{\text{old}} - \text{DeleteList}) \cup \text{AddList}\).

Goal Stack Planning

Goal Stack Planning is an early linear planning algorithm that uses a LIFO stack to manage the achievement of complex, compound goals (like those in the Block World domain).

How it Works

1. The original compound goal (e.g., \(\text{ON}(A, B) \land \text{ON}(B, C)\)) is pushed onto the stack.
2. The algorithm splits the compound goal into individual sub-goals and pushes them onto the stack individually.
3. When the top of the stack is a goal that is not true in the current state, the planner pushes the corresponding STRIPS action (that has an ADD list satisfying the goal) onto the stack.
4. It then immediately pushes the Preconditions of that action onto the stack as new sub-goals.
5. When an action reaches the top of the stack and its preconditions are met, the action is executed (popped, state updated, added to the final plan).

Limitation (Sussman Anomaly): Because it plans sub-goals linearly and independently, achieving one sub-goal can sometimes undo the progress of a previously achieved sub-goal, leading to suboptimal plans.

The Knowledge Acquisition Bottleneck

The Knowledge Acquisition Bottleneck refers to the most difficult, time-consuming, and expensive phase of building an Expert System: extracting heuristic knowledge from human experts and formalizing it into machine-readable rules.

Why it Occurs

• Tacit Knowledge: Human experts often use intuition or "gut feeling" accumulated over decades. They struggle to articulate these subconscious decisions as explicit IF-THEN rules.
• Vocabulary Gap: Knowledge Engineers (AI developers) and Domain Experts (Doctors, Geologists) speak different technical languages, leading to misinterpretations.
• Time Constraints: Experts are highly paid and busy; their time is expensive.
• Contradictions: Multiple experts might provide conflicting rules for the exact same edge-case scenario.

This bottleneck historically led to the decline of symbolic Expert Systems in favor of modern Machine Learning, which extracts patterns directly from data rather than relying on human interviews.

Classification vs. Regression in Machine Learning

Both Classification and Regression belong to the Supervised Learning paradigm, meaning they learn from historical datasets where the input data is paired with the correct output labels. The fundamental difference lies in the type of output variable they predict.

Resolution Refutation: Marcus is Dead

Part (a) FOL Conversion and Resolution Proof:

1. Axioms in First-Order Logic (FOL):

1. Marcus was a man: \(\text{Man(Marcus)}\)
2. Marcus was a Pompeian: \(\text{Pompeian(Marcus)}\)
3. All Pompeians were Romans: \(\forall x (\text{Pompeian}(x) \implies \text{Roman}(x))\)
4. Caesar was a ruler: \(\text{Ruler(Caesar)}\)
5. All Romans were either loyal to Caesar or hated him: \(\forall x (\text{Roman}(x) \implies (\text{LoyalTo}(x, Caesar) \lor \text{Hate}(x, Caesar)))\)
6. Everyone is loyal to someone: \(\forall x \exists y (\text{LoyalTo}(x, y))\)
7. People only try to assassinate rulers they are not loyal to: \(\forall x \forall y ((\text{Person}(x) \land \text{Ruler}(y) \land \text{TryAssassinate}(x, y)) \implies \neg \text{LoyalTo}(x, y))\)
8. Marcus tried to assassinate Caesar: \(\text{TryAssassinate(Marcus, Caesar)}\)
9. All men are persons: \(\forall x (\text{Man}(x) \implies \text{Person}(x))\) (Implicit axiom required for chaining)
10. All men are mortal: \(\forall x (\text{Man}(x) \implies \text{Mortal}(x))\) (Given, but 'dead' relies on hate in this specific historical problem variant. We prove 'Marcus hated Caesar' as requested by standard PYQ).

2. Conversion to CNF (Clause Form):

• C1: \(\text{Man(Marcus)}\)
• C2: \(\text{Pompeian(Marcus)}\)
• C3: \(\neg \text{Pompeian}(x_1) \lor \text{Roman}(x_1)\)
• C4: \(\text{Ruler(Caesar)}\)
• C5: \(\neg \text{Roman}(x_2) \lor \text{LoyalTo}(x_2, Caesar) \lor \text{Hate}(x_2, Caesar)\)
• C6: \(\neg \text{Person}(x_3) \lor \neg \text{Ruler}(y_1) \lor \neg \text{TryAssassinate}(x_3, y_1) \lor \neg \text{LoyalTo}(x_3, y_1)\)
• C7: \(\text{TryAssassinate(Marcus, Caesar)}\)
• C8: \(\neg \text{Man}(x_4) \lor \text{Person}(x_4)\)

3. Resolution Steps (Proving Marcus hated Caesar):

• Negate Goal: \(\neg \text{Hate(Marcus, Caesar)}\) (Clause 9)
• Resolve C2 and C3 \(\{x_1 / Marcus\}\) \(\implies\) \(\text{Roman(Marcus)}\) (Clause 10)
• Resolve C10 and C5 \(\{x_2 / Marcus\}\) \(\implies\) \(\text{LoyalTo}(Marcus, Caesar) \lor \text{Hate}(Marcus, Caesar)\) (Clause 11)
• Resolve C11 and C9 \(\implies\) \(\text{LoyalTo(Marcus, Caesar)}\) (Clause 12)
• Resolve C1 and C8 \(\{x_4 / Marcus\}\) \(\implies\) \(\text{Person(Marcus)}\) (Clause 13)
• Resolve C6, C13, C4, and C7 \(\{x_3 / Marcus, y_1 / Caesar\}\) \(\implies\) \(\neg \text{LoyalTo(Marcus, Caesar)}\) (Clause 14)
• Resolve C12 and C14 \(\implies\) \(\emptyset\) (Contradiction!)

Part (b) Unification Algorithm:

Unification is a recursive algorithm that takes two literals as input and returns a substitution (Most General Unifier, MGU) that makes them identical, or reports FAILURE.

• If they are identical constants/variables, return empty substitution \(\{\}\).
• If one is a variable \(x\) and the other is a term \(t\):
  - Check if \(x\) occurs inside \(t\) (Occurs Check). If yes, return FAILURE.
  - Else, return substitution \(\{x/t\}\).
• If they are predicates (e.g., \(P(a,b)\) and \(P(x,y)\)), ensure the predicate names match and arity (number of arguments) match. Recursively unify each argument pair, composing the substitutions.

Alpha-Beta Pruning and Minimax Properties

Part (a) Alpha-Beta Pruning Execution Trace:

Given leaf nodes (L to R): 3, 5, 6, 9, 1, 2, 0, -1.

• Bottom-Up Evaluation:
  - MAXL1 evaluates to \(\max(3, 5) = 5\).
  - MAXL2 evaluates to \(\max(6, 9) = 9\).
  - MIN1 receives 5 and 9. It evaluates to \(\min(5, 9) = 5\).
  - Root MAX receives 5 from the left branch. It updates its \(\alpha = 5\).
  - MAXR1 evaluates to \(\max(1, 2) = 2\).
  - MIN2 evaluates its first child (MAXR1) and gets 2. MIN2's provisional value is now \(\le 2\). Thus, MIN2's \(\beta = 2\).
• Pruning Trigger: At MIN2, \(\alpha = 5\) (from Root) and \(\beta = 2\). Since \(\alpha \ge \beta\) (\(5 \ge 2\)), the remaining children of MIN2 (the MAXR2 branch) are completely pruned. Root MAX ultimately chooses the left branch with a value of 5.

Part (b) Minimax Algorithm Properties:

• Completeness: Yes, it is complete if the game tree is finite (e.g., maximum depth \(m\) is bounded).
• Optimality: Yes, it is optimal against an optimal opponent. If the opponent plays sub-optimally, Minimax still guarantees at least the computed score.
• Time Complexity: \(O(b^m)\), where \(b\) is the legal moves (branching factor) and \(m\) is the maximum depth.
• Space Complexity: \(O(bm)\) if generating all successors at once, or \(O(m)\) if generating them one at a time (like DFS).

Decision Trees: Information Gain and Pruning

Part (a) Information Gain Calculation:

Given Dataset \(S\) with 14 total samples: 9 'Yes' and 5 'No'.

1. Calculate Entropy of the Root Dataset \(H(S)\):
   \(H(S) = - \left(\frac{9}{14}\right) \log_2\left(\frac{9}{14}\right) - \left(\frac{5}{14}\right) \log_2\left(\frac{5}{14}\right) = 0.940 \text{ bits}\)
2. Calculate Expected Entropy after splitting on an Attribute (e.g., 'Wind'):
   Assume 'Wind' splits the data into 8 'Weak' (6 Yes, 2 No) and 6 'Strong' (3 Yes, 3 No).
   \(H(S_{\text{Weak}}) = -\left(\frac{6}{8}\right)\log_2\left(\frac{6}{8}\right) - \left(\frac{2}{8}\right)\log_2\left(\frac{2}{8}\right) = 0.811\)
   \(H(S_{\text{Strong}}) = -\left(\frac{3}{6}\right)\log_2\left(\frac{3}{6}\right) - \left(\frac{3}{6}\right)\log_2\left(\frac{3}{6}\right) = 1.0\)
   \(H(S | \text{Wind}) = \left(\frac{8}{14} \times 0.811\right) + \left(\frac{6}{14} \times 1.0\right) = 0.892\)
3. Calculate Information Gain:
   \(IG(S, \text{Wind}) = H(S) - H(S | \text{Wind}) = 0.940 - 0.892 = 0.048 \text{ bits}\)

The ID3 algorithm calculates the Information Gain for every attribute (Outlook, Temp, Humidity, Wind) and selects the one with the highest IG as the root node. It then recursively applies this process to the child subsets.

Part (b) Overfitting and Pruning:

• Overfitting: Occurs when a decision tree grows too deep and complex, memorizing the noise and outliers in the training data rather than generalizing the underlying pattern. An overfitted tree performs perfectly on training data but poorly on unseen test data.
• Pruning: The solution to overfitting. It reduces the size of decision trees by removing sections of the tree that provide little power to classify instances.
  • Pre-pruning: Halts tree construction early (e.g., stopping when a node has fewer than \(N\) samples, or when Information Gain falls below a threshold).
  • Post-pruning: Grows the tree to its maximum depth, then works bottom-up, collapsing leaf nodes into their parents if the removal does not decrease classification accuracy on a validation set.

Bayesian Networks and Naive Bayes

Part (a) Bayesian Network Joint Probability:

Given a Burglar Alarm network with variables: Burglary (\(B\)), Earthquake (\(E\)), Alarm (\(A\)), JohnCalls (\(J\)), MaryCalls (\(M\)).

Network topology: \(B\) and \(E\) are independent root nodes pointing to \(A\). \(A\) points to both \(J\) and \(M\).

Goal: Calculate the joint probability \(P(B \land \neg E \land A \land J \land \neg M)\).

Using the chain rule parameterized by the BBN topology, the joint probability factors as:

Assuming standard Pearl's network CPT values:

• \(P(B) = 0.001\)
• \(P(\neg E) = 1 - P(E) = 1 - 0.002 = 0.998\)
• \(P(A | B, \neg E) = 0.94\)
• \(P(J | A) = 0.90\)
• \(P(\neg M | A) = 1 - P(M | A) = 1 - 0.70 = 0.30\)

Calculation: \(0.001 \times 0.998 \times 0.94 \times 0.90 \times 0.30 = 0.0002532924 \approx 0.000253\)

Part (b) Naive Bayes Classifier for Text Classification:

The Naive Bayes Classifier is based on applying Bayes' theorem with a strong (naive) assumption of conditional independence between the features (words) given the class label (e.g., Spam or Ham).

• It calculates the prior probability of each class \(P(\text{Class})\) from the training data frequency.
• It calculates the likelihood of each word occurring in that class \(P(\text{Word}_i | \text{Class})\). Laplace Smoothing is often used to prevent zero probabilities for unseen words.
• To classify a new email, it multiplies these probabilities together and selects the class with the highest posterior probability (Maximum A Posteriori - MAP).

A* Search Trace and Optimality Proof

Part (a) Tracing A* Search:

A* evaluates nodes using \(f(n) = g(n) + h(n)\).

• Initialization: Open List = \([S (f = 0 + h(S))]\), Closed List = \([]\)
• Step 1: Pop \(S\) from Open. Generate successors. Calculate \(g\), \(h\), and \(f\) for each. Add successors to Open. Add \(S\) to Closed.
• Step 2: Sort Open List by lowest \(f(n)\). Pop the node with the lowest \(f(n)\). If it's a Goal, terminate and retrace path.
• Step 3: If not a goal, generate its successors. If a successor is already in Open or Closed with a higher \(g(n)\) cost, update its parent pointer and lower its \(g(n)\) (and \(f(n)\)). Re-push to Open.

Part (b) Proof of Optimality for A* (Tree Search):

Theorem: A* search is optimal if the heuristic \(h(n)\) is admissible (i.e., \(h(n) \le h^*(n)\) for all \(n\), where \(h^*(n)\) is the true optimal cost).

Proof by Contradiction:

1. Assume A* returns a suboptimal goal node \(G_2\) with path cost \(f(G_2) = g(G_2) > C^*\) (where \(C^*\) is the optimal cost). Since it's a goal, \(h(G_2) = 0\).
2. Let \(G_1\) be the true optimal goal node, so \(f(G_1) = g(G_1) = C^*\).
3. Before \(G_2\) was chosen for expansion, there must have been an unexpanded node \(n\) on the Open list that is on the optimal path to \(G_1\).
4. Because \(h(n)\) is admissible, \(f(n) = g(n) + h(n) \le C^*\).
5. From step 1, we know \(f(G_2) > C^*\).
6. Therefore, \(f(n) < f(G_2)\).
7. Since A* always expands the node with the lowest \(f\)-value, it should have expanded \(n\) before \(G_2\).
8. This contradicts the assumption that A* selected \(G_2\) while \(n\) was on the Open list. Thus, A* must never return a suboptimal goal. \(\blacksquare\)

CSP Map Coloring and Arc Consistency (AC-3)

Part (a) CSP Map Coloring Formulation:

Suppose we have 4 adjacent regions: \(A, B, C, D\) (e.g., \(A\) neighbors \(B, C, D\); \(B\) neighbors \(A, C\); \(C\) neighbors \(A, B, D\); \(D\) neighbors \(A, C\)). We must color them using 3 colors: Red, Green, Blue.

• Variables (\(X\)): \(\{A, B, C, D\}\)
• Domain (\(D\)): \(\{R, G, B\}\) for all variables.
• Constraints (\(C\)): Adjacent regions must have different colors. \(\{A \neq B, A \neq C, A \neq D, B \neq C, C \neq D\}\)

Part (b) Tracing AC-3 Algorithm:

AC-3 enforces arc consistency by ensuring that for every directed arc \((X_i, X_j)\), every value in \(D_i\) has a valid corresponding value in \(D_j\).

1. Initialization: Insert all arcs into a Queue: \((A,B), (B,A), (A,C), (C,A), (A,D), (D,A), (B,C), (C,B), (C,D), (D,C)\).
2. Initial Check: All domains are \(\{R, G, B\}\). For any arc, say \((A,B)\), if \(A=R\), \(B\) can be \(G\) or \(B\). Thus, no values violate the constraints initially. The graph is initially arc-consistent.
3. Constraint Propagation (During Search): Assume we assign \(A = Red\).
4. The domain of \(A\) becomes \(\{R\}\).
5. Queue contains \((B,A)\). To make \(B\) consistent with \(A\), we must remove \(R\) from \(B\)'s domain. \(D_B\) becomes \(\{G, B\}\).
6. Queue contains \((C,A)\). Remove \(R\) from \(C\)'s domain. \(D_C\) becomes \(\{G, B\}\).
7. Queue contains \((D,A)\). Remove \(R\) from \(D\)'s domain. \(D_D\) becomes \(\{G, B\}\).
8. Because \(D_B, D_C, D_D\) changed, we re-evaluate their arcs. e.g., Arc \((B,C)\). If \(B=G\), \(C\) can be \(B\). If \(B=B\), \(C\) can be \(G\). No further domain reductions occur yet until another assignment is made.

Simulated Annealing in Detail

Part (a) Simulated Annealing Algorithm:

Simulated Annealing avoids local maxima by probabilistically accepting worse states. The probability of acceptance decreases as the system "cools" down.

Part (b) Calculating Acceptance Probability \(P = e^{\frac{\Delta E}{T}}\):

Assume a "bad move" where the new state is worse by an energy difference of \(\Delta E = -5\).

• At high temperature (\(T = 100\)):
  \(P = e^{-5 / 100} = e^{-0.05} \approx 0.9512\) (95.12% chance to accept the bad move). The algorithm explores freely.
• At medium temperature (\(T = 10\)):
  \(P = e^{-5 / 10} = e^{-0.5} \approx 0.6065\) (60.65% chance to accept). Exploration decreases.
• At low temperature (\(T = 1\)):
  \(P = e^{-5 / 1} = e^{-5} \approx 0.0067\) (0.67% chance to accept). The algorithm has essentially converged into a greedy hill-climbing search.

Resolution Refutation: John is a Criminal

Part (a) FOL Conversion:

1. It is a crime for an American to sell weapons to hostile nations:
   \(\forall x \forall y \forall z ((\text{American}(x) \land \text{Weapon}(y) \land \text{Sells}(x, y, z) \land \text{Hostile}(z)) \implies \text{Criminal}(x))\)
2. Country Nono has some missiles:
   \(\exists x (\text{Owns}(Nono, x) \land \text{Missile}(x))\). Skolemized to: \(\text{Owns}(Nono, M_1)\) and \(\text{Missile}(M_1)\).
3. All of Nono's missiles were sold to it by John:
   \(\forall x ((\text{Missile}(x) \land \text{Owns}(Nono, x)) \implies \text{Sells}(John, x, Nono))\)
4. Missiles are weapons:
   \(\forall x (\text{Missile}(x) \implies \text{Weapon}(x))\) (Implicit domain knowledge)
5. An enemy of America counts as "hostile":
   \(\forall x (\text{Enemy}(x, America) \implies \text{Hostile}(x))\) (Implicit domain knowledge)
6. Nono is an enemy of America:
   \(\text{Enemy}(Nono, America)\)
7. John is an American:
   \(\text{American}(John)\)

Part (b) Resolution Tree Derivation:

• Negated Goal: \(\neg \text{Criminal}(John)\)
• From (1) and \(\neg \text{Criminal}(John)\) \(\{x/John\}\): We need to prove he is an American, sells a weapon, to a hostile nation. \(\implies \neg \text{American}(John) \lor \neg \text{Weapon}(y) \lor \neg \text{Sells}(John, y, z) \lor \neg \text{Hostile}(z)\)
• Resolve with (7) \(\text{American}(John)\): \(\implies \neg \text{Weapon}(y) \lor \neg \text{Sells}(John, y, z) \lor \neg \text{Hostile}(z)\)
• Resolve with (5) and (6) \(\implies \text{Hostile}(Nono)\) \(\{z/Nono\}\): \(\implies \neg \text{Weapon}(y) \lor \neg \text{Sells}(John, y, Nono)\)
• Resolve with (3) \(\{x/y\}\): \(\implies \neg \text{Weapon}(y) \lor \neg \text{Missile}(y) \lor \neg \text{Owns}(Nono, y)\)
• Resolve with (4): \(\implies \neg \text{Missile}(y) \lor \neg \text{Owns}(Nono, y)\)
• Resolve with (2) \(\{y/M_1\}\): \(\implies \text{Empty Clause} (\emptyset)\). Contradiction found, John is a Criminal.

Fuzzy Logic Controller: Automatic Washing Machine

Part (a) Controller Design:

The goal is to map two crisp inputs (Dirtiness, Fabric Type) to a single crisp output (Wash Time) using a Mamdani Fuzzy Inference System.

• Input 1 (Dirtiness %): Fuzzy sets \(\{Low, Medium, High\}\)
• Input 2 (Fabric Type): Fuzzy sets \(\{Silk (Delicate), Cotton, Jeans (Strong)\}\)
• Output (Wash Time mins): Fuzzy sets \(\{Short, Normal, Long, Very Long\}\)

Part (b) Execution Pipeline:

1. Fuzzification: Assume sensor inputs: Dirtiness = 80%, Fabric = Jeans. By projecting 80% onto the Dirtiness membership functions, we get \(\mu_{High}(Dirt) = 0.8\), \(\mu_{Medium}(Dirt) = 0.2\). For Jeans, \(\mu_{Strong}(Fabric) = 0.9\).
2. Fuzzy Rules Matrix (IF-THEN):
   • IF Dirt is High AND Fabric is Strong THEN Wash Time is Very Long.
   • IF Dirt is Medium AND Fabric is Strong THEN Wash Time is Long.
   • IF Dirt is High AND Fabric is Delicate THEN Wash Time is Normal (to prevent damage).
3. Rule Evaluation (MIN Operator for AND):
   Rule 1 firing strength: \(\min(0.8, 0.9) = 0.8\). Output fuzzy set 'Very Long' is clipped at height 0.8.
   Rule 2 firing strength: \(\min(0.2, 0.9) = 0.2\). Output fuzzy set 'Long' is clipped at height 0.2.
4. Aggregation & Defuzzification (Centroid Method):
   The clipped output sets are unioned together (MAX operator) to form an irregular geometric shape on the Wash Time axis. The crisp wash time is computed by finding the geometric Center of Gravity (Centroid) of this shape on the X-axis: \[ Z = \frac{\sum \mu(z) \cdot z}{\sum \mu(z)} \]
   The result is a precise numerical output (e.g., 55.4 minutes).

Backpropagation Learning Algorithm

Part (a) Overview of Backpropagation:

Backpropagation trains Multi-Layer Perceptrons (MLPs) by propagating the output error backward through the network to update the weights, minimizing the loss function over time.

1. Forward Pass: Inputs are multiplied by weights, passed through activation functions (e.g., Sigmoid), and generate a predicted output \(\hat{y}\).
2. Error Calculation: The Loss \(E\) is calculated. Using Sum of Squared Errors: \(E = \frac{1}{2} (\text{target} - \hat{y})^2\).
3. Backward Pass: Gradients of the loss with respect to every weight are computed using the Calculus Chain Rule.
4. Weight Update: Weights are adjusted against the gradient: \(w_{ij} = w_{ij} - \eta \frac{\partial E}{\partial w_{ij}}\).

Part (b) Derivation using Gradient Descent and Chain Rule:

Let's find the gradient for a weight \(w_{jk}\) connecting a hidden node \(j\) to an output node \(k\).

We need \(\frac{\partial E}{\partial w_{jk}}\). Using the Chain Rule, we expand this across the output node's operations:

• 1. Derivative of Error w.r.t output: \(\frac{\partial (\frac{1}{2}(t_k - \text{out}_k)^2)}{\partial \text{out}_k} = - (t_k - \text{out}_k)\)
• 2. Derivative of output w.r.t net sum (Sigmoid derivative): \(\frac{\partial \sigma(\text{net}_k)}{\partial \text{net}_k} = \text{out}_k (1 - \text{out}_k)\)
• 3. Derivative of net sum w.r.t weight: \(\frac{\partial (\sum w_{jk} \cdot \text{out}_j)}{\partial w_{jk}} = \text{out}_j\) (the input from the previous hidden node)

Multiplying these together yields the local gradient (often denoted as \(\delta_k\)):

The weight is updated as: \(w_{jk}^{\text{new}} = w_{jk}^{\text{old}} + \eta \cdot (t_k - \text{out}_k) \cdot \text{out}_k (1 - \text{out}_k) \cdot \text{out}_j\).

Genetic Algorithm Trace: Optimizing \(f(x) = x^2\)

Part (a) GA Execution Example:

Goal: Maximize \(f(x) = x^2\) for \(0 \le x \le 31\). We represent \(x\) as a 5-bit binary string (chromosome).

1. Initialization: Randomly generate 4 chromosomes.
   C1: 01101 (13) \(\implies f(13) = 169\)
   C2: 11000 (24) \(\implies f(24) = 576\)
   C3: 01000 (8) \(\implies f(8) = 64\)
   C4: 10011 (19) \(\implies f(19) = 361\)
2. Fitness Calculation & Roulette Wheel Selection:
   Total Fitness = \(169 + 576 + 64 + 361 = 1170\).
   Probabilities: \(P(C1)=14\%\), \(P(C2)=49\%\), \(P(C3)=5\%\), \(P(C4)=31\%\).
   Assume the Roulette wheel spins 4 times and selects: C2, C4, C2, C1 (fitter chromosomes are selected more often).
3. 1-Point Crossover:
   Pair 1: C2 (110|00) and C4 (100|11). Crossover point = 3.
   Offspring 1: 11011 (27) \(\implies f = 729\) (Improvement!)
   Offspring 2: 10000 (16) \(\implies f = 256\)
   Pair 2: C2 and C1...
4. Mutation: Randomly flip a bit with low probability (e.g., 0.01). Suppose Offspring 1 mutates at bit 1: 11011 \(\rightarrow\) 11111 (31) \(\implies f=961\).

Through successive generations, the population's average and maximum fitness will converge towards the global optimum (31 in this constrained example).

Q-Learning Manual Trace

Part (a) Environment Setup:

Assume a simple 3x3 grid. The agent starts at (1,1). The Goal is at (3,3) with reward +100. Pits at (2,2) with reward -100. Every regular move has a reward of -1. Discount factor \(\gamma = 0.9\). Learning Rate \(\alpha = 1.0\) (replaces old values entirely).

Part (b) Tracing an Episode:

• All \(Q(s, a)\) in the Q-table are initialized to 0.
• Step 1: Agent in (1,1). Moves Right to (2,1). Receives \(r = -1\). Next state is (2,1).
  \(Q((1,1), R) = -1 + 0.9 \times \max_a Q((2,1), a) = -1 + 0 = -1\).
• Step 2: Agent in (2,1). Moves Up to (2,2) [PIT!]. Receives \(r = -100\). Episode ends.
  \(Q((2,1), U) = -100 + 0 = -100\).
• Next Episode Step 1: Agent in (1,1). Chooses to move Right to (2,1). Receives \(r = -1\).
  \(Q((1,1), R) = -1 + 0.9 \times \max(Q((2,1), R)=0, Q((2,1), U)=-100, \dots)\).
  The max is 0 (moving right from 2,1). So \(Q((1,1), R)\) remains -1. However, the agent has learned to avoid moving Up from (2,1).

Over thousands of episodes, the +100 reward from (3,3) propagates backward through the grid, creating a gradient of Q-values that acts as an optimal policy path.

Converting FOL to Conjunctive Normal Form (CNF)

Let's trace the conversion of the sentence: "Everyone who loves all animals is loved by someone."

1. Initial FOL: \(\forall x (\forall y (\text{Animal}(y) \implies \text{Loves}(x, y)) \implies \exists z \text{Loves}(z, x))\)

2. Eliminate Implications (\(A \implies B \equiv \neg A \lor B\)):

\(\forall x (\neg (\forall y (\neg \text{Animal}(y) \lor \text{Loves}(x, y))) \lor \exists z \text{Loves}(z, x))\)

3. Move Negations Inwards (De Morgan's):

\(\forall x (\exists y (\neg (\neg \text{Animal}(y) \lor \text{Loves}(x, y))) \lor \exists z \text{Loves}(z, x))\)

\(\forall x (\exists y (\text{Animal}(y) \land \neg \text{Loves}(x, y)) \lor \exists z \text{Loves}(z, x))\)

4. Standardize Variables: All variables are already distinct (\(x, y, z\)).

5. Skolemize (Eliminate \(\exists\)): \(y\) and \(z\) are existentially quantified inside the scope of \(\forall x\), so they depend on \(x\). Replace them with Skolem functions \(F(x)\) and \(G(x)\).

\(\forall x ((\text{Animal}(F(x)) \land \neg \text{Loves}(x, F(x))) \lor \text{Loves}(G(x), x))\)

6. Drop Universal Quantifiers:

\((\text{Animal}(F(x)) \land \neg \text{Loves}(x, F(x))) \lor \text{Loves}(G(x), x)\)

7. Distribute \(\lor\) over \(\land\):

\((\text{Animal}(F(x)) \lor \text{Loves}(G(x), x)) \land (\neg \text{Loves}(x, F(x)) \lor \text{Loves}(G(x), x))\)

8. Separate Clauses:

• C1: \(\text{Animal}(F(x)) \lor \text{Loves}(G(x), x)\)
• C2: \(\neg \text{Loves}(x, F(x)) \lor \text{Loves}(G(x), x)\)

PEAS and Environment for a Medical Diagnosis Agent

Part (a) PEAS Description:

• Performance Measure: Accuracy of disease diagnosis, speed of diagnosis, minimizing false positives/negatives, reducing cost of unnecessary tests, improving patient survival rates.
• Environment: Patient (symptoms, vital signs), medical history database, hospital laboratory (test results), medical staff.
• Actuators: Screen display (prescribing treatments, outputting diagnosis, requesting further tests), automated email/pager to doctors.
• Sensors: Keyboard/voice input for symptoms, direct digital feeds from medical equipment (ECG, blood pressure monitor, MRI scanners).

Part (b) Environment Properties:

• Partially Observable: The agent cannot 'see' the internal state of the patient directly; it relies on tests and symptoms which may not reveal everything immediately.
• Stochastic: Diseases and treatments are probabilistic. Administering a drug does not guarantee a 100% specific outcome.
• Sequential: Current decisions (ordering a blood test) affect future percepts and decisions.
• Static: The patient's underlying condition doesn't usually change in the few seconds the agent takes to compute a diagnosis (though it can be dynamic in an ICU setting).
• Continuous: Time, blood pressure, and drug dosages are continuous variables.

Iterative Deepening DFS (IDDFS) vs BFS and DFS

Part (a) Comparison:

Part (b) IDDFS Trace:

IDDFS repeatedly executes Depth-Limited Search (DLS), increasing the depth limit each time.

• Iteration 1 (Limit = 0): Explores only the Root node. If Root != Goal, discard.
• Iteration 2 (Limit = 1): Explores Root, then all nodes at Depth 1 using DFS memory. Discard.
• Iteration 3 (Limit = 2): Explores Root, Depth 1, and Depth 2 nodes. Discard.

Why is it not terribly wasteful? Although IDDFS regenerates the top nodes multiple times, in a tree where branching factor \(b > 1\), the vast majority of nodes are at the bottom layer. The overhead of regenerating the top levels is mathematically negligible compared to the memory savings (e.g., for \(b=10\), 90% of nodes are at the deepest level being searched).

4-Queens Problem as a CSP with Backtracking

Part (a) CSP Formulation for 4-Queens:

• Variables: \(\{Q_1, Q_2, Q_3, Q_4\}\) representing columns 1 to 4.
• Domains: \(\{1, 2, 3, 4\}\) representing the row placement.
• Constraints: No two queens share a row (\(Q_i \neq Q_j\)) or a diagonal (\(|Q_i - Q_j| \neq |i - j|\)).

Part (b) Backtracking Trace:

1. Step 1: Assign \(Q_1 = 1\) (Queen 1 at Row 1). Valid.
2. Step 2: Try \(Q_2 = 1\) (Conflict Row). Try \(Q_2 = 2\) (Conflict Diag). Try \(Q_2 = 3\). Valid.
3. Step 3: Try \(Q_3 = 1, 2, 3, 4\). All conflict! (1: Row, 2: Diag with Q2, 3: Row, 4: Diag with Q2).
4. Step 4 (Backtrack!): Un-assign \(Q_3\). Go back to \(Q_2\). Try the next value for \(Q_2\), which is \(Q_2 = 4\). Valid.
5. Step 5: Try \(Q_3 = 1\) (Conflict Diag), \(Q_3 = 2\). Valid.
6. Step 6: Try \(Q_4 = 1, 2, 3, 4\). All conflict!
7. Step 7 (Backtrack!): Un-assign \(Q_4, Q_3, Q_2\). Go back to \(Q_1\). Try \(Q_1 = 2\).
8. Step 8: Continue forward: \(Q_1 = 2 \implies Q_2 = 4 \implies Q_3 = 1 \implies Q_4 = 3\). Solution found!

Semantic Networks and Frames Representation

Part (a) Scenario: "Tweety is a Canary. Canaries are birds. Birds have wings. Birds can fly. Sylvester is a Cat. Cats eat birds."

Part (b) Semantic Network Construction:

Part (c) Equivalent Frame Representation:

Frame: Bird
  IS-A: Animal
  Has-Part: Wings
  Ability: Fly
Frame: Canary
  IS-A: Bird
  Color: Yellow
Frame: Tweety
  IS-A: Canary
Frame: Cat
  IS-A: Mammal
  Diet: (Eats Bird)
Frame: Sylvester
  IS-A: Cat

Conceptual Dependency (CD) Structure

Part (a) The Sentence: "John gave Mary a book."

Part (b) Conceptual Dependency Analysis:

The verb "gave" implies a transfer of possession. Therefore, the core primitive ACT is ATRANS.

• ACT: ATRANS (Transfer of abstract relationship/possession)
• Actor: John (The entity performing the ATRANS)
• Object: Book (The entity being transferred)
• Recipient (To): Mary
• Donor (From): John

Graphical CD Representation:

John \(\Leftrightarrow\) ATRANS \(\leftarrow \text{O}\) Book \(\leftarrow \text{R}\) (To: Mary, From: John)

(Where \(\Leftrightarrow\) denotes the actor-action relation, \(\leftarrow \text{O}\) denotes the object relation, and \(\leftarrow \text{R}\) denotes the recipient-donor relation).

Inference generated: Because of ATRANS, the system can logically deduce that Mary now possesses the book, and John no longer possesses it, without needing explicit rules for the English word "gave".

Resolution Refutation: Clue (Colonel Mustard)

Part (a) Knowledge Base (Propositional Logic):

1. The murder was committed in the Library or the Conservatory: \(L \lor C\)
2. If the murder was in the Library, then Colonel Mustard did it: \(L \implies M\) \(\equiv\) \(\neg L \lor M\)
3. If the murder was in the Conservatory, then Miss Scarlet did it: \(C \implies S\) \(\equiv\) \(\neg C \lor S\)
4. Miss Scarlet is innocent (she didn't do it): \(\neg S\)

Goal to prove: Colonel Mustard did it (\(M\)).

Part (b) Resolution Proof:

• Step 1: Negate the goal and add to KB. Goal clause: \(\neg M\).
• Step 2: Resolve \((\neg C \lor S)\) with \(\neg S\).
  Result: \(\neg C\) (The murder was not in the Conservatory).
• Step 3: Resolve \((\neg L \lor M)\) with \(\neg M\).
  Result: \(\neg L\) (The murder was not in the Library).
• Step 4: Resolve \((L \lor C)\) with \(\neg C\).
  Result: \(L\) (The murder was in the Library).
• Step 5: Resolve \(L\) (from Step 4) with \(\neg L\) (from Step 3).
  Result: \(\emptyset\) (Contradiction!).

Because the negated goal led to a contradiction, the original goal (\(M\)) must be true. Colonel Mustard did it.

Bayes' Theorem: Medical Test Calculation

Part (a) Problem Statement:

A disease affects 1% of the population. A test for the disease is 99% accurate (True Positive Rate = 0.99, True Negative Rate = 0.99). If a person tests positive, what is the probability they actually have the disease?

Part (b) Application of Bayes' Theorem:

Let \(D\) = Patient has Disease, \(\neg D\) = Patient is Healthy.
Let \(+\) = Test is Positive, \(-\) = Test is Negative.

• Priors: \(P(D) = 0.01\), \(P(\neg D) = 0.99\)
• Likelihoods: \(P(+ | D) = 0.99\) (True Positive), \(P(+ | \neg D) = 0.01\) (False Positive)

We need to find \(P(D | +)\):

First, calculate total probability of a positive test, \(P(+)\):

Now, calculate posterior:

Conclusion: Despite a 99% accurate test, because the disease is so rare (Base Rate Fallacy), a person testing positive only has a 50% chance of actually having the disease. Half of all positive tests are false positives.

Block World and Sussman Anomaly

Part (a) Block World Formulation:

The Block World is a domain where a robotic arm can move uniform blocks on a table.

• Predicates: \(\text{ON}(A, B)\), \(\text{ON}(A, \text{Table})\), \(\text{CLEAR}(A)\), \(\text{HOLDING}(A)\), \(\text{ARMEMPTY}\).
• Actions (STRIPS):
  - Unstack(A, B): Pre: \(\text{ON}(A, B), \text{CLEAR}(A), \text{ARMEMPTY}\). Add: \(\text{HOLDING}(A), \text{CLEAR}(B)\). Delete: \(\text{ON}(A, B), \text{ARMEMPTY}\).
  - Stack(A, B): Pre: \(\text{HOLDING}(A), \text{CLEAR}(B)\). Add: \(\text{ON}(A, B), \text{ARMEMPTY}\). Delete: \(\text{HOLDING}(A), \text{CLEAR}(B)\).

Part (b) Sussman Anomaly in Goal Stack Planning:

Suppose Initial State: \(C\) is on \(A\). \(A\) and \(B\) are on the Table. Goal State: \(A\) on \(B\), and \(B\) on \(C\) (\(\text{ON}(A, B) \land \text{ON}(B, C)\)).

• Goal Stack Planning attempts to solve sub-goals linearly.
• If it tries to achieve \(\text{ON}(A, B)\) first: It clears \(A\) by unstacking \(C\) and putting it on the table. Then it puts \(A\) on \(B\). Now it tries to achieve \(\text{ON}(B, C)\). But to move \(B\), it must unstack \(A\) again! It destroyed its previous progress.
• If it tries to achieve \(\text{ON}(B, C)\) first: It places \(B\) on \(C\). Then it tries to achieve \(\text{ON}(A, B)\). But \(A\) is trapped under \(C\) (which is under \(B\)). It must undo everything.

Resolution: Non-linear planning (like Plan-Space Planning) is required to interleave the steps: Clear \(A\) (put \(C\) on table), then put \(B\) on \(C\), then put \(A\) on \(B\).

Minimax Algorithm for Tic-Tac-Toe

Part (a) Game Representation:

Tic-Tac-Toe is a 2-player zero-sum game. Player X (MAX) aims for +1, Player O (MIN) aims for -1. A draw is 0. The state space contains \(3^9\) possible board configurations, but the actual reachable states are far fewer.

Part (b) Minimax Execution:

• Tree Generation: From an empty board, MAX (X) can place a mark in 9 positions (9 branches). For each branch, MIN (O) has 8 responses. This creates the game tree.
• Leaf Evaluation: The algorithm recursively reaches the end of the game (win, lose, or draw) and assigns a utility score (+1 for X win, -1 for O win, 0 for draw).
• Value Back-propagation:
  - If it is O's turn (MIN node), it looks at all its child board states and selects the minimum score (aiming for -1).
  - If it is X's turn (MAX node), it looks at its children and selects the maximum score (aiming for +1).
• Because Tic-Tac-Toe is perfectly solvable and has a small state space, Minimax can search the entire tree to depth 9. It proves mathematically that optimal play by both sides always results in a Draw (0).

Components of a Natural Language Processing (NLP) System

An NLP system requires several interacting components to map raw text to machine-understandable representations.

1. Lexicon (Dictionary): A database of words, their base forms (lemmas), syntactic categories (Noun, Verb), and semantic meanings.
2. Morphological Analyzer / Tokenizer: Splits text into sentences and words. It uses stemming/lemmatization to reduce words to their root (e.g., "running" \(\rightarrow\) "run").
3. Parser (Syntactic Analyzer): Uses grammar rules (like Context-Free Grammars) to validate sentence structure. Outputs a Parse Tree showing Subject, Verb, Object relationships.
4. Semantic Interpreter: Maps the parse tree to a logical meaning representation (e.g., First-Order Logic or Conceptual Dependency graphs). It handles word sense disambiguation (e.g., "bank" of a river vs financial "bank").
5. Context & Pragmatic Manager: Resolves pronouns across sentences (anaphora resolution) and infers intent based on real-world knowledge (e.g., recognizing that "Can you pass the salt?" is a request, not a yes/no question).
6. Natural Language Generator (NLG): The reverse pipeline. Takes a logical machine concept and translates it back into grammatically correct human text.

Forward vs Backward Chaining Trace

Part (a) Knowledge Base (KB):

R1: IF \(A \land B\) THEN \(C\)
R2: IF \(C\) THEN \(D\)
R3: IF \(A \land E\) THEN \(F\)
Facts: \(A\), \(B\).

Part (b) Forward Chaining (Data-Driven):

Goal: Find all conclusions.

1. Iteration 1: Known facts \(\{A, B\}\). Check rules. R1 condition (\(A \land B\)) is satisfied. Fire R1. Add \(C\) to known facts.
2. Iteration 2: Known facts \(\{A, B, C\}\). R2 condition (\(C\)) is satisfied. Fire R2. Add \(D\) to known facts.
3. Iteration 3: Known facts \(\{A, B, C, D\}\). No more rules can fire (R3 needs \(E\), which is missing). Terminate.

Part (c) Backward Chaining (Goal-Driven):

Goal: Prove \(D\) is true.

1. Check if \(D\) is a known fact. (No).
2. Find a rule that concludes \(D\). R2: IF \(C\) THEN \(D\). New sub-goal: Prove \(C\).
3. Check if \(C\) is a known fact. (No).
4. Find a rule that concludes \(C\). R1: IF \(A \land B\) THEN \(C\). New sub-goals: Prove \(A\), Prove \(B\).
5. Check \(A\). It is a known fact (True). Check \(B\). It is a known fact (True).
6. Since sub-goals \(A\) and \(B\) are true, \(C\) is true. Since \(C\) is true, \(D\) is true. Proof succeeds!

Propositional Logic and Truth Tables

Part (a) Converting English to Logic:

Sentence: "If it rains, the grass is wet. It is raining. Therefore, the grass is wet."

• Let \(R\) = "It rains"
• Let \(W\) = "The grass is wet"
• Premise 1: \(R \implies W\)
• Premise 2: \(R\)
• Conclusion (Theorem): \(W\)

We want to prove that the conclusion logically follows from the premises. This means the implication \(((R \implies W) \land R) \implies W\) must be a Tautology (True in all cases).

Part (b) Truth Table Proof:

Because the final column is entirely True, the argument is logically valid (This specific argument form is known as Modus Ponens).

Artificial Neural Networks (ANN): Architectures

An ANN is a biologically inspired computational model consisting of interconnected artificial neurons organized in layers: an Input layer, one or more Hidden layers, and an Output layer.

1. Feedforward Neural Networks (FNN)

• Architecture: Data strictly flows in one direction—from the input layer, through the hidden layers, directly to the output layer. There are no cycles or loops.
• Memory: They have no internal state or memory. The output for a given input is always the same, regardless of the sequence of previous inputs.
• Use Cases: Image classification, regression tasks, tabular data (e.g., standard Multi-Layer Perceptrons or Convolutional Neural Networks).

2. Recurrent Neural Networks (RNN)

• Architecture: RNNs contain directed cycles. The output of a neuron is fed back into itself or previous layers. This recurrent connection allows information to persist.
• Memory: RNNs maintain a "hidden state" that acts as internal memory, allowing them to process sequences of inputs where temporal context matters.
• Use Cases: Time-series forecasting, Natural Language Processing, Speech recognition (where the current word depends heavily on the previous words). Advanced variants include LSTMs and GRUs to handle long-term dependencies.

Support Vector Machines (SVM)

Support Vector Machine (SVM) is a powerful supervised machine learning algorithm used primarily for classification. Its fundamental objective is to find a line (or hyperplane in higher dimensions) that perfectly separates data points of different classes.

The Hyperplane and Margin

• In a 2D space, the separator is a line. In 3D, it's a plane. In N-D, it's an \((N-1)\)-dimensional Hyperplane.
• There could be infinite lines that separate two clusters of data. SVM doesn't just pick any line; it picks the Optimal Separating Hyperplane.
• Margin Maximization: The optimal hyperplane is the one that has the maximum distance (margin) from the nearest data points of both classes. A larger margin implies better generalization to unseen data.

Support Vectors

The Support Vectors are the specific, critical data points that lie closest to the hyperplane (exactly on the edges of the margin). These points "support" the construction of the hyperplane. If you remove all other data points in the dataset, the position of the hyperplane would not change. The algorithm is highly memory efficient because it only depends on these few support vectors.

Note: If data is not linearly separable, SVM uses the 'Kernel Trick' to map data into a higher-dimensional space where a linear hyperplane can separate them.

Hidden Markov Models (HMM) in AI

A Hidden Markov Model (HMM) is a statistical Markov model where the system being modeled is assumed to be a Markov process with unobserved (hidden) states. It is widely used for sequential data.

Core Components

• Hidden States (\(S\)): The underlying reality we want to discover, but cannot directly observe (e.g., the actual phonemes or words being spoken).
• Observations (\(O\)): The tangible data we can measure (e.g., the acoustic sound waves captured by a microphone).
• Transition Probabilities (\(A\)): The probability of moving from one hidden state to another (e.g., probability that the phoneme /b/ is followed by the phoneme /a/).
• Emission Probabilities (\(B\)): The probability of generating a specific observation given a specific hidden state (e.g., probability that the acoustic wave looks like this when the person is saying the phoneme /b/).

Use in Speech Recognition

In speech recognition, the system receives a sequence of acoustic observations. It uses the Viterbi Algorithm (a dynamic programming algorithm) applied to the HMM to calculate the most probable sequence of hidden states (words) that could have generated those observed sounds.

Unsupervised Learning: K-Means Clustering

Unsupervised Learning deals with unlabeled data. The algorithm must find hidden structure or patterns within the data on its own. The most common technique is clustering.

K-Means Algorithm

K-Means partitions \(N\) observations into \(K\) distinct, non-overlapping clusters. It minimizes the variance (squared distance) between data points and their cluster's center.

The Algorithm Steps:

1. Initialization: The user specifies \(K\) (the number of clusters). The algorithm randomly selects \(K\) data points to act as the initial cluster centers (centroids).
2. Assignment Step: Calculate the Euclidean distance from every data point to all \(K\) centroids. Assign each data point to the cluster of the centroid it is closest to.
3. Update Step: Recalculate the position of each centroid. The new centroid is the mathematical mean (average) of all the data points currently assigned to that cluster.
4. Convergence: Repeat steps 2 and 3 iteratively until the centroids stop moving (or movement is below a tolerance threshold), meaning the assignments are stable.

Drawback: It requires the user to guess the optimal \(K\) beforehand, and is sensitive to the initial random placement of centroids.

Expert Systems and MYCIN

Part (a) Expert System Architecture Recap:

Expert systems consist of a Knowledge Base (facts and heuristics extracted from experts), an Inference Engine (the logic processor using forward/backward chaining), and a User Interface.

Part (b) Case Study: MYCIN (1970s)

MYCIN was one of the earliest and most famous expert systems, developed at Stanford University to diagnose severe bacterial infections (like meningitis) and recommend antibiotic dosages.

• Knowledge Base: Contained around 600 IF-THEN rules representing the heuristic knowledge of expert physicians. (e.g., IF the infection is primary-bacteremia AND the site of culture is a sterile record THEN there is evidence that the organism is bacteroides).
• Inference Engine: Used Backward Chaining. It started with a hypothesis (the patient has a specific infection) and worked backward, asking the doctor via a text interface for lab results to prove the hypothesis.
• Certainty Factors: MYCIN pioneered the use of "Certainty Factors" (CF) ranging from -1.0 (definitely false) to +1.0 (definitely true) to handle the inherent uncertainty of medical diagnoses, long before Bayesian networks became standard.
• Performance: Studies showed MYCIN outperformed junior doctors and was on par with infectious disease experts, though it was never fully deployed in hospitals due to legal and ethical liability issues of the era.