Sub- CSA2001-FUNDAMENTALS IN AI and ML

Submitted by- ABHAY KUMAR (21BAC10020)

List of Experiments:-

E.NO EXPERIMENT NAME

10

11

12
13

14

15
  Prolog stands for programming in logic.
 Prolog is a declarative language, which means that a program consists of data based on the facts and
rules (Logical relationship) rather than computing how to find a solution.

A.Facts
 A fact is like a predicate expression.
 It is used to provide a declarative statement about the problem.
 In a Prolog expression, when a variable occurs, it is assumed to be universally quantified.
 Facts are specified in the form of the head. Head is known as the clause head.
 It will take in the same way as the goal entered at the prompt by the user.
 Whenever a variable occurs in a Prolog expression, it is assumed to be universally
quantified.

For example:

B.Object
 an object is a named collection of predicate definitions.
 In Prolog, data objects are also known as terms.
 The object system can be seen as an extension of SICStus Prolog's module system.
 In addition an object may have attributes that are modifiable.
 Predicate definitions belonging to an object are called methods.
 So, an object is conceptually a named collection of methods and attributes. .
C.Variable
 A variable is a name that is used to stand for a term.
 It can begin with an underscore or lower case letters.

 All variables and arguments are local in scope to the predicate in which they are declared
 Prolog variables are only "variable" until bound (unified) with something else.
 At that point they cease to be variable and become one with that with which they were unified.
 Hence the use of the term "unification": to unify is to become one.
 The special variable _ is the "anonymous variable".

Eg-

D.Predicates

 There was a simple program that has five clauses.

 Head is a compound term for each first three clauses with functor parent.
 We have defined parent relation by stating the n-tuples of objects based on the given info in the
family tree.
 The user can easily query the Prolog system about relations defined in the program.
  A Prolog program consists of clauses terminated by a full stop.
 The arguments of relations can (among other things) be: concrete objects, or constants (such as
pat and jim), or general objects such as X and Y. Objects of the first kind in our program are
called atoms. Objects of the second kind are called variables.
 Questions to the system consist of one or more goals.

Predicate Description

var(X) succeeds if X is currently an un-instantiated variable.

novar(X) succeeds if X is not a variable, or already instantiated

atom(X) is true if X currently stands for an atom

number(X) is true if X currently stands for a number

integer(X) is true if X currently stands for an integer

float(X) is true if X currently stands for a real number.

atomic(X) is true if X currently stands for a number or an atom.

compound(X) is true if X currently stands for a structure.

ground(X) succeeds if X does not contain any un-instantiated variables.

RULES
question can be restated as a general rule:

One person, Teacher, teaches another person, Student if X lectures in a subject, Subject and
Student studies Subject.

In Prolog this is written as:

teaches (Teacher, Student) :-
lectures (Teacher, Student),
studies (Student, Subject).
 This is also called a clause.
 Facts are unit clauses and rules are non-unit clauses. “: -" means "if" or "is implied by".
 This symbol is often called the neck symbol.
 The left-hand side of the neck is called the head. The right-hand side of the neck is
called the body.
 The comma, ",", separating the goals is stands for and.

Try this rule out:

More_advanced (Student1, Student2) :-
year (Student1, Year1),
year (Student2, Year2),
Year1 > Year2.
Note the use of the predefined predicate ">".

 We will give a goal to evaluate and Prolog will work through the clauses in the database.
 In this, Prolog attempts to match the goal with each clause.
 The matching process works from left to right. The goal will fail if no match is found. If a
match is found, the action will take.
 Prolog uses the unification technique, and it is a very general form of matching
technique.
 In unification, one or more variables being given value to make the two call terms
identical. This process is called binding the variables to values.
 For example, Prolog can unify the terms cat(A), and cat(mary) by binding variable A to
atom mary that means we are giving the value mary to variable A.
 Prolog can unify person (Kevin, dane) and person (L, S) by binding L and S to atom kevin
and dane, respectively.
 In starting, all variables have no value. In unification, once a variable bound to the value,
it can be made unbound again and then perhaps be bound to a new value using the
backtracking.

 Arithmetic Operations in Prolog • Prolog arithmetic can be a little surprising ?- X = 3 + 4. X =

3+4 ; • 3 + 4 is just a term whose functor is + and arguments are 3 and 4
 A special predefined operator, is, is provided to circumvent this problem.
 The is operator will force evaluation. So the right way to invoke arithmetic is: ?
 X is 3+4.
  Now the answer will be: X=7
 The addition here was carried out by a special procedure that is associated with the operator +.
 We call such procedures built-in procedures

1.Input/Output: - A Prolog program can read data from input streams, and write data to output
streams.

 Streams are associated with files.

 Data coming from the user's terminal is treated as just another input stream.
 The names of other files can be chosen by the programmer according to the rules of the OS.
 Data output to the terminal is treated as another output stream. Both of these
 "pseudo-files" are referred to by the name user.

2.COMPOUND GOALS: -
 A compound goal is composed using operators similar to those employed by PROLOG,
 that is, the comma for conjunction, the semicolon for disjunction, and the arrow for
conditional execution.
 Three of the several significant extensions to PROLOG syntax and semantics are of
particular interest here

Recursion is a technique in which one predicate uses itself (may be with some other predicates) to find
the truth value.

Let us understand this definition with the help of an example − • is digesting(X,Y) :- just ate(X,Y). • is
digesting(X,Y) :-just ate(X,Z),is digesting(Z,Y).

llowing diagram –

So, we can understand the predecessor relationship is recursive.

We can express this relationship using the following syntax − • predecessor (X, Z): - parent (X, Z). • predecessor (X,
Z): - parent (X, Y), predecessor (Y, Z).

 The list is a simple data structure that is widely used in non-numeric programming. List consists
of any number of items,
 for example, red, green, blue, white, dark. It will be represented as, [red, green, blue, white,
dark]. The list of elements will be enclosed with square brackets.
 A list can be either empty or non-empty. In the first case, the list is simply written as a Prolog
atom, []. In the second case, the list consists of two things as given below –
1. The first item, called the head of the list;
2. The remaining part of the list, called the tail.
 Suppose we have a list like: [red, green, blue, white, dark]. Here the head is red and tail is [green,
blue, white, dark]. So, the tail is another list.
 Now, let us consider we have a list, L = [a, b, c]. If we write Tail = [b, c] then we can also write
the list L as L = [ a | Tail]. Here the vertical bar (|) separates the head and tail parts.
 So, the following list representations are also valid − • [a, b, c] = [x | [b, c] ] • [a, b, c] = [a, b | [c] ]
• [a, b, c] = [a, b, c | [ ] ]
 For these properties we can define the list as –
 A data structure that is either empty or consists of two parts − a head and a tail. The tail itself
has to be a list.

 Dynamic database can change dynamically at execution time and are of two types.

Type1: created at each execution. It grows, shrinks and is deleted at the end of program.

 This type of database is no longer available after program finishes its execution and is called
working memory.

Type2: Other type of dynamic databases are those which are stored in files and called database files.
– These are consulted in any program whenever required.

 These types of databases are not part of any particular program and are available for use in
future by different programs using system defined predicates called save and consult.
1. While executing a Prolog program one can load database file(s) using 'consult' predicate.
2. These files can be updated dynamically at run time and saved using 'save' predicate.
 Clauses can be added to a database at run time using following predicates. asserta(X) &
assertz(X) - succeed by adding fact X in the beginning & at the end of database of facts
respectively.
 For example, asserta(father(mike, john)) adds fact father(mike, john) in the beginning of current
database.
  Clauses can be constructed dynamically and asserted in a dynamic database as follows: start :-
writeln('Input name of mother: '), readln(M), writeln('Input name of child: '), readln(C),
assert(parent(M, C)), assert(female(M)).
 Similarly obsolete clauses can be deleted by using system defined predicate called retract from
dynamic database at the run time.
 For example, retract(father(mike, X)) deletes the first fact father(mike, _) from working memory.

STRINGS

 Strings are a time and space efficient mechanism to handle text in Prolog.
 Strings are stores as a byte array on the global (term) stack and thus destroyed on backtracking
and reclaimed by the garbage collector.
 Strings were added to SWI-Prolog based on an early draft of the ISO standard, offerring a
mechanism to represent temporary character data efficiently.
 As SWI-Prolog strings can handle 0-bytes, they are frequently used through the foreign
language interface for storing arbitrary byte-sequences.
 SWI-Prolog offers garbage collection on the atom-space as well as representing 0-bytes in atoms.

Below are some of the differences:

• creation Creating strings is fast, as the data is simply copied to the global stack.

Atoms are unique and therefore more expensive in terms of memory and time to create.

On the other hand, if the same text has to be represented multiple times, atoms are more efficient.

• destruction Backtracking destroys strings at no cost.

 They are cheap to handle by the garbage collector, but it should be noted that extensive use of
strings will cause many garbage collections. Atom garbage collection is generally faster.
 String objects by default have no syntax and thus can only be created using the predicates below
or through the foreign language interface.
 There are two ways to make read text into strings, both controlled through Prolog flags. One is
by setting the double_quotes flag to string and the other is by setting the backquoted_string flag
to true.
 string_to_atom(?String, ?Atom) Logical conversion between a string and an atom. At least one
of the two arguments must be instantiated. Atom can also be an integer or floating point
number. string_to_list(?String, ?List) Logical conversion between a string and a list of ASCII
characters.
 At least one of the two arguments must be instantiated. string_length(+String, -Length) Unify
Length with the number of characters in String. This predicate is functionally equivalent to and
 also accepts atoms, integers and floats as its first argument.
string_concat(?String1, ?String2, ?String3)

Problem Statement: Perform following String operations with and without pointers to arrays (without
using the library functions

A. substring
B. palindrome
C. compare
D. copy
E. reverse

Explanation:
 For above statement "String operations with and without pointers to arrays without using library
function.
 In first operation(substring), we took 2 strings and check whether string second is a substring of
first our not. If its a substring then here we checking the position of substring in first string.
 In second operation we check a sstring characters in such a manner that- first character
compared with last one, second with second last n so on.
 In third we just check two strings. we compare string character by character from left side.
 In fourth, we just copy string characters of first string into second string which is easy to
understand when you see code for string copy.
 In last, for string reverse used swapping method that swaps first and last character, second n
second last character and so on.

Program:
void substr(char str1[], char str2[]);
int palindrome(char str[]);
int compare(char str1[], char str2[]);
void copy(char str1[], char str2[]);
void reverse(char str[]);int main(){
char str1[100], str2[100];
int result, option;
do {
printf("\n1.Substring Searching");
printf("\n2.Check for Palindrome");
printf("\n3.String Comparison");
printf("\n4.Copy string");
printf("\n5.Reverse String");
printf("\n6.Quit");
printf("\n\nEnter Your Choice:");
scanf("%d", &option);switch (option) {
case 1:
printf("\nEnter 1st string:");
scanf("%s",&str1);
printf("\nEnter 2nd string:");
scanf("%s",&str2);
substr(str1, str2);
printf("\nPress a Character");
getch();
break;case 2:
printf("\n Enter a String:");
scanf("%s",&str1);
result = palindrome(str1);
if (result == 0)
printf("\nNot a palindrome");
else
printf("\nA palindrome");
printf("\nPress a Character");
getch();
break;
case 3:
printf("\nEnter 1st string:");
for (j = 0; str1[i + j] == str2[j] && str2[j] != '\0'; j++);
if (str2[j] == '\0')
printf("\nString found at location : %d", i + 1);
}
}
int palindrome(char str[]) {
int i, j;
i = j = 0;
while (str[j] != '\0')
j++;
while (i < j) {
if (str[i] != str[j - 1])
return (0);
i++;
j--;
}
return (1);
}
int compare(char str1[], char str2[]) {
int i;
i = 0;
while (str1[i] != '\0') {
if (str1[i] > str2[i])
return (1);
if (str1[i] < str2[i])
return (-1);
i++;
}
return (0);
}
void copy(char str2[], char str1[]) {
int i = 0;
while (str1[i] != '\0') {
str2[i] = str1[i];
i++;
}
str2[i] = '\0';}
void reverse(char str[]) {int i, j;char temp;i = j = 0;while
(str[j] != '\0')
j++;
j--;
while (i < j) {
temp = str[i];
str[i] = str[j];
str[j] = temp;
i++;
j--;
}
}
Output:
1.Substring Searching
2.Check for Palindrome
3.String Comparison
4.Copy string
5.Reverse String
6.Quit
Enter Your Choice:1
Enter 1st string:Digvijay
Enter 2nd string:jay
String found at location : 6
Press a Character
1.Substring Searching
2.Check for Palindrome
3.String Comparison
4.Copy string
5.Reverse String
6.Quit
Enter Your Choice:2
Enter a String:racecar
A palindrome
Press a Character
1.Substring Searching
2.Check for Palindrome
3.String Comparison
4.Copy string
5.Reverse String
6.Quit
Enter Your Choice:3
Enter 1st string:sagar
Enter 2nd string:amar
1st>2nd
Press a Character
1.Substring Searching
2.Check for Palindrome
3.String Comparison
4.Copy string
5.Reverse String
6.Quit
Enter Your Choice:4
Enter a String:sasha
Result=sasha
Press a Character
1.Substring Searching
2.Check for Palindrome
3.String Comparison
4.Copy string
5.Reverse String
6.Quit

struct library {
char book_name[20];
char author[20];
int pages;
float price;
};
// Driver Code
int main()
{
// Create a instance
struct library lib[100];
char ar_nm[30], bk_nm[30];
// Keep the track of the number of
// of books available in the library
int i, input, count;
i = input = count = 0;
// Iterate the loop
while (input != 5) {
printf("\n\n********######"
"WELCOME TO E-LIBRARY "
"#####********\n");
printf("\n\n1. Add book infor"
"mation\n2. Display "
"book information\n");
printf("3. List all books of "
"given author\n");
printf(
"4. List the count of book"
"s in the library\n");
printf("5. Exit");
// Enter the book details
printf("\n\nEnter one of "
"the above: ");
scanf("%d", &input);
// Process the input
switch (input) {
// Add book
case 1:
printf("Enter book name = ");
scanf("%s", lib[i].book_name);
printf("Enter author name = ");
scanf("%s", lib[i].author);
printf("Enter pages = ");
scanf("%d", &lib[i].pages);
printf("Enter price = ");
scanf("%f", &lib[i].price);
count++;
break;
// Print book information
case 2:
printf("you have entered"
" the following "
"information\n");
for (i = 0; i < count; i++) {
printf("book name = %s",
lib[i].book_name);
printf("\t author name = %s",
lib[i].author);
printf("\t pages = %d",
lib[i].pages);
// Take the author name as input
case 3:
printf("Enter author name : ");
scanf("%s", ar_nm);
for (i = 0; i < count; i++) {
if (strcmp(ar_nm,
lib[i].author)== 0)
printf("%s %s %d %f",
lib[i].book_name,
lib[i].author,
lib[i].pages,
lib[i].price);}
break;
// Print total count
case 4:
printf("\n No of books in "
"brary : %d",count);
break;
case 5:
exit(0);}}
return 0

class Graph:
# Constructor
def init (self):
# default dictionary to store graph
self.graph = defaultdict(list)
# function to add an edge to graph
def addEdge(self, u, v):
self.graph[u].append(v)
# A function used by DFS
def DFSUtil(self, v, visited):
visited.add(v)
print(v, end=' ')
for neighbour in self.graph[v]:
if neighbour not in visited:
self.DFSUtil(neighbour, visited)
def DFS(self, v):
visited = set()
self.DFSUtil(v, visited)
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
print("Following is DFS from (starting from vertex 2)")
g.DFS(2)

class Graph:
def init (self)
self.graph = defaultdict(list)
def addEdge(self,u,v):
self.graph[u].append(v)
def BFS(self, s):
visited = [False] * (max(self.graph) + 1)
# Create a queue for BFS
queue = []

queue.append(s)
visited[s] = True
while queue:

s = queue.pop(0)
print (s, end = " ")
for i in self.graph[s]:
if visited[i] == False:
queue.append(i)
visited[i] = True

g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
print ("Following is Breadth First Traversal"
" (starting from vertex 2)")
g.BFS(2)

# problem using naive approach.

from sys import maxsize
from itertools import permutations
V = 4
# implementation of traveling Salesman Problem
def travellingSalesmanProblem(graph, s):
# store all vertex apart from source vertex
vertex = []
for i in range(V):
if i != s:
vertex.append(i)
# store minimum weight Hamiltonian Cycle
min_path = maxsize
next_permutation=permutations(vertex)
for i in next_permutation:
# store current Path weight(cost)
current_pathweight = 0
path weight
k = s
for j in i:
current_pathweight += graph[k][j]
k = j
current_pathweight += graph[k][s]
# update minimum
min_path = min(min_path, current_pathweight)
return min_path
# Driver Code
if name == " main ":
# matrix representation of graph
graph = [[0, 10, 15, 20], [10, 0, 35, 25],
[15, 35, 0, 30], [20, 25, 30, 0]]
s = 0
print(travellingSalesmanProblem(graph, s)

board=['0','1','2','3','4','5','6','7','8']
empty = [0,1,2,3,4,5,6,7,8]

def display_board():
print(' | | ')
print(board[0]+' | '+board[1]+' | '+board[2])
print(' | | ')
print('---------')
print(' | | ')
print(board[3]+' | '+board[4]+' | '+board[5])
print(' | | ')
print('---------')
print(' | | ')
print(board[6]+' | '+board[7]+' | '+board[8])
print(' | | ')
def player_input(player):
player_symbol = ['X','O']
correct_input = True
position = int(input('player {playerNo} chance! Choose field to fill
{symbol} '.format(playerNo = player +1, symbol = player_symbol[player])))
if board[position] == 'X' or board[position] == 'O':
correct_input = False
if not correct_input:
print("Position already equipped")
player_input(player)
else:
empty.remove(position)
board[position] = player_symbol[player]
return 1

def check_win():
player_symbol = ['X','O']
winning_positions
=[[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]]
for check in winning_positions:
first_symbol = board[check[0]]
if first_symbol != ' ':
won = True
for point in check:
if board[point] != first_symbol:
won = False
break
if won:
if first_symbol == player_symbol[0]:
print('player 1 won')
else:
print('player 2 won')
break
else:
won = False
if won:
return 0
else:
 return 1

def play():
player = 0
while empty and check_win():
display_board()
player_input(player)
player = int(not player)
if not empty:
print("NO WINNER!")

if __name__ == '__main__':
play()