SPPU 2019 Syllabus S.E Computer Engineering
computer engineering semester 4 2023 may microprocessor pattern 2019SPPU 2019 Syllabus S.E Computer Engineering
Engineering Mechanics Endsem (2023)SPPU 2019 Syllabus S.E Computer Engineering
Audit course reportSPPU 2019 Syllabus S.E Computer Engineering
Tutorial work Handwritten notes SE unit2 by juhi AgrawalSPPU 2019 Syllabus S.E Computer Engineering
Lecture notesName Planned Date
Implement depth first search algorithm and Breadth First Search algorithm, Use an undirected graph and develop a recursive algorithm for searching all the vertices of a graph or tree data structure. Implement A star Algorithm for any gamesearch problem. 2 Implement A star Algorithm for any game searchproblem.
Implement Greedy search algorithm for any ofthe following application: I. Selection Sort II. Minimum Spanning Tree III. Single-Source Shortest Path Problem IV. Job Scheduling Problem V. Prim's Minimal Spanning Tree Algorithm VI. Kruskal's Minimal Spanning TreeAlgorithm VII. Dijkstra's Minimal Spanning Tree Algorithm
Implement a solution for a Constraint Satisfaction Problem using Branch and Boundand Backtracking for n-queens problem or a graph colouring problem 5 Develop an elementary chatbot for anysuitablecustomer interaction application.
Implement any one of the following Expert System I. Hospitals and medical facilities 7 Case study on Amazon EC2 and learn aboutAmazon EC2 web services. 8 Installation and configure Google App Engine. 9 Creating an Application in SalesForce programming Language. 10 Design and develop custom Application (MiniProject) using Salesforce Cloud 11 Mini-Project
Title: Implement depth first search algorithm and Breadth First Search algorithm, Use an undirected graph and develop a recursive algorithm for searching all the vertices of a graph or tree data structure. Aim: Implement DFS & BFS in Artificial Intelligence. Prerequisites:
Theory: The Depth First Search (DFS) is a search technique which searches to the lowest depth or ply of the tree DFS uses Stack as a data structure (OPEN list) to process the given state space.
Fig-1: State Space Representation S = < a:[b,c], b:[a,c,d], c:[a,b,d], d:[b,c] >Algorithm DFS()Def DFS(Start) Open=StartClosed=<> State = FAILURE While (Open <> Empty ) AND (State <> SUCCESS) thenPick front node ̳N‘ from Open Open = Open – If GOALTEST(N) = TRUE then State = SUCCESS Closed = APPEND (Closed , )Else Closed = APPEND (Closed , )Child = < MOVEGEN(N) >Child = Child= Open = APPEND (Child,Open)End If End While Return State Def GOALTEST(N) If N = Goal thenReturn TRUE Else Return FALSE
Def MOVEGEN(N) Succ =<> For N in S do Succ= Succ U Return Succ Def APPEND (list1, list2)New_list = list1 + list2 Return New_list
Analysis of DFS()
The Breadth First Search (BFS) is a search technique which searches the tree level wise and left to right at each level of the tree. The BFS uses Queue as a data structure (OPEN list) to process the given state space.
Algorithm BFS()Def BFS(Start) Open=Start Closed=<> State = FAILURE While (Open <> Empty ) AND (State <> SUCCESS) thenPick front node ̳N‘ from Open Open = Open – If GOALTEST(N) = TRUE then State = SUCCESS Closed = APPEND (Closed , )Else Closed = APPEND (Closed , )Child = < MOVEGEN(N) >Child = Child= Open = APPEND (Open, Child)End If End While Return State
Analysis of BFS()
def GOALTEST(N): if N == Goal: return True else: return False
def MOVEGEN(N): New_list=list() if N in SuccList(): New_list=SuccList[N]print("New_list=",New_list) return New_list
def APPEND(L1,L2): New_list=L1+L2return New_list
def DFS(): OPEN=[Start] CLOSED=list()global State global Closed
while (len(OPEN) != 0) and (State != SUCCESS):print(" ") N= OPEN[0] print("N=",N) del OPEN[0] #delete the node we picked
if GOALTEST(N)==True: State = SUCCESS CLOSED = APPEND(CLOSED,list(N))
CLOSED = APPEND(CLOSED,list(N))print("CLOSED=",CLOSED) CHILD = MOVEGEN(N)print("CHILD=",CHILD) for val in CLOSED: if val in CHILD: CHILD(val)for val in OPEN: if val in CHILD: CHILD(val) OPEN = APPEND(CHILD,OPEN) #append movegen elements to OPENprint("OPEN=",OPEN) Closed=CLOSEDreturn State
#Driver Code result=DFS() #call search algorithmprint(Closed,result)
def GOALTEST(N): if N == Goal: return True else: return False
def MOVEGEN(N): New_list=list() if N in SuccList(): New_list=SuccList[N] print("New_list=",New_list)return New_list
def BFS(): OPEN=[Start] CLOSED=list()global State global Closed while (len(OPEN) != 0) and (State != SUCCESS):print(" ") N= OPEN[0] print("N=",N) del OPEN[0] #delete the node we picked
if GOALTEST(N)==True: State = SUCCESS CLOSED = APPEND(CLOSED,list(N))print("CLOSED=",CLOSED) else: CLOSED = APPEND(CLOSED,list(N))print("CLOSED=",CLOSED) CHILD = MOVEGEN(N)print("CHILD=",CHILD) for val in CLOSED: if val in CHILD: CHILD(val)for val in OPEN: if val in CHILD: CHILD(val) OPEN = APPEND(OPEN,CHILD) #append movegen elements to OPEN print("OPEN=",OPEN) Closed=CLOSEDreturn State
#Driver Code result=BFS() #call search algorithmprint(Closed,result)
The algorithm DFS and BFS are used in the problem of graph and computer network.
Input : The State Space representation of a given Graph.
Output : The output is the path traversed by the algorithm from start node to goal node. If search fails to find thegoal then it returns the search status as FAILURE.
Conclusion: The implementation simulates the working of DFS and BFS on given graph in the perspective of AI.
Title: Implement A* Algorithm for any game search problem.
Aim: Implementation of A* Algorithm for any game search problem.
Prerequisites: Concept of Heuristic function, state space.
Objectives: Student should be able to implement A* algorithm on given graph.
A* (pronounced as "A star") is a computer algorithm that is widely used in path finding and graph traversal. However, the A* algorithm introduces a heuristic into a regular graph-searching algorithm, essentially planningahead at each step so a more optimal decision is made. A* is an extension of Dijkstra's algorithm with some characteristics of breadth-first search (BFS). A* uses a function f(n) that gives an estimate of the total cost of a path using that node. Therefore, A* is aheuristic function, which differs from an algorithm in that a heuristic is more of an estimate and is not necessarily provably correct. A* expands paths that are already less expensive by using this function: f(n)=g(n)+h(n)where, f(n) = total estimated cost of path through node ng(n) = cost so far to reach node n h(n) = estimated cost from n to goal. This is the heuristic part of the cost function, so it is like a guess.
The calculation of h(n) can be done in various ways: The Manhattan distance (explained below) from node n to the goal is often used. This is a standard heuristicfor a grid. If h(n) = 0, A* becomes Dijkstra's algorithm, which is guaranteed to find a shortest path.
The heuristic function must be admissible, which means it can never overestimate the cost to reach the goal the Manhattan distance and h(n)= 0 are admissible.
Consider the following graph with edge cost (distance between two nodes like A-B, C-F, etc) and theheuristics value to reach to the target node.
The above graph can be represented as dictionary data structure of Python as: graph=
to store g-score and h-scorelist first value is the g-score, second value is the h-score,i., heuristic'A':, 'B':
The algorithm will retrieve the graph as follow:
astar: F=G+H, we name F as f_distance, G as g_distance, H as heuristic
#Assign all the nodes, a f_distance value as infinity as initial valuef_distance=
#The f_ditance value of start node is 0f_distance[start_node]=
#Assign all the nodes, a g_distance value as infinity as initial valueg_distance=
#The g_ditance value of start node is 0g_distance[start_node]=
#Keep the track of parent node in came_formcame_from= came_from[start_node]=start_node
queue=[(0,start_node)] #use queue as listwhile queue: f_distance,current_node=heapq(queue)if current_node == end_node: print('found the end_node') return f_distance, came_from #for all the neighbors of the current node calculate g_distancefor next_node,weights in graph[current_node].items(): temp_g_distance=g_distance[current_node]+weights[0] #g_distance of current node is less than the g_distance of neighbor#Update the g_distance of next node to the smaller distance value temp_g_distance<g_distance[next_node]: g_distance[next_node]=temp_g_distance heuristic=weights[1] f_distance=temp_g_distance+heuristic came_from[next_node]=current_node heapq(queue,(f_distance,next_node)) return f_distance, came_from#Driver Code Node_distance, Path=astar(graph,'A','F')print(Node_distance) print(Path)
8-Puzzle using A* Algorithms N-Puzzle or sliding puzzle is a popular puzzle that consists of N tiles where N can be 8, 15, 24, and so on our example N = 8. The puzzle is divided into sqrt(N+1) rows and sqrt(N+1) columns
Eg. 15-Puzzle will have 4 rows and 4 columns and an 8-Puzzle will have 3 rows and 3 columns. The puzzle consists of N tiles and one empty space where the tiles can be moved. Start and Goal configurations (also called state) of the puzzle are provided.
Rules for solving the puzzle.
Instead of moving the tiles in the empty space, we can visualize moving the empty space in place of thetile, basically swapping the tile with the empty space. The empty space can only move in four directions viz. 1 2 3 Left The empty space cannot move diagonally and can take only one step at a time.
In our 8-Puzzle problem, we can define the h-score as the number of misplaced tiles by comparing the current state and the goal state or summation of the Manhattan distance between misplaced nodes. g-score will remain as the number of nodes traversed from a start node to get to the current node.
From Figure below, we can calculate the h-score by comparing the initial(current) state and goal state andcounting the number of misplaced tiles. Thus, h-score = 5 and g-score = 0 as the number of nodes traversed from the start node to the current nodeis 0.
How A* solves the 8-Puzzle problem. We first move the empty space in all the possible directions in the start state and calculate the f-score for each state. This is called expanding the current state. After expanding the current state, it is pushed into the closed list and the newly generated states are pushedinto the open list. A state with the least f-score is selected and expanded again. This process continues untilthe goal state occurs as the current state. Basically, here we are providing the algorithm a measure to choose its actions. The algorithm chooses the best possible action and proceeds in that path solves the issue of generating redundant child states, as the algorithm will expand the node with the least f-score.
def accept(n): """ Accepts the puzzle from the user """puz = [] for i in range(n): puz([val for val in input().split()])return puz
def print_board(board,n):for i in range(n): print() for j in range(n): print(board[i][j],end=' ')
#Find the position of blank spacedef find_space(Current,n): for blank_row_pos in range(n): for blank_col_pos in range(n): if Current[blank_row_pos][blank_col_pos]=='_':return blank_row_pos,blank_col_pos
#Copy the current node to new node for shuffling the blank space and create a new configurationdef copy_current(Current): temp=[] for i in range(len(Current)):row=[] for val in Current[i]:
#Move the blank space in given direction, if out of range return None
def shuffle(Current,brow_pos,bcol_pos,move_x,move_y): if move_x >= 0 and move_x < len(Current) and move_y >= 0 and move_y < len(Current):temp=[] temp=copy_current(Current) change=temp[move_x][move_y] temp[move_x][move_y]=temp[brow_pos][bcol_pos]temp[brow_pos][bcol_pos]=change return temp else: return None
#Function to calculate g_score: the number of nodes traversed from a start node to get to the current nodedef g_score(Node):
return Node[1] #Node=[Board,level,fscore]
#Function to calculate h_score: the number of misplaced tiles by comparing the current state and the goalstate def h_score(Current,Goal,n):hscore= for i in range(n): for j in range(n): if (Current[i][j] != Goal[i][j]) and (Current[i][j]!='_'):hscore
+=1 return hscore
#Function to calculate f_Score= g_score + h_Scoredef f_score(Node,Goal,n): Current=Node[0] return g_score(Node) + h_score(Current,Goal,n)
#Generate the child nodes by moving the blank in any four direction (up,down,left,right)def move_gen(Node,Goal,n):
Current=Node[0]level=Node[1] fscore= row,col=find_space(Current,n) move_positions=[[row,col-1],[row,col+1],[row-1,col],[row+1,col]] #left,right,up,downchildren=[] #List of child nodes of current node for move in move_positions: child=shuffle(Current,row,col,move[0],move[1])if child is not None: cNode=[child,0,0] #Dummy node for calculating f_Scorefscore=f_score(cNode,Goal,n)
Node=[child,level+1,fscore]children(Node) print("\n\n The Children ::",children)return children
#Function goal_test to see the goal configuration is reacheddef goal_test(Current,Goal,n): if h_score(Current,Goal,n) == 0:return True else: return False
#Function to Sort OPEN based on f_scoredef sort(L): L(key = lambda x: x[2],reverse=False)return L
#Function for starting the Gamedef play_game(Start, Goal, n): #when game starts fscore=0 #fscore initialized to zero gscore=0 #gscore initialized to zero level=0 #the start configuration is root node s at level-0 of the state space tree''' print_board(Start,n); print_board(Goal,n) print("\n\nI AM HERE . \n\n")''' Node=[Start,level,fscore] fscore=f_score(Node,Goal,n)
#Every Node is [board configuration ,level,gscore] Node = [Start,level,fscore] # current node is Start nodeprint("\nThe Node is=\n",Node) OPEN = [] #OPEN list as frontier CLOSED = [] #CLOSED as exploredOPEN(Node) levelcount=
#Explored the current node to reach to the Goal configurationwhile True: N=OPEN[0] #first node of open del OPEN[0] # delete first node of open
Current=N[0] #Extract board configuration print("\n\n The current configuration is ::",Current) CLOSED(N) #if goal configuration is reached terminateif goal_test(Current,Goal,n) == True: print("\nGoal reached!!") print("CLOSED=",CLOSED) break
CHILD=move_gen(N,Goal,n) #print("\n\n The CHILD is ::",CHILD)OPEN=[] for child in CHILD: OPEN(child) #sort the OPEN list based on fscore value of each nodesort(OPEN) #print("\n\n The OPEN is ::",OPEN)
#Drive Code n=int(input("Enter the board size:")) print("\nEnter Start Configuration of board")Start=accept(n) print("\nEnter Goal Configuration of board")Goal=accept(n) play_game(Start, Goal, n)
Application: A* Algorithm is used in various diversified areas of research, computer network & graph, Google maps tofind the shortest path between source and destination.
Input : State Space representation of graph. Output : The shortest path between source and destination. Conclusion: The A* algorithm finds the shortest path between source and destination using heuris
Title: Implement Greedy search algorithm for any of the following application:
Aim: Implement Dijkstra's Minimal Spanning Tree Algorithm
Prerequisites: Concept of Graph and the Graph representation using Adjacency Matrix/List.
Objectives: Student should be able to implement Dijkstra's algorithm
Theory: Consider the following graph given in figure below.
The above graph representation is a python dictionary wherein a node and its immediate successors or child nodes are specifies, for example, Node ̳A‘ has node ̳B‘ and node ̳C‘ as successors. The path cost from node ̳A‘ to node ̳B‘ is 2 and that of path ̳A‘ to ̳C‘ is 3.
function Dijkstra(Graph, source): dist[source] ← 0 // the start node has distance 0 create vertex priority queue Q //Use priority Queue here
for each vertex v in Graph: if v ≠ source dist[v] ← INFINITY //Assign the weight prev[v] ← UNDEFINED //predecessor of current node v
while Q is not empty: u ← Q_min() // Remove and return best vertex
for each neighbor v of u still in Q: // only v that are still in Qalt ← dist[u] + length(u, v) if alt < dist[v]: dist[v] ← altprev[v] ← u Q_priority(v, alt)
return dist, prev
Code of Dijkstra‘s Algorithm:
def dijkstra(graph,node): #The distance value of start node is zero ̳0‘distances[node]=0
#Assign infinity to all other nodes distances= print("distances::",distances)
#Predecessor of node is stored here previous=
graph> queue=[(0,node)] #queue stores start ̳node‘ with edge distance value
while queue: #heapq of python maintains the priority queue (min queue) #heappop() method of heapq will pop the minimum val of the heap current_distance, current_node = heapq(queue)
relaxation, visit all the successors of current_node and get the edge cost as wellfor next_node, weight
in graph[current_node].items(): distance_temp=current_distance+weight #if the distance of the currently visited node is smaller than the earlier stored cost #thenupdate the distance value of current node with smaller cost if distance_temp<distances[next_node]: distances[next_node]=distance_temp previous[next_node]=current_node heapq(queue,(distance_temp,next_node)) print("Distances::",distances)return distances,previous
#Driver Code Node_distance, Path = dijkstra(graph,'A')print(Node_distance) print(Path)
The algorithm finds the Minimal Spanning Tree for given graph when a source is specified so it is used inGoogle Map and other similar application to find the shortest route between the source and destination.
Input: State Space representation of the given Graph or the problem. Output: The algorithm finds the Minimal Spanning Tree for given graph when a source is specified.
Conclusion: The Dijkstra‘s Algorithm finds the Single source and multiple destinations with shortest distance between the two nodes in the given graph thereby finding the shortest distance between a given source and the destination.
Title: Implement a solution for a Constraint Satisfaction Problem using Branch and Bound and Backtracking for n-queens problem or a graph coloring problem.
Aim: Implement a solution for a Constraint Satisfaction Problem using Branch and Bound and Backtracking for N-queens problem.
Prerequisites: Concept of CSP, backtracking and branch & bound technique.
Objectives: Student should be able to implement the 8-Queen problem using CSP, backtracking and branch & bound technique.
Theory: A constraint satisfaction problem consists of three components, X,D, and C:X is a set of variables, . D is a set of domains, , one for each variable. C is a set of constraints that specify allowable combinations of values. Each domain Di consists of a set of allowable values, for variable Xi. Each constraint Ci consists of a pair _scope, rel _, where scope is a tuple of variables that participate in the constraint and relis a relation that defines the values that those variables can take on. A relation can be represented as an explicit list of all tuples of values that satisfy the constraint, or as an abstract relation that supports two operations: testing if a tuple is a member of the relation and enumerating the members of the relation. For example, if X1 and X2 both have the domain , then the constraint saying the two variables must havedifferent values can be written as <(X1,X2), [(A,B), (B,A)]> or as <(X1,X2),X1 ≠ X2>. To solve a CSP, we need to define a state space and the notion of a solution. Each state in a CSP is defined by an assignment of values ASSIGNMENT to some or all of the variables, . An assignment that does not violate any constraints is called a consistent or legal assignment. A complete assignment is one in which every variable is assigned, and a solution to a CSP is a consistent, complete assignment. A partial assignment is one that assigns values to only some of the variables.
The N-Queens problem is a puzzle of placing exactly N queens on an NxN chessboard, such that no two queens can attack each other in that configuration. Thus, no two queens can lie in the same row,column or diagonal.
In the backtracking algorithm, we consider possible configurations one by one and backtrack if we hit a dead end. The branch and bound solution is somehow different, it generates a partial solution until it figures that there's no point going deeper as we would ultimately lead to a dead end.
In the backtracking approach, we maintain an 8x8 binary matrix for keeping track of safe cells (by eliminating the unsafe cells, those that are likely to be attacked) and update it each time we place a new queen. However, it required O(n^2) time to check safe cell and update the queen. In the 8 queens problem, we ensure the following:
Applying the backtracking approach: Now, we place queen q 1 in the very first acceptable position (1, 1). Next, we put queen q 2 so that both thesequeens do not attack each other. We find that if we place q 2 in column 1 and 2, then the dead end is encountered. Thus the first acceptable position for q 2 in column 3, i. (2, 3) but then no position is left for placing queen 'q 3 ' safely. So we backtrack one step and place the queen 'q 2 ' in (2, 4), the next
best possible solution. Then we obtain the position for placing 'q 3 ' which is (3, 2). But later this position also leads to a dead end, and no place is found where 'q 4 ' can be placed safely. Then we have to backtrack till 'q 1 ' and place it to (1, 2) and then all other queens are placed safely by moving q 2 to (2, 4), q 3 to (3, 1) and q 4 to (4, 3). That is, we get the solution (2, 4, 1, 3). This is one possible solution for the 4-queens problem. For another possible solution, the whole method is repeated for all partial solutions. The other solutions for 4 - queens problems is (3, 1, 4, 2) i.
The implicit tree for 4 - queen problem for a solution (2, 4, 1, 3) s as follows:
Fig shows the complete state space for 4 - queens problem. But we can use backtracking method togenerate the necessary node and stop if the next node violates the rule, i., if two queens are attacking.
4 - Queens solution space with nodes numbered in DFS It can be seen that all the solutions to the 4 queens problem can be represented as 4 - tuples (x 1 , x 2 , x 3 , x 4 )where xi represents the column on which queen "qi" is placed. One possible solution for 8 queens problem is shown in fig:
backtracking global NN = 4
def printSolution(board):for i in range(N): for j in range(N): print (board[i][j], end = " ") print()
A utility function to check if a queen canbe placed on board[row][col]. Note that this# function is called when "col" queens arealready placed in columns from 0 to col -1.# So we need to check only left side forattacking queens
def isSafe(board, row, col):
Check this row on left sidefor i in
range(col): if board[row][i] == 1: return False
Check upper diagonal on left sidefor i, j in zip(range(row, -1, -1),
range(col, -1, -1)): if board[i][j] == 1: return False
Check lower diagonal on left sidefor i, j in zip(range(row, N, 1),
if board[i][j] == 1: return False
def solveNQUtil(board, col):
base case: If all queens are placed# then return
true if col >= N: return True
Consider this column and try placing# this queen in all rows one by
one for i in range(N):
if isSafe(board, i, col):
Place this queen in board[i][col]board[i][col] =
1 # recur to place rest of the queens if solveNQUtil(board, col + 1) == True:return True
If placing queen in board[i][col# doesn't lead to a solution, then # queen from board[i][col]
if the queen can not be placed in any row in# this column col then return
false return False
This function solves the N Queen problem using# Backtracking. It mainly uses solveNQUtil() tosolve the problem. It returns false if queens# cannot be placed, otherwise return true and# placement
of queens in the form of 1s.
note that there may be more than onesolutions, this function prints one of the# feasible solutions.
def solveNQ(): board = [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ]
if solveNQUtil(board, 0) == False: print ("Solution does not exist")return False printSolution(board)return True
Applying the branch and bound approach:
The branch and bound approach suggest that we create a partial solution and use it to ascertain whether we need to continue in a particular direction or not. For this problem, we create 3 arrays to check for conditions 1,3 and 4. The Boolean arrays tell which rows and diagonals are already occupied. To achieve this, we need a numbering system to specify which queen is placed.
The indexes on these arrays would help us know which queen we are analyzing. Preprocessing - create two NxN matrices, one for top-left to bottom-right diagonal, and other for top- right to bottom-left diagonal. We need to fill these in such a way that two queens sharing same top- left_bottom- right diagonal will have same value in slashDiagonal and two queens sharing same top- right_bottom-left diagonal will have same value in backSlashDiagnol. slashDiagnol(row)(col) = row + col backSlashDiagnol(row)(col) = row - col + (N-1) < N = 8 >
For placing a queen i on row j, check the following:
""" A utility function to print solution """def printSolution(board): for i in range(N): for j in range(N): print(board[i][j], end = " ") print()
""" A Optimized function to check if a queen can be placed on board[row][col] """ def isSafe(row, col, slashCode, backslashCode,
rowLookup, slashCodeLookup, backslashCodeLookup):if (slashCodeLookup[slashCode[row][col]] or backslashCodeLookup[backslashCode[row][col]] orrowLookup[row]): return Falsereturn True
""" A recursive utility functionto solve N Queen problem """ def solveNQueensUtil(board, col, slashCode, backslashCode, rowLookup, slashCodeLookup,backslashCodeLookup):
""" base case: If all queens areplaced then return True """ if(col >= N): return Truefor i in range(N): if(isSafe(i, col, slashCode, backslashCode, rowLookup, slashCodeLookup,backslashCodeLookup)):
""" Place this queen in board[i][col] """board[i][col] = 1 rowLookup[i] = True slashCodeLookup[slashCode[i][col]] = True backslashCodeLookup[backslashCode[i][col]] = True""" recur to place rest of the queens """ if(solveNQueensUtil(board, col + 1, return True slashCode, backslash Code, rowLookup, slashCodeLookup,backslashCodeLookup)):
""" If placing queen in board[i][col] doesn't lead to a solution,then backtrack """ """ Remove queen from board[i][col] """board[i][col] = 0 rowLookup[i] = False slashCodeLookup[slashCode[i][col]] = False backslashCodeLookup[backslashCode[i][col]] = False
""" If queen can not be place in any row inthis column col then return False """ return False
""" This function solves the N Queen problem using Branch or Bound. It mainly uses solveNQueensUtil()tosolve the problem. It returns False if queens cannot be placed,otherwise return True or prints placement of queens in the form of 1s note that there may be more than one solutions,this function prints one of the feasible solutions.""" def solveNQueens(): board = [[0 for i in range(N)] for j in range(N)]
slashCode = [[0 for i in range(N)] for j in range(N)]backslashCode = [[0 for i in range(N)] for j in range(N)]
arrays to tell us which rows are occupiedrowLookup = [False] *
N # keep two arrays to tell us
which diagonals are occupiedx = 2 * N - 1
slashCodeLookup = [False] * x backslashCodeLookup = [False] * x
initialize helper matricesfor rr in range(N):
for cc in range(N): slashCode[rr][cc] = rr + cc backslashCode[rr][cc] = rr - cc + 7
if(solveNQueensUtil(board, 0, slashCode, backslashCode, rowLookup, slashCodeLookup, backslashCodeLookup) == False): print("Solution does not exist")return False
solution found printSolution(board)return TrueDriver Cde solveNQueens()
The CSP, Backtracking and Branch & Bound technique are used in many applications like Map coloring,optimization problems and network programing.
Input: Board with N x N size. Output: The algorithm places all the N Queens in N different columns with the given constraints.
Conclusion: The N queen problem is implemented using python language with two techniques called Backtracking and branch & bound.
Title: Implement the Expert System for Medical Diagnosis of 5-10 diseases based on adequate symptoms.
Aim: Implement Expert System using prolog: Medical Diagnosis of 5-10 diseases based on adequate symptoms.
Prerequisites: Expert System Design, Prolog, First Order Logic concepts.
Objectives: Student should be able to implement the Expert System for Medical Diagnosis.
Theory: What are Expert Systems? The expert systems are the computer applications developed to solve complex problems in a particulardomain, at the level of extra-ordinary human intelligence and expertise. Characteristics of Expert Systems High performance Understandable Reliable Highly responsive
Capabilities of Expert Systems Advising Instructing and assisting human in decision making Demonstrating Deriving a solution Diagnosing Explaining Predicting results Suggesting alternative options to a problem Refining their own knowledge
Components of Expert System The components of ES include − Knowledge Base Inference Engine User Interface
Figure: Implementation of AI Enabled Expert System Using Prolog Platform Knowledge Base It contains domain-specific and high-quality knowledge. Knowledge is required to exhibit intelligence. The success of any Expert System majorly depends upon the collection of highly accurate and precise knowledge Components of the Knowledge Base The ES knowledge base is your store for both, factual and technical information. True Information – It is information that is widely accepted by Information Engineers and experts in the field of work. Heuristic Knowledge – It is about practice, accurate judgment, human ability to analyze, and guess. Information representation It is a method used to organize and legitimize information. It is in the form of IF-THEN-ELSE rules.
Acquisition of information The success of any professional program or expert system depends to a large extent on the quality, completeness, and accuracy of the information stored in the database. The knowledge base is built on the study of various experts, scholars, and information engineers information engineer is a person with the qualities of empathy, rapid learning, and case analysis skills. Knowledge Engineer gets information from a course specialist by recording, interviewing, and supervising him at work, etc. He then classifies and organizes the information in a logical manner, in accordance with the IF- THEN-ELSE rules, which will be used by the interference machine. The information engineer also monitors the development of ES.
Inference engine The application of effective procedures and rules by Inference Engine is essential for taking the right,flawless, solution. In the event that ES is based on information, the Inference Engine acquires and uses the informationavailable at the information center to achieve a specific solution.
In the event of Rule Based Expert System, It applies: – It applies repetitive rules to facts, which are found in the application of the previous law. Add new information to the database if needed. It resolves conflicts of law where many rules apply in a particular case.
To recommend a solution, the Inference Engine uses the following strategies 1. Forward Chaining-To recommend a solution, the Inference Engine uses the following strategies 2. Backward Chaining– begins with a goal and then works backwards to find out which facts need to beemphasized in order to achieve the goal.
User Interface With the help of the user interface, the professional system works with the user, captures queries such as inreadable formats, and transmits them to the inference engine.
Example of World Old Expert System-Mycin o MYCIN(ES): MYCIN was a built using backward chaining methodology who used artificial intelligence to identify bacteria that cause serious infections, such as bacterium and meningitis, and recommend antibiotics, with a dose determined by the patient‘s body weight – a term derived from antibiotics it self, suc h a s anti-bacterial drugs .mycin ―. o Mycin system was also used to diagnose blood clotting disorders. o MYCIN was developed over five or six years in the early 1970‘s at Stanford University. o It was written in Lisp as Edward Shortliffe‘s doctoral degree directed by Bruce G. Buchanan, Stanley N. Cohen and others.
What is Prolog Language or Platform o Prolog long form stands for programming in Logic. It is logical & declarative language that playsimportant role in Artificial intelligence. o In prolog, logic is expressed as relations which is in the form of ― Facts‖ and ― R ules‖. Main part in implementation of Prolog is logic being applied. o In prolog Computation is carried out by running a query over these wriyyen relations whereasrelations are formed with the help of Facts & Rules. o In Declarative language the programmer specifies a goal to be achieved & prolog system works onhow to achieve it. o In prolog .pl extension is used for program.
Comparing Prolog with Traditional Language Traditional programming languages or old PL are said to be procedure oriented programminglanguage where programmer specifies in details how to solve problems. Related to purely declarative language programmer only specifies what problem is & leaves rest ofthe part to language system itself (prolog). Prolog is considered to be Non-procedural language system. It is based on pattern matching language consist of series of Rules & Facts.
Important Features & Signs Used In Prolog
Important Features & Signs Used In Prolog o. Indicates Prolog statement termination. o = Indicates Non equality operators. o? Indicates querry start point o Facts & predicates always start with alphabet.
Terminologies Used In PrologFact o Fact is explicit relationship between object and properties of object o In prolog, We declare some facts. These facts constitute the Knowledge Base of the expert system. We can ask query against the Knowledge Base. We can get output as affirmative if our query is already present in the knowledge Base or it is implied by Knowledge Base, otherwise we get outputas negative. o So, Knowledge Base can be considered as similar to database, against which we can ask query. o Prolog facts are represented in definite pattern. o Facts consist of entities and their relation. o Entities are mentioned or written within the parenthesis separated by comma (, ). o Their relation is expressed at the beginning and outside the parenthesis. o Every fact/rule ends with a dot (.).
So, a typical prolog fact consist of following Format: relation(entity1, entity2, . ‘th entity).
Example : 1(raju,mahesh).2(sonu). 3_number(5).
Explanation: These facts can be interpreted as: 1. and Mahesh are friends. 2. Sonu is a singer. 3. 5 is an odd number. Rules : This term rule is implicit relationship between object and properties of object\Ex:-‘A‘ is child of ̳B‘ if ̳B‘ is parent of ̳A‘
Queries : Queries term related to asking question about relationship between object and object properties Ex:-‘B‘ is parent of whom?
Predicates : A predicate is defined by a collection of clauses. A clause is either a rule or a fact. Predicate is formed withthe help of facts.
Running queries In Prolog :A typical prolog query can be asked as :Query 1 : ?- singer(sonu). Output : Yes.
Explanation :Because our knowledge base contains the above fact, so output was ̳Yes‘, otherwise itwould have been ̳No‘.
Query 2 : ?- odd_number(7).Output : No. Explanation : As our knowledge base does not contain the above fact, so output was ̳No‘. Sample Tutorials On Prolog :Tutorial:-01(Applying Rules on Facts)Facts are mentioned below- o Ram is male o Shyam is male o Ravi is male o Priyanka is female o Sonia is female
From above facts Predicates are formed as follows o male(ram). o male(shyam). o male(ravi). o female(priyanka). o female(sonia).
Program: (Expert_System_Medical_Diagnosys)go:- hypothesis(Disease), write('It is suggested that the patient has '),
write(Disease),nl, undo; write('Sorry, the system is unable to identify the disease'),nl,undo.
hypothesis(cold):- symptom(headache), symptom(runny_nose),symptom(sneezing), symptom(sore_throat),nl, write('Advices and Sugestions:'),nl, write('1: Tylenol'),nl, write('2: Panadol'),nl, write('3: Nasal spray'),nl, write('Please weare warm cloths because'),nl.
hypothesis(influenza) :-symptom(sore_throat), symptom(fever), symptom(headache), symptom(chills), symptom(body_ache), nl, write('Advices and Sugestions:'),nl, write('1: Tamiflu'),nl, write('2: Panadol'),nl, write('3: Zanamivir'),nl, write('Please take a warm bath and do salt gargling because'),nl.
hypothesis(typhoid) :- symptom(headache), symptom(abdominal_pain),symptom(poor_appetite), symptom(fever),nl,
write('Advices and Sugestions:'),nl,
write('1: Chloramphenicol'),nl, write('2: Amoxicillin'),nl, write('3: Ciprofloxacin'),nl, write('4: Azithromycin'),nl, write('Please do complete bed rest and take soft diet because'),nl.
hypothesis(chicken_pox) :-symptom(rash), symptom(body_ache), symptom(fever),nl, write('Advices and Sugestions:'),nl, write('1: Varicella vaccine'),nl, write('2: Immunoglobulin'),nl, write('3: Acetomenaphin'),nl, write('4: Acyclovir'),nl, write('Please do have oatmeal bath and stay at home because'),nl.
hypothesis(measles) :- symptom(fever), symptom(runny_nose), symptom(rash), symptom(conjunctivitis),nl, write('Advices and Sugestions:'),nl, write('1: Tylenol'),nl, write('2: Aleve'),nl, write('3: Advil'),nl, write('4: Vitamin A'),nl, write('Please get rest and use more liquid because'),nl. hypothesis(malaria) :-symptom(fever), symptom(sweating), symptom(headache), symptom(nausea), symptom(vomiting), symptom(diarrhea), nl, write('Advices and Sugestions:'),nl, write('1: Aralen'),nl, write('2: Qualaquin'),nl, write('3: Plaquenil'),nl, write('4: Mefloquine'),nl, write('Please do not sleep in open air and cover your full skin because'),nl. ask(Question) :- write('Does the patient has the symptom '),write(Question), write('? : '), read(Response),nl,
( (Response == yes ; Response == y) -> assert(yes(Question)) ; assert(no(Question)), fail). :- dynamic yes/1,no/1.
symptom(S) :- (yes(S) -> true ; (no(S) -> fail ; ask(S))).
undo :- retract(yes()),fail. undo :- retract(no()),fail.
?- go. Does the patient has the symptom headache? : y |:.
Does the patient has the symptom runny_nose? : |: n the patient has the symptom sore_throat? : |: y the patient has the symptom fever? : |: y. Does the patient has the symptom chills? : |: y. Does the patient has the symptom body_ache? : |: y. Advices and Sugestions: 1: Tamiflu 2: Panadol 3: Zanamivir Please take a warm bath and do salt gargling becauseIt is suggested that the patient has influenza true.
Input: Response to the query asked by the Expert System related to symptoms of the patient.
Output: The prediction of the disease based on the symptoms provided by patient.
Conclusion: The Expert System is implemented using PROLOG language which predicts the disease based on thesymptoms of the patient.
Title: Develop an elementary chatbot for any suitable customer interaction application. Aim: Implement chatbot which interact with the customer and responds to the query asked by the customer. Prerequisites: Chatbot implementation concepts, python, chatbot libraries. Objectives: Student should be able to customer care chatbot.
Theory: What is a Chatbot? A chatbot is an AI-based software designed to interact with humans in their natural languages. These chatbots are usually converse via auditory or textual methods, and they can effortlessly mimic human languages to communicate with human beings in a human-like manner
Chatbots can be categorized into two primary variants – Rule-Based and Self-learning.
The Rule-based approach trains a chatbot to answer questions based on a set of pre-determined rules on which it was initially trained. These set rules can either be very simple or very complex. While rule-based chatbots can handle simple queries quite well, they usually fail to process more complicated queries/requests.
As the name suggests, self-learning bots are chatbots that can learn on their own. These leverage advanced technologies like Artificial Intelligence and Machine Learning to train themselves from instances and behaviours. Naturally, these chatbots are much smarter than rule-based bots. Self- learning bots can be further divided into two categories – Retrieval Based or Generative.
Chatbot in Today’s Generation
Today, we have smart AI-powered Chatbots that use natural language processing (NLP) to understand human commands (text and voice) and learn from experience. Chatbots have become a staple customer interaction tool for companies and brands that have an active online presence (website and social network platforms).
ChatterBot is a Python library that is designed to deliver automated responses to user inputs. It makes useof a combination of ML algorithms to generate many different types of responses. This feature allows developers to build chatbots using python that can converse with humans and deliver appropriate and relevant responses. Not just that, the ML algorithms help the bot to improve its performance with experience.
Another excellent feature of ChatterBot is its language independence. The library is designed in a way that makes it possible to train your bot in multiple programming languages.
How does ChatterBot function?
When a user enters a specific input in the chatbot (developed on ChatterBot), the bot saves the input along with the response, for future use. This data (of collected experiences) allows the chatbot to generate automated responses each time a new input is fed into it.
The program chooses the most-fitting response from the closest statement that matches the input, and then delivers a response from the already known selection of statements and responses. Over time, as the chatbot engages in more interactions, the accuracy of response improves.
How To Make A Chatbot In Python?
You can also install ChatterBot‘s latest development version directly from GitHub. For this, you will haveto write and execute the following command:
pip install git+git:github/gunthercox/ChatterBot.git@masterIf you wish to upgrade the command, you can do so as well:
Now that your setup is ready, we can move on to the next step to create chatbot using python. 2. Import Classes Importing classes is the second step in the Python chatbot creation process. All you need to do is import two classes – ChatBot from chatterbot and ListTrainer from chatterbot. To do this, you can executethe following command:
Here, the argument (that corresponds to the parameter name) represents the name of your Python chatbot you wish to disable the bot‘s ability to learn after the training, you can include the ― read_only=True‖ command. The command ― logic_adapte rs‖ denotes the list of adapters used to train the chatbot.
While the ― chatterbot.logic on‖ helps the bot to solve math problems, the ― chatterbot.logic tch‖ helps it to choose the be st match from the list of responses already provided.
Since you have to provide a list of responses, you can do it by specifying the lists of strings that can be later used to train your Python chatbot, and find the best match for each query. Here‘s an example of responses you can train your chatbot using python to learn:
You can a lso create and train the bot by writing an instance of ― ListTraine r‖ and supplying it with a list of strings like so:
Now, your Python chatbot is ready to communicate.
To interact with your Python chatbot, you can use the .get_response() function. This is how it should look while communicating:
However, it is essential to understand that the chatbot using python might not know how to answer all yourquestions. Since its knowledge and training is still very limited, you have to give it time and provide more training data to train it further.
from chatterbot import ChatBot
Create object of ChatBot
class bot = ChatBot('Buddy')
Create object of ChatBot class with Storage
Adapterbot = ChatBot( 'Buddy', storage_adapter='chatterbot.storage', database_uri='sqlite:' )
Create object of ChatBot class with Logic
Adapterbot = ChatBot('Buddy', logic_adapters=['chatterbot.logic', 'chatterbot.logic'], )
from chatterbot import ListTrainer trainer = ListTrainer(bot) trainer(['Hi', 'Hello',
'I need your assistance regarding my order','Please, Provide me with your order id', 'I have a complaint.',
'Please elaborate, your concern', 'How long it will take to receive an order ?', 'An order takes 3-5 Business days to get delivered.','Okay Thanks', 'No Problem! Have a Good Day!' ])
Get a response to the input text 'I would like to book a
flight.' response = bot_response('I have a complaint.')
print("Bot Response:", response) name=input("Enter Your Name: ") print("Welcome to the Bot Service! Let me know how can I help you?")while True: request=input(name+':') if request=='Bye' or request =='bye':print('Bot: Bye') breakelse: response=bot_response(request)print('Bot:',response)
Aim: Case study on Amazon EC2 to learn about Amazon EC2,Amazon Elastic ComputeCloud is a central part of Amazon's cloud computing platform, Amazon Web Services. How EC2 allowsusers torrent virtual computers on which to run their own computer applications.
Software Requirements: Ubuntu 18 PHPMySQL
Hardware Requirements: Pentium IV system with latest configuration
Amazon Elastic Compute Cloud (EC2)
Elastic IP addresses allow you to allocate a static IP address and programmatically assign it to an instance. You can enable monitoring on an Amazon EC2 instance using Amazon CloudWatch2 in order to gain visibility into resource utilization, operational performance and overall demand patterns (including metrics such as CPU utilization, disk reads and writes, and network traffic). You can create Auto feature3 to automatically scale your capacity on certain conditions based on Amazon CloudWatch collects. You can also distribute incoming traffic by creating an elastic load balancer usingthe Elastic Load Balancing4 service. Amazon Elastic Block Storage (EBS)5 volumes provide network Point-in-time consistent snapshots of EBS volumes can be created and stored on Amazon Simple Storage Service(Amazon S3)6. Amazon S3 is highly durable and distributed data store. With a simple web services interface, you can storeand retry at any time, from anywhere on the web using standard HTTP verbs. Copies of objects can be distributed andcached at 14 edge locations around the world by creating a distribution using Amazon CloudFront7 service content). Amazon SimpleDB8 is a web service that provides the core functionality of a database- real-time lookup and simple querying of structured data
complexity. You can organize the dataset into domains and can run queries across all of the Auto-scaling Group using the Auto network-attached persistent storage to Amazon EC2 instances. retrieve large amounts of data as objects in buckets (containers) udFront7 – a web service for content delivery (static or streaming
Amazon Relational Database Service9 (Amazon RDS) provides an easy way to setup, operate and scale a relational database in the cloud. You can launch a DB Instance and get access to a full- featured MySQL database and not worry about common database administration tasks like backups, patch management etc. Amazon Simple Queue Service (Amazon SQS)10 is a reliable, highly scalable, hosted distributed queue for storing messages as they travel between computers and application components.
Amazon Simple Notifications Service (Amazon SNS) provides a simple way to notify applications or people from the cloud by creating Topics and using a publish-subscribe protocol.
Amazon Elastic MapReduce provides a hosted Hadoop framework running on the webscale infrastructure of Amazon Elastic Compute Cloud (Amazon EC2) and Amazon Simple Storage Service (Amazon S3) and allows you to create customized JobFlows. JobFlow is a sequence of MapReduce steps.
Amazon Virtual Private Cloud (Amazon VPC) allows you to extend your corporate network into a private cloud contained within AWS. Amazon VPC uses IPSec tunnel mode that enables you to create asecure connection between a gateway in your data center and a gateway in AWS.
Amazon Route53 is a highly scalable DNS service that allows you manage your DNS records by creating a HostedZone for every domain you would like to manage.
AWS Identity and Access Management (IAM) enable you to create multiple Users with unique security credentials and manage the permissions for each of these Users within your AWS Account. IAMis natively integrated into AWS Services. No service APIs have changed to support IAM, and exiting applications and tools built on top of the AWS service APIs will continue to work when using
AWS also offers various payment and billing services that leverages Amazon‘s payment infrastructure. All AWS infrastructure services offer utility-style pricing that require no longterm commitments or contracts. For example, you pay by the hour for Amazon EC2 instance usage and pay by the gigabyte for storage and data transfer in the case of Amazon S3. More information about each of these services and their pay-as-you-go pricing is available on the
You are free to use the programming model, language, or operating system (Windows,OpenSolaris or any flavor of Linux) of your choice. You are free to pick and choose the AWS products that best satisfy your requirements—you can use anyof the services individually or in any combination. Because AWS provides resizable (storage, bandwidth and computing) resources, you are free to consumeas much or as little and only pay for what you consume. You are free to use the system management tools you‘ve used in the past and extend your datacenter into the cloud.
Launching an EC2 instance
The Choose an Amazon Machine Image (AMI) page displays a list of basic configurations called Amazon Machine Images (AMIs) that serve as templates for your instance. Select the HVM edition of the Amazon Linux 2 AMI.
On the Choose an Instance Type page, choose c5d as the hardwareconfiguration of your instance and Review and Launch.
On Instances details, make sure the Auto-assign Public IP is Enable and you selected Enclaveas Enable. Click on Next: Add Storage
Review the configurations and click next: Add TagesThe ephemeral0 is the Instance Storagebased on NVMe SSD.
A tag consists of a case-sensitive key-value pair. For example, you could define a tag with key = Name andvalue = Webserver. Add a tag and click Next: Configure Security Group
A security group is a set of firewall rules that control the traffic for your instance. On this page, you can add rules to allow specific traffic to reach your instance. For example, if you want to set up a web server and allow Internet traffic to reach yourinstance, add rules that allow unrestricted access to the HTTP and HTTPS ports. Give the Security group a name and Description. Select source as My IP to avoid expose SSH port 22 to the world. Click Review and Launch.
Review Instance Launch and click Launch
In the Select an existing key pair or create a new key pair dialog box, choose Create a new key pair, enter a name for the key pair, and then choose Download Key Pair. This is the only chance for you tosave the private key file, so be sure to download it. Save the private key file in a safe place. You can use C:\user\yourusername\myfirstkey if you are on a Windows machine, and
~/.ssh/myfirstkey if you are on a Mac or Linux machine. You need to provide the name of your key pair when you launch an instance, and the corresponding private key each time you connect to the instance.
A confirmation page lets you know that your instance is launching. Choose View Instances to close the confirmation pageand return to the console. On the Instances page, you can view the status of your instance. It takes a short time for an instance to launch. When you launch an instance, its initial state is pending. After the instance starts, its state changes to running, and it receives a publicDNS name.
Performed case study of Amazon web services: Amazon EC2.
Assignment No: 7
Aim: Case study on Microsoft azure to learn about Microsoft Azure is a cloud computingplatform and infrastructure, created by Microsoft, forbuilding, deploying and managing applications and services through a global network of Microsoft-managed datacenters. How it work, different services provided by it.
Software Requirements: Ubuntu 18 PHPMySQL
Hardware Requirements: Pentium IV system with latest configuration
Theory: Execution Environment
The Windows Azure execution environment consists of a platform for applications and services hosted within one or more roles. The types of roles you can implement in Windows Azure are:
Azure Compute (Web and Worker Roles). A Windows Azure application consists of one or more hosted roles running within the Azure data centers. Typically there will be at least one Web role that is exposed for access by users of the application. The application may contain additional roles, including Worker roles that are typically used to perform background processing and support tasks for Web roles. For more detailed information see “Overview of Creating a Hosted Service for Windows Azure” attechnet.microsoft/en-au/library/gg432976.aspx and “Building an Application that Runs in a Hosted Service” at technet.microsoft/en- au/library/hh180152.
Virtual Machine (VM role). This role allows you to host your own custom instance of the Windows Server 2008 R2 Enterprise or Windows Server 2008 R2 Standard operating system within a Windows Azure data center. For more detailed i