GTU 3170716 Artificial Intelligence (AI) Summer 2026 Solved Paper & Solutions

A Perceptron is the simplest form of an Artificial Neural Network (ANN) used for linear binary classification, invented by Frank Rosenblatt in 1958. It consists of input features, associated synaptic weights, a summation function, and an activation (threshold) function.

Mathematical Formulation:

Where $f(z) = 1$ if $z \ge 0$, and $0$ otherwise.

Example (Logic AND Function):

• Inputs: $x_1, x_2 \in \{0, 1\}$
• Weights: $w_1 = 1.0, w_2 = 1.0$, Threshold $\theta = 1.5$
• For $(0,0) \implies 0 - 1.5 = -1.5 < 0 \implies y = 0$
• For $(1,1) \implies (1+1) - 1.5 = +0.5 \ge 0 \implies y = 1$

In Hill Climbing search, three common failure states prevent the algorithm from finding the global optimum:

1. Local Maximum: A state that is better than all its immediate neighbors, but worse than the global maximum. The algorithm stops because no neighboring move improves the heuristic evaluation.
2. Plateau (Flat Maximum): A flat region of the search space where all neighboring states have the exact same heuristic value. The search cannot determine which direction leads uphill and wanders aimlessly.
3. Ridge: A steep slope with a continuous crest that slopes gently upwards. Steps in orthogonal directions move down either side, so single-operator hill climbing gets stuck or oscillates unless multi-directional moves are allowed.

1. Is the problem decomposable into independent subproblems?

• Yes. To move $N$ disks from $A$ to $C$: (1) Move $N-1$ disks from $A$ to $B$, (2) Move disk $N$ from $A$ to $C$, (3) Move $N-1$ disks from $B$ to $C$.

2. Can solution steps be undone (Ignorable, Recoverable, or Irrecoverable)?

• Recoverable. Disks moved between pegs can be moved back to their prior positions at the cost of additional step count. No move causes irreversible damage.

3. Is the universe predictable (Deterministic vs. Non-deterministic)?

• Predictable (Deterministic). Moving a disk from peg $A$ to $B$ produces an exact, certain outcome with zero environmental uncertainty or randomness.

4. Is a good solution absolute or relative?

• Relative (Optimization). Any valid sequence that moves the disks solves the problem, but the optimal solution requires the minimal step count of exactly $2^N - 1$ moves.

5. Is the solution a state or a path?

• Path. The final state (all disks on peg $C$) is trivial and known in advance. The actual solution is the ordered sequence of move operations.

6. What is the role of knowledge (Heuristic Knowledge vs. Formal Rules)?

• Formal Rules. Requires minimal domain knowledge beyond the formal recursive rules and mathematical disk-size constraints.

7. Does the task require interaction with a person (Conversational vs. Solitary)?

• Solitary. The algorithm operates autonomously on the state space without human guidance.

In the Travelling Salesman Problem (TSP), the goal is to find the minimum-cost Hamiltonian cycle visiting every city exactly once and returning to the start.

Standard Heuristic Functions for TSP:

1. Nearest Neighbor Heuristic (Greedy):

• At each unvisited city, greedily select the closest neighboring city with the lowest link cost:

2. Minimum Spanning Tree (MST) Heuristic (Admissible for $A^*$):

• Construct an MST over all remaining unvisited cities plus the current city and start city:

• Property: Since an MST has fewer constraints than a tour, $\text{Cost}(\text{MST}) \le \text{Cost}(\text{Tour})$, guaranteeing $h(n)$ is admissible ($h(n) \le h^*(n)$).

2. Deduce $O$:

• In the thousands column: $S + M + c_3 = O + 10 \cdot c_4 = O + 10$.
• Since $M = 1$, $S + 1 + c_3 = O + 10 \implies S - O = 9 - c_3$.
• If $c_3 = 0$, $S - O = 9 \implies S = 9, O = 0$.
• If $c_3 = 1$, $S - O = 8 \implies S = 9, O = 1$ (impossible, since $M=1$ already).
• Therefore, $O = 0$, $S = 9$, and carry $c_3 = 0$.

3. Deduce $E$ and $N$:

• In hundreds column: $E + O + c_2 = N + 10 \cdot c_3$. Since $O = 0$ and $c_3 = 0$:

• Since $E \ne N$, carry $c_2 = 1$, hence $N = E + 1$.

4. Deduce $R$:

• In tens column: $N + R + c_1 = E + 10 \cdot c_2 = E + 10$.
• Substitute $N = E + 1$:

• If $c_1 = 0$, $R = 9$ (impossible, $S=9$ already).
• Hence carry $c_1 = 1$, which means $R = 8$.

5. Deduce $D, E, Y$:

• In units column: $D + E = Y + 10 \cdot c_1 = Y + 10$ (since $c_1 = 1$).
• Unused digits are $\{2, 3, 4, 5, 6, 7\}$.
• Since $D + E \ge 12$, and $N = E + 1$, test values for $E$:
• If $E = 5$, then $N = 6$.
• Then $D + 5 = Y + 10 \implies D - Y = 5$.
• Choose $D = 7$, then $Y = 2$.
• Digits assigned: $S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2$. All unique!

Morphological Analysis is the first stage in Natural Language Processing (NLP) that analyzes the internal structure of words by decomposing them into their smallest meaningful grammatical units, called morphemes.

Components of Morphemes:

1. Stem / Root: The core base word carrying primary semantic meaning (e.g., play).
2. Affixes (Prefixes & Suffixes): Grammatical attachments modifying meaning or tense:

• Inflectional: Changes tense/plurality without changing word class (e.g., play $+ \text{<code class="solution-code-pill">-ed</code>} \to \text{<code class="solution-code-pill">played</code>}$).
• Derivational: Creates a new word or changes grammatical category (e.g., \text{teach} $+ \text{<code class="solution-code-pill">-er</code>} \to \text{<code class="solution-code-pill">teacher</code>}$).

Example:

1. Initial Population:

• A pool of candidate solutions represented as chromosomes (strings of binary bits or real numbers) is randomly generated.

2. Fitness Function Evaluation:

• Each candidate chromosome is assigned a numeric fitness score $f(x)$ indicating how well it solves the optimization objective.

3. Selection:

• Fittest individuals are proportionally selected to breed offspring (Roulette Wheel Selection, Tournament Selection).

4. Crossover (Recombination):

• Pairs of parent chromosomes exchange genetic material across a crossover point to produce novel offspring:
• Parent 1: 1 1 0 1 | 0 0 $\to$ Child 1: 1 1 0 1 1 1
• Parent 2: 0 0 1 0 | 1 1 $\to$ Child 2: 0 0 1 0 0 0

5. Mutation:

• With a low probability ($p_m \approx 0.01$), random bits in offspring are flipped ($0 \leftrightarrow 1$) to maintain genetic diversity and prevent premature convergence.

6. Termination:

• Repeat steps 2 to 5 across successive generations until an optimal fitness threshold is achieved or generations expire.

1. Forward Pass:

• For input vector $\mathbf{x}$, compute activations layer by layer:

• Compute final network output $\hat{y}$ and loss (e.g., Mean Squared Error):

2. Backward Pass (Error Signal Computation):

• Output Layer Error ($\delta_k$):

• Hidden Layer Error ($\delta_j$):
• Propagate error backward from the next layer $k$:

3. Weight Update Rule (Gradient Descent):

• Update weights and biases using learning rate $\eta$:

Syntax Analysis (Parsing) in Natural Language Processing checks whether a linear sequence of words adheres to the formal grammatical rules of the language, transforming a flat token list into a structured hierarchical Parse Tree.

Key Elements:

• Context-Free Grammar (CFG): Defined by rules $S \to NP \; VP$, $NP \to \text{Det} \; N$, $VP \to V \; NP$.
• Parse Tree Representation:

S
       /   \
      NP    VP
     / \   /  \
   Det  N  V   NP
    |   |  |   | \
   The cat sat on mat

• Validates sentence legality and resolves syntactic ambiguity (e.g., "I saw the man with a telescope").

• Inherited Knowledge for Tommy:
• Tommy has color Brown (direct property).
• Tommy inherits Barks from DOG.
• Tommy inherits Warm-Blooded from MAMMAL.
• Tommy inherits Breathes Oxygen from ANIMAL.