ATAL BIHARI VAJPAYEE- INDIAN INSTITUTE OF

INFORMATION TECHNOLOGY AND MANAGEMENT

ARTIFICIAL
INTELLIGENCE

LAB ASSIGNMENT
9th May 2020

SUBMITTED BY:

Saurabh Prakash Giri 2018-IMG-057

Program 1:
Write a program to implement DFS and BFS algorithm.

Theory:
BFS algorithm
A standard BFS implementation puts each vertex of the graph into one of two categories:
➢ Visited
➢ Not Visited

The purpose of the algorithm is to mark each vertex as visited while avoiding cycles. The
algorithm works as follows:

➢ Start by putting any one of the graph's vertices at the back of a queue.
➢ Take the front item of the queue and add it to the visited list.
➢ Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to
the back of the queue.
➢ Keep repeating steps 2 and 3 until the queue is empty.
➢ The graph might have two different disconnected parts so to make sure that we cover
every vertex, we can also run the BFS algorithm on every node.

DFS algorithm
A standard DFS implementation puts each vertex of the graph into one of two categories:
➢ Visited
➢ Not Visited

The purpose of the algorithm is to mark each vertex as visited while avoiding cycles. The DFS
algorithm works as follows:

➢ Start by putting any one of the graph's vertices on top of a stack.

➢ Take the top item of the stack and add it to the visited list.
➢ Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to
the top of the stack.
➢ Keep repeating steps 2 and 3 until the stack is empty.

Program algorithm:
BFS pseudocode
create a queue Q
mark v as visited and put v into Q
while Q is non-empty
remove the head u of Q
mark and enqueue all (unvisited) neighbours of u
DFS pseudocode (recursive implementation)

DFS(G, u)
u.visited = true
for each v ∈ G.Adj[u]
if v.visited == false
DFS(G,v)
init() {
For each u ∈ G
u.visited = false
For each u ∈ G
DFS(G, u)
}

Complexity analysis:
BFS algorithm
Time Complexity: O(V+E) where V is number of vertices in the graph and E is number of edges
in the graph.

DFS algorithm
Time complexity: O(V + E), where V is the number of vertices and E is the number of edges in
the graph.
Space Complexity: O(V).
Since, an extra visited array is needed of size V.

Input / Output Screenshots :

Program 2:
Write a program to simulate 4 Queen / N Queen Problem.

Theory:
The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two
queens attack each other. The chess queens can attack in any direction as horizontal, vertical,
horizontal and diagonal way. A binary matrix is used to display the positions of N Queens, where
no queens can attack other queens.
The idea is to place queens one by one in different columns, starting from the leftmost column.
When we place a queen in a column, we check for clashes with already placed queens. In the
current column, if we find a row for which there is no clash, we mark this row and column as
part of the solution. If we do not find such a row due to clashes then we backtrack and return
false.

Program algorithm:
1) Start in the leftmost column
2) If all queens are placed
return true
3) Try all rows in the current column.
Do following for every tried row.
a) If the queen can be placed safely in this row
then mark this [row, column] as part of the
solution and recursively check if placing
queen here leads to a solution.
b) If placing the queen in [row, column] leads to
a solution then return true.
c) If placing queen doesn't lead to a solution then
unmark this [row, column] (Backtrack) and go to
step (a) to try other rows.
3) If all rows have been tried and nothing worked,
return false to trigger backtracking.

Complexity analysis:
Average and worst case complexity of the solution is O(N!) (since, you are checking all the
possible solutions i.e. (N^N arrangements). If you need all the possible solutions, the best,
average and worst case complexity remains O(N!)
Input / Output Screenshots :
Program 3:
Write a program to solve tower of Hanoi problem.

Theory:
Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of
the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1) Only one disk can be moved at a time.

2) Each move consists of taking the upper disk from one of the stacks and placing it on top of
another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3) No disk may be placed on top of a smaller disk.

With three disks, the puzzle can be solved in seven moves. The minimum number of moves
required to solve a Tower of Hanoi puzzle is 2n-1, where n is the number of disks.

Program algorithm:
void Towerof Hanoi(int n, String from, String using, String to)
{
if(n>0)
{
Towerof Hanoi(n-1, from, to, using);
System.out.println(“Move disk ”+n+” from ”+from+” to ”+to);
Towerof Hanoi(n-1, using, from, to);
}
}

Complexity analysis:
n n
Time complexity is O(2 ) or O(a ) where a is a constant greater than 1.
Input / Output Screenshots :
Program 4:
Write a program for Hill Climbing algorithm.

Theory:
Hill Climbing is a heuristic search used for mathematical optimization problems in the field of
Artificial Intelligence.
Given a large set of inputs and a good heuristic function, it tries to find a sufficiently good
solution to the problem. This solution may not be the global optimal maximum.

1. Variant of generate and test algorithm : It is a variant of generate and test algorithm. The
generate and test algorithm is as follows :

1. Generate possible solutions.

2. Test to see if this is the expected solution.
3. If the solution has been found quit else go to step 1.
Hence we call Hill climbing as a variant of generate and test algorithm as it takes the
feedback from the test procedure. Then this feedback is utilized by the generator in
deciding the next move in search space.
2. Uses the Greedy approach : At any point in state space, the search moves in that direction
only which optimizes the cost of function with the hope of finding the optimal solution at
the end.

Program algorithm:
function HILL-CLIMBING(problem) returns a state that is a local maximum
current ← MAKE-NODE(problem.INITIAL-STATE)
loop do
neighbor ← a highest-valued successor of current
if neighbor.VALUE ≤ current.VALUE then return current.STATE
current ← neighbor

Complexity analysis:
Hill climbing is neither complete nor optimal, has a time complexity of O(∞) but a space
complexity of O(b).
Input / Output Screenshots :
Program 5:
Write a program to implement A* algorithm.

Theory:
A* Search algorithm is one of the best and popular technique used in path-finding and graph
traversals. Informally speaking, A* Search algorithms, unlike other traversal techniques, it has
“brains”. What it means is that it is really a smart algorithm which separates it from the other
conventional algorithms. And it is also worth mentioning that many games and web-based maps
use this algorithm to find the shortest path very efficiently (approximation).

The A* search algorithm is an extension of Dijkstra's algorithm useful for finding the lowest cost
path between two nodes (aka vertices) of a graph. The path may traverse any number of nodes
connected by edges (aka arcs) with each edge having an associated cost. The algorithm uses a
heuristic which associates an estimate of the lowest cost path from this node to the goal node,
such that this estimate is never greater than the actual cost.
The algorithm should not assume that all edge costs are the same. It should be possible to start
and finish on any node, including ones identified as a barrier in the task.

Program algorithm :
let the openList equal empty list of nodes
let the closedList equal empty list of nodes
put the startNode on the openList (leave it's f at zero)
while the openList is not empty
let the currentNode equal the node with the least f value
remove the currentNode from the openList
add the currentNode to the closedList
if currentNode is the goal
You've found the end!
let the children of the currentNode equal the adjacent nodes
for each child in the children
if child is in the closedList
continue to beginning of for loop
child.g = currentNode.g + distance between child and current
child.h = distance from child to end
child.f = child.g + child.h
if child.position is in the openList's nodes positions
if the child.g is higher than the openList node's g
continue to beginning of for loop
add the child to the openList
Input / Output Screenshots:
Program 6:
Write a program to solve water jug problem.

Theory:
Given two unmarked jugs with capacities x and y liters. The moves to obtain exactly n liters of
water in any of the two jugs or both by the end.Given that:

1. There is infinite supply of water.

2. Both the jugs are empty at the beginning.
Operations allowed:
1. Empty /fill a jug completely with water.
2. Pour water from one jug to another until one of the jugs is either empty or full.

Solution: (Always pour from n litre jug into m litre jug)

1. Fill the n litre jug and empty it into m litre jug.
2. Whenever the n litre jug becomes empty fill it.
3. Whenever the m litre jug becomes full empty it.
4. Repeat steps 1, 2 and 3 till either n litre jug or the m litre jug contains d litres of water.

Program algorithm:
We approach problem using memoization and recursion . At any point, there can be a total of six
possibilities:
• Empty the first jug completely
• Empty the second jug completely
• Fill the first jug
• Fill the second jug
• Fill the water from the second jug into the first jug until the first jug is full or the second
jug has no water left
• Fill the water from the first jug into the second jug until the second jug is full or the first
jug has no water left
Using Recursion, visit all the six possible moves one by one until one of them returns True.
Since there can be repetitions of same recursive calls, hence every return value is stored
using memoization to avoid calling the recursive function again and returning the stored value.

Complexity analysis:
Time complexity: O(M * N)
Auxiliary Space: O(M * N)
Input / Output Screenshots: