(a) You will investigate various search algorithms for the graph in figure 1. Edges arelabeled with their costs, and heuristic values h for states are labeled next to thestates. S is the start state, and G is the goal state. For each of the following graphsearch strategies, work out the order in which states are expanded, the path returnedby graph search, the path cost, as well as the states that are not expanded. In allsearch algorithms, assume ties are broken in alphabetical order. Draw search tree foreach search strategy to illustrate your answer.Figure 1: Search graph 12 of 5(i) Depth first search [ 3 marks](ii) Breadth First search [ 3 marks](iii) Uniform cost Search [ 4 marks](iv) A* search [4 marks](v) Greedy Search [ 2 marks](b) The heuristic values for the graph in figure 2 are not correct. For which single state (S,A, B, C, D, or G) could you change the heuristic value to make everything admissibleand consistent? What range of values are possible to make this correction? [ 4marks]Figure 2: Search graph 2Question 3(a) Explain the role probability play in Artificial Intelligence. [2 marks](b) Covid-19, Maleria and Paralysis diseases cases have been reported in Makerere Uni-versity. The Ministry of Healthy has sent a team of experts to perform a diseasediagnosis to patients suspected being suffering from the diseases within Makerereand report on their rampage as soon as possible. But as they try to perform thedisease diagnostics, they discover that these diseases exhibit similar symptoms whichmakes the diagnosis process much more complicated, thus delaying the results. Inorder to reduce on the time delay in the provision of diagnostics results in the nearfuture, they have proposed using a machine learning diagnosis system and you havebeen approached to assist in the development of such systems. Using the knowledgeof Artificial intelligence and probability theory, discuss the steps you would followin developing such a system. You should clearly state the assumptions and relevantexamples for full marks. [18 marks]

(a) For each of the following graph search strategies, we will work out the order in which states are expanded, the path returned by graph search, the path cost, as well as the states that are not expanded. We will assume ties are broken in alphabetical order.

(i) Depth First Search:

• Order of states expanded: S, A, C, D, G
• Path returned: S -> A -> C -> D -> G
• Path cost: 12
• States not expanded: B

(ii) Breadth First Search:

• Order of states expanded: S, A, B, C, D, G
• Path returned: S -> A -> C -> G
• Path cost: 8
• States not expanded: D

(iii) Uniform Cost Search:

• Order of states expanded: S, A, C, D, G
• Path returned: S -> A -> C -> D -> G
• Path cost: 12
• States not expanded: B

(iv) A* Search:

• Order of states expanded: S, A, C, D, G
• Path returned: S -> A -> C -> D -> G
• Path cost: 12
• States not expanded: B

(v) Greedy Search:

• Order of states expanded: S, A, C, D, G
• Path returned: S -> A -> C -> D -> G
• Path cost: 12
• States not expanded: B

(b) To make the heuristic values admissible and consistent, we can change the heuristic value for state C. The range of values that are possible to make this correction depends on the specific heuristic function being used and the problem domain. Without further information, it is not possible to determine the exact range of values.

Question 3: (a) Probability plays a crucial role in Artificial Intelligence. It allows us to model uncertainty and make decisions based on uncertain information. In AI, probability is used in various areas such as probabilistic reasoning, Bayesian networks, machine learning, and decision making under uncertainty.

(b) In developing a machine learning diagnosis system for diseases with similar symptoms, the following steps can be followed:

1. Data Collection: Gather a dataset of patient records including symptoms, test results, and disease diagnoses.

2. Feature Selection: Identify relevant features that can help distinguish between different diseases. This may involve domain knowledge and statistical analysis.

3. Data Preprocessing: Clean the data, handle missing values, and normalize the features if necessary.

4. Model Selection: Choose an appropriate machine learning algorithm for classification, such as decision trees, support vector machines, or neural networks.

5. Training: Split the dataset into training and testing sets. Use the training set to train the chosen model on the labeled data.

6. Model Evaluation: Evaluate the performance of the trained model using the testing set. Metrics such as accuracy, precision, recall, and F1 score can be used.

7. Model Improvement: Fine-tune the model by adjusting hyperparameters or trying different algorithms to improve its performance.

8. Deployment: Once the model is satisfactory, deploy it in a production environment where it can be used for disease diagnosis.

Assumptions:

• The dataset is representative and contains sufficient information for accurate diagnosis.
• The chosen machine learning algorithm is suitable for the given problem.
• The symptoms used for diagnosis are reliable indicators of the diseases.
• The model will be regularly updated and retrained as new data becomes available.

Relevant examples:

• In a dataset of malaria cases, features like fever, headache, and presence of parasites in blood smears can be used to classify patients as malaria positive or negative.
• In a dataset of COVID-19 cases, features like cough, fever, and travel history can be used to classify patients as COVID-19 positive or negative.
• In a dataset of paralysis cases, features like muscle weakness, loss of sensation, and medical history can be used to classify patients as paralysis positive or negative.

By following these steps and making appropriate assumptions, a machine learning diagnosis system can be developed to assist in the timely and accurate diagnosis of diseases with similar symptoms.