THE UNIVERSITY OF DODOMA

COLLEGE OF INFORMATICS AND VIRTUAL EDUCATION

SECOND SEMESTER 2024/2025
CP 422: Assignment No 1
Instructions:
i. To increase student engagement, the assignment shall be done in group of not less
than ten with an upper bound 11. Part A shall be submitted not later than 6 th May
2025 through tom.tesha@gmail.com, word document, font size 12, space 1.5, align-
ment justify. Part B shall be submitted not later than 20 th May 2025 through the same
email, code in Notepad ++, and graphs if any, tables if any and the required output
should be in word document, font size 12, space 1.5, alignment justify
ii. Your explanation should be succinct
iii. Important note ….. Student participation per group should neither be less than 10
nor more 11
iv. This assignment weight in your CA (10 Marks)

Part A: Testing your reading understanding and application

Question one
a) Provide a concise description on
i. Breadth-First Search (BFS)
ii. Depth-First Search (DFS)
iii. Iterative Deepening DFS (IDFS)
b) Given the following graph (provide a simple graph diagram), perform:
i. BFS
ii. DFS
iii. IDFS
NB: In your response, show the order of node expansion clearly.
c) By using the same graph, if each edge has a different cost; perform Uniform Cost Search
showing the cumulative cost calculations at each step
d) If we assume the heuristic function h(n) is defined between edges
i. Perform Best-First Search and A* Search.
 ii. Compare the two search paths found.
NB: For the manual computation, use the algebra f(n) = g(n) + h(n) at each step
Question two
a) In your own words, summarize the steps of the Local Search algorithms
b) Explain (in about 200 words) why Simulated Annealing can sometimes find better solu-
tions than Hill Climbing.
−Δ E
c) Consider the Annealing described by the cooling schedule formula: P=e T , briefly explain

what happens when T is very high or very low with respect to exploitation and exploration of the
neighboring solutions
d) Applying your understanding of the Local Search algorithmic efficiency/bottleneck, list two real-
world problems where Genetic Algorithms could outperform traditional search methods. Justify
briefly.

Question three
a) Consider a simple map-coloring problem (3 countries, 3 colors), apply the:
i. Backtracking Search
ii. Backtracking + Forward Checking
iii. Backtracking + Arc Consistency (AC-3)
NB: In each method show the steps clearly
b) Consider the Constraint Satisfaction Problem (CSP) with 5 variables: X1, X2, X3, X4, X5.
Each variable can take a value from the domain: {1,2,3} and the constraints to be satis-
fied are { X1 ≠ X2, X2 ≠ X3, X3 ≠ X4 and X4 ≠ X5
Requirements
i. Solve the above CSP using a Local Search algorithm with the Min-Conflicts
heuristic. You begin with a random assignment of values and at each step, choose
a variable that is in conflict and change its value to minimize the number of con-
straint violations. Show the initial assignment, intermediate steps (at least 2 steps),
and the final solution (when no conflicts remain).
ii. Explain in a few lines how does Arc Consistency reduce the search space com-
pared to plain Backtracking.
c) Local Search algorithms, such as Hill Climbing, often struggle with getting trapped in lo-
cal optima because they only seek the steepest immediate ascent, which can prevent them
 from reaching the global optimum. Suggest suitable strategies to overcome such bottle-
neck for the Local Search application in CSP

Question four
a) Using proof by resolution;
i. Translate the following English statements into First-Order Logic (FOL).
1. Every student who studies passes the exam.”
2. Very few students who study do not pass the exam.
ii. Then, using inference rules (like Universal and Existential Instantiation + Modus Po-
nens), prove each simple query in 1) and 2).

Simple Projects (10 Marks)

Question five
a) Implement the Breadth-First Search (BFS), Depth-First Search (DFS) and A* Search
(with a simple heuristic f ( n )=g ( n ) +h ( n )) algorithms in Python or Java (your choice)
Assume you are helping a delivery person to find the best route in a region that has 10
cities connected by roads.

Conditions are;
Some roads have direct connections between cities (given with their travel cost).
Some cities are not directly connected (no edge).
Each city also has an estimated straight-line distance (heuristic value) to the destination
city.
Your goal is to find the best route from City A (starting point) to City J (destination).
Assume the cities are A, B, C, D, E, F, G, H, I, J
Road Connection Actual Costs so far (Travel Costs Between Cities):
From/ A B C D E F G H I J
To
A - 4 3 - - - - - - -
B 4 - 1 2 5 - - - - -
C 3 1 - 4 - 7 - - - -
D - 2 4 - 1 5 - - - -
 E - 5 - 1 - 3 8 - - -
F - - 7 5 3 - 2 6 - -
G - - - - 8 2 - 2 3 -
H - - - - - 6 2 - 1 5
I - - - - - - 3 1 - 2
J - - - - - - - 5 2 -
NB (-) Indicates there is no direct connection

Heuristic Values (Estimated Straight-Line Distance to Destination J):

City Heuristic (estimated cost to the goal)
A 10
B 9
C 7
B 8
E 6
F 5
G 3
H 6
I 2
J 0

Required output
a) For each case, Print:
i. The path found (sequence of cities).
ii. The total path cost.
iii. The number of nodes expanded.
b) For the analyses and in few words, Compare BFS, DFS, and A*:
i. Specify which one found the best (lowest-cost) path? (Assess completeness)
ii. Which one expanded fewer nodes? (This assess space complexity)

Question Six
Implement the Simulated Annealing to solve the N-Queens Problem (N=8). Requirements:
show the number of steps taken to find a solution and describe how the number of conflicts
changes over time.
Required output
Implemented that runs and solves the problem using recommended data structure if any.

Question Seven
Write a CSP program that solves a simple Sudoku puzzle (4x4 or 6x6) using
i. Backtracking Search
ii. Forward Checking enhancement

Required output
Implemented programs that run and solves the problem using recommended data structure if any.

Nawatakia mafanikio mema