Artificial intelligence

1. (a) Describe the structure of a graph as used in artificial intelligence. [3]
2. (b) Explain how a graph can be used by a delivery robot in a hospital to plan its route. [2]

Roads between five villages in the Swat valley are shown as an undirected weighted graph (distances in km):A – B: 4A – C: 2B – C: 1B – D: 5C – D: 8C – E: 10D – E: 2

1. (a) Use Dijkstra's algorithm to find the shortest distance from village A to each of the other villages. Show the final distance of every node. [4]
2. (b) State the shortest route from A to E. [1]

An undirected weighted graph of five computer-lab buildings is stored in an adjacency matrix (0 means no edge). Rows and columns are in the order K, L, M, N, O:K: 0 6 2 0 0L: 6 0 3 4 0M: 2 3 0 9 8N: 0 4 9 0 2O: 0 0 8 2 0

1. (a) List the edges of the graph with their weights. [2]
2. (b) State which node has the most edges, and how many. [1]
3. (c) Find the shortest distance from K to O and the route. [2]

1. (a) State what g, h and f represent in the A* algorithm. [3]
2. (b) Three nodes are on the open list: X (g = 12, h = 9), Y (g = 15, h = 4), Z (g = 8, h = 14). Calculate f for each and state which node A* expands next. [2]

A courier company in Karachi models roads between its warehouse W and depots P, Q, R, S and T (distances in km, roads are two-way):W – P: 6W – Q: 3P – Q: 2P – R: 5Q – R: 9Q – S: 9R – S: 1R – T: 4S – T: 8

1. (a) Use Dijkstra's algorithm to complete a table showing, for each depot, the shortest distance from the warehouse W and the previous node on the shortest route. [5]
2. (b) State the shortest route from W to T. [1]
3. (c) The road between R and S is closed. State the new shortest distance from W to S. [1]

A robot in a factory in Sialkot plans a route. The undirected weighted graph (costs in metres) is:S – A: 4S – B: 3A – C: 5B – C: 7B – D: 6C – G: 4D – G: 8A – D: 3The heuristic h (estimated straight-line distance to G) is: S 10, A 6, B 8, C 3, D 8, G 0.

1. (a) Use the A* algorithm to find the shortest path from S to G. For each node you visit, show g (cost from S), h and f = g + h, and give the order in which nodes are expanded. [5]
2. (b) Explain why node D was never expanded. [1]

An A* search for a delivery van uses these values (true cost = actual shortest distance to the goal E):Node | h | True costA | 10 | 12B | 8 | 7C | 6 | 9D | 4 | 4E | 0 | 0

1. (a) State what is meant by an admissible heuristic. [1]
2. (b) Using the table, decide whether the heuristic is admissible. Identify any node that breaks the rule. [2]
3. (c) Explain why using a heuristic that overestimates can make A* return a route that is not the shortest. [2]

Travel times (minutes) between junctions in Rawalpindi, roads two-way:A – B: 3A – C: 6B – C: 2B – D: 7C – D: 3C – E: 8D – E: 2D – F: 6E – F: 3

1. (a) Use Dijkstra's algorithm to find the shortest time from A to F and the route. [3]
2. (b) Road works increase the time on edge C–D from 3 to 9 minutes. Find the new shortest time from A to F and the route. [2]
3. (c) Explain why a navigation app must re-run the algorithm when traffic conditions change. [1]

1. (a) Describe two differences between Dijkstra's algorithm and the A* algorithm. [4]
2. (b) Suggest a suitable heuristic for A* in a road-navigation app and explain why it is suitable. [2]

1. (a) A puzzle game has a 3 × 3 sliding-tile board. Explain how the possible positions of the board can be represented as a graph so that an AI can solve the puzzle. [3]
2. (b) Explain why A* with a good heuristic is more suitable than Dijkstra's algorithm for this puzzle. [2]

A route planner for a hiking trail network in the Margalla Hills uses this undirected graph (times in minutes):S – A: 5S – B: 7S – C: 4A – D: 6B – D: 3B – E: 6C – E: 9C – F: 7D – G: 8E – G: 6F – E: 4F – T: 14G – T: 3E – T: 9Heuristic h (estimated minutes to T): S 19, A 14, B 13, C 18, D 10, E 9, F 11, G 3, T 0.

1. (a) Use the A* algorithm to find the shortest path from S to T. Show g, h and f for every node added to the open list, any updated values, and the order in which nodes are expanded. [6]
2. (b) Dijkstra's algorithm makes the nodes permanent in the order S, C, A, B, D, F, E, G, T. Compare this with your answer to part (a) and explain why A* needed to expand fewer nodes. [2]

A one-way road system in a new housing scheme near Lahore is modelled as a directed weighted graph (travel times in minutes; X → Y means you can only drive from X to Y):P → Q: 4P → R: 6Q → R: 3Q → S: 8R → S: 2R → T: 7S → T: 1S → U: 6T → U: 3U → V: 2T → V: 8R → Q: 1V → S: 1

1. (a) Use Dijkstra's algorithm to find the shortest distance from P to every other junction. Show the order in which junctions are made permanent. [5]
2. (b) State the shortest route from P to V. [1]
3. (c) Explain why there is no route from V back to P. [2]

A water pipeline network between pumping stations near Faisalabad (undirected, lengths in km):A – B: 7A – C: 3A – D: 9B – C: 2B – E: 4C – D: 5C – F: 11D – F: 4E – F: 4E – G: 8F – G: 2

1. (a) Apply Dijkstra's algorithm from A. Write the order in which the nodes become permanent and the final distance of each node. [5]
2. (b) State the shortest route from A to G. [1]
3. (c) Each time a node becomes permanent, the algorithm updates its neighbours. State how many times in total a tentative distance is improved (replaced by a smaller value) during the algorithm. [2]

The five-building network from the adjacency matrix below is used to test a shortest-path program. Rows/columns are K, L, M, N, O:K: 0 6 2 0 0L: 6 0 3 4 0M: 2 3 0 9 8N: 0 4 9 0 2O: 0 0 8 2 0

1. (a) Write a program that stores the graph in a 2D list Graph (0 = no edge), a function Dijkstra(Start) that returns a list of shortest distances and a list of previous nodes, and a function Route(Previous, Target) that returns the route as a string such as "K-M-L". The main program must output, for every node, its name, its shortest distance from K and its route. Give the test output. (Python shown; Java or VB.NET solutions are equally acceptable.) [12]

A drone in a crop-spraying project in Punjab plans a flight between waypoints (undirected, costs in units of battery):H – J: 2H – K: 6J – K: 3J – L: 8K – M: 4L – M: 2L – N: 3M – N: 7K – P: 9P – N: 5Heuristic h: H 10, J 10, K 9, L 3, M 5, N 0, P 4.

1. (a) Use A* to find the shortest path from H to N. Show g, h and f for each node you add to the open list and state the order of expansion. [5]
2. (b) Dijkstra's algorithm would make H, J, K, M and L permanent before N. Explain, with reference to the heuristic values, why A* reached N after expanding fewer nodes. [2]

1. (a) Explain the difference between artificial intelligence (AI) and machine learning. [2]
2. (b) State what is meant by deep learning. [2]

An agricultural research institute in Faisalabad uses machine learning to help wheat farmers.

1. (a) Describe supervised learning, using an example from this scenario. [2]
2. (b) Describe unsupervised learning, using an example from this scenario. [2]

A bank in Nairobi is building a machine-learning system to detect fraudulent card payments.

1. (a) Explain the difference between labelled and unlabelled data. [2]
2. (b) Explain why the available data is split into a training set and a test set. [2]

1. (a) For each task, state whether supervised, unsupervised or reinforcement learning is most suitable: (i) an email filter trained on messages marked 'spam' or 'not spam'; (ii) a program that learns to play a racing game by being given points for finishing laps quickly; (iii) grouping news articles into topics without any topic labels; (iv) predicting house prices in Islamabad from past sales. [4]

1. (a) Describe how reinforcement learning could be used to train a robot vacuum cleaner to clean a room efficiently. Use the terms agent, environment, action, reward and policy. [5]

1. (a) Describe the structure of an artificial neural network. [4]
2. (b) Explain how artificial neural networks have helped machine learning. [2]

A single artificial neuron in a fire-alarm system has three inputs x₁, x₂, x₃ (each 0 or 1) with weights 0.6, −0.4 and 0.3, and a bias of −0.5. It outputs 1 if the weighted sum (including the bias) is ≥ 0, and 0 otherwise.

1. (a) Calculate the weighted sum and the output of the neuron for the inputs x₁ = 1, x₂ = 0, x₃ = 1. [2]
2. (b) Calculate the weighted sum and the output for x₁ = 0, x₂ = 1, x₃ = 1. [2]
3. (c) State what happens to the weights during training when the output is wrong. [1]

1. (a) Describe how back propagation of errors is used to train an artificial neural network. [4]

An online clothing store in Lahore has data about 200 000 customers.

1. (a) Describe how unsupervised learning could be used by the store to group its customers, and give one way the store could use the results. [3]
2. (b) Explain why supervised learning could not be used for this task at first. [1]

1. (a) Explain the difference between machine learning and deep learning in the way features are identified. [2]
2. (b) Give two reasons why deep learning needs more computing resources than simpler machine-learning methods. [2]

A small neural network has inputs A and B (0 or 1). Each neuron outputs 1 if its weighted sum (including bias) is ≥ 0, otherwise 0.Hidden neuron h₁: weights 1 (from A), 1 (from B), bias −0.5Hidden neuron h₂: weights 1 (from A), 1 (from B), bias −1.5Output neuron: weights 1 (from h₁), −2 (from h₂), bias −0.5

1. (a) Complete a table showing h₁, h₂ and the output for all four combinations of inputs A and B. [4]
2. (b) Identify the logic function that the network carries out, and explain why a network with a hidden layer is needed for it. [2]

An agricultural extension service in Punjab wants to help farmers who cannot easily reach an expert.

1. (a) Explain how deep learning could be used to build a system that identifies crop diseases from photographs taken by farmers' phones. Refer to the data needed, training, testing and use of the system. [6]

A tutoring centre in Dubai trained a linear regression model to predict test score (y) from hours of study (x): y = 6x + 38. The data used to test it is:Hours | Actual score2 | 494 | 635 | 667 | 82

1. (a) Explain what is meant by regression in machine learning. [2]
2. (b) Use the model to predict the score of a student who studies for 6 hours. [1]
3. (c) Calculate the mean squared error of the model on the four data points. [3]

A perceptron has two inputs with weights w₁ = 0.2 and w₂ = −0.5, and a bias of 0.1 (treated as a weight on a constant input of 1). It outputs 1 if the weighted sum ≥ 0, otherwise 0. The training rule is: new weight = old weight + η × (target − output) × input, with learning rate η = 0.1. A training example has inputs (1, 1) and target output 1.

1. (a) Calculate the output of the perceptron before training for the input (1, 1). [2]
2. (b) Use the training rule to calculate the new values of w₁, w₂ and the bias. [3]
3. (c) Show that the perceptron now gives the target output for this input. [1]

A warehouse robot in Port Qasim is trained by reinforcement learning. Each move costs a reward of −1, reaching the loading bay gives +10, and hitting a shelf gives −10 and ends the episode.Episode 1: 3 moves then reaches the loading bay (rewards −1, −1, −1, +10)Episode 2: 5 moves then reaches the loading bay (rewards −1, −1, −1, −1, −1, +10)Episode 3: 2 moves then hits a shelf (rewards −1, −1, −10)

1. (a) Calculate the total reward for each episode and state which episode the agent should learn to repeat. [3]
2. (b) Explain the difference between exploration and exploitation in reinforcement learning, and why the agent needs both. [3]