Artificial Intelligence Lab (BTCS-704) Nida 1603502

PRACTICAL-1
AIM: WAP of Recursion pseudo code and example.

Recursion pseudo code:

prodedure fanc(A[n] , p , q ) //(this is my array,first digit of A ,last digit of A)

if A[n/2] >= 0

return fanc(A[n/2] , A[n/2] , A[n-1])

else

return fanc(A[n/2] , A[0] , A[n/2 -1])

if p<q

print p

else

print q

Recursion Example: C Program to find factorial of a given number using recursion

#include <stdio.h>
 int factorial(int);

 int main()

{
int num;
int result;

printf("Enter a number to find it's Factorial: ");

scanf("%d", &num);

if (num < 0)

{
printf("Factorial of negative number not possible\n");
}

Chandigarh Engineering College 1 Dr. B K Verma

Artificial Intelligence Lab (BTCS-704) Nida 1603502

Else
{

result = factorial(num);
printf("The Factorial of %d is %d.\n", num, result);

}
return 0;
}

int factorial(int num)

if (num == 0 || num == 1)

{
return 1;

Else
{
return(num * factorial(num - 1));
}}

$ cc pgm5.c

$ a.out

Enter a number to find it's Factorial: 6

The Factorial of 6 is 720.

Chandigarh Engineering College 2 Dr. B K Verma

Artificial Intelligence Lab (BTCS-704) Nida 1603502

PRACTICAL-2
AIM: WAP of Brute force solution to the knapsack problem.

Brute force solution pseudo code:

# let w[1], ... , w[n] be the weights of the items
# let v[1], ... , v[n] be the values of the items
# let maxWeight be the capacity of the knapsack
bestValue := 0
function solve(n, currentWeight, currentValue) {
if n = 0 and currentWeight <= maxWeight and currentValue > bestValue:
bestValue := currentValue
if n = 0: return
# don't pack this item
solve(n-1, currentWeight, currentValue)
# pack this item
solve(n-1, currentWeight + w[n], currentValue + v[n])
}
solve(n, 0, 0)
print bestValue

Example:
#include <stdio.h>

int max(int a, int b) { return (a > b)? a : b; }

// Returns the maximum value that can be put in a knapsack of capacity W

int knapsack(int W, int wt[], int val[], int n)

{
int i, w;
int K[n+1][W+1];

Chandigarh Engineering College 3 Dr. B K Verma

Artificial Intelligence Lab (BTCS-704) Nida 1603502

// Build table K[][] in bottom up manner

for (i = 0; i <= n; i++)

for (w = 0; w <= W; w++)

if (i==0 || w==0)

K[i][w] = 0;

else if (wt[i-1] <= w)

K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);

else
K[i][w] = K[i-1][w];

}}
return K[n][W];

}
int main()

int val[] = {60, 100, 120};

int wt[] = {10, 20, 30};
int W = 50;
int n = sizeof(val)/sizeof(val[0]);
printf("\nValue = %d", knapsack(W, wt, val, n));
return 0;
}

$ gcc knapsack.c -o knapsack

$ ./knapsack

Value = 220

Chandigarh Engineering College 4 Dr. B K Verma

Artificial Intelligence Lab (BTCS-704) Nida 1603502

PRACTICAL-3
AIM: WAP of graph coloring problem.

Basic Graph Coloring Algorithm:

1. Color first vertex with first color.
2. Do following for remaining V-1 vertices.
….. a) Consider the currently picked vertex and color it with the
lowest numbered color that has not been used on any previously
colored vertices adjacent to it. If all previously used colors
appear on vertices adjacent to v, assign a new color to it.

Chandigarh Engineering College 5 Dr. B K Verma

Artificial Intelligence Lab (BTCS-704) Nida 1603502

Example:
// A C++ program to implement greedy algorithm for graph coloring
#include <iostream>
#include <list>
using namespace std;
// A class that represents an undirected graph
class Graph
{
   int V;    // No. of vertices
 list<int> *adj;    // A dynamic array of adjacency lists
public:
  // Constructor and destructor
 Graph(int V)   { this->V = V; adj = new list<int>[V]; }
 ~Graph()       { delete [] adj; }
 // function to add an edge to graph
void addEdge(int v, int w);  
    // Prints greedy coloring of the vertices
 void greedyColoring();
};
void Graph::addEdge(int v, int w)
{
 adj[v].push_back(w);
adj[w].push_back(v);  // Note: the graph is undirected
}
// Assigns colors (starting from 0) to all vertices and prints
// the assignment of colors
void Graph::greedyColoring()
{
 int result[V];
 // Assign the first color to first vertex
 result[0]  = 0;
// Initialize remaining V-1 vertices as unassigned
for (int u = 1; u < V; u++)
 result[u] = -1;  // no color is assigned to u
// A temporary array to store the available colors. True
// value of available[cr] would mean that the color cr is
// assigned to one of its adjacent vertices
 bool available[V];
for (int cr = 0; cr < V; cr++)
 available[cr] = false;
// Assign colors to remaining V-1 vertices
 for (int u = 1; u < V; u++)
 // Process all adjacent vertices and flag their colors
 // as unavailable

Chandigarh Engineering College 6 Dr. B K Verma

Artificial Intelligence Lab (BTCS-704) Nida 1603502

 list<int>::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
  if (result[*i] != -1)
available[result[*i]] = true;
 // Find the first available color
  int cr;
for (cr = 0; cr < V; cr++)
if (available[cr] == false)
break;
result[u] = cr; // Assign the found color
// Reset the values back to false for the next iteration
for (i = adj[u].begin(); i != adj[u].end(); ++i)
 if (result[*i] != -1)
available[result[*i]] = false; }
// print the result for (int u = 0; u < V; u++)
 cout << "Vertex " << u << " --->  Color "
<< result[u] << endl;
}
// Driver program to test above function
int main()
{
 Graph g1(5);
 g1.addEdge(0, 1);
 g1.addEdge(0, 2);
 g1.addEdge(1, 2);
 g1.addEdge(1, 3);
 g1.addEdge(2, 3);
g1.addEdge(3, 4);
cout << "Coloring of graph 1 \n";
 g1.greedyColoring();
Graph g2(5);
g2.addEdge(0, 1);
 g2.addEdge(0, 2);
 g2.addEdge(1, 2);
 g2.addEdge(1, 4);
g2.addEdge(2, 4);
 g2.addEdge(4, 3);
 cout << "\nColoring of graph 2 \n";
  g2.greedyColoring();
return 0;
}

Chandigarh Engineering College 7 Dr. B K Verma

Artificial Intelligence Lab (BTCS-704) Nida 1603502

Output:

Coloring of graph 1

Vertex 0 ---> Color 0

Vertex 1 ---> Color 1

Vertex 2 ---> Color 2

Vertex 3 ---> Color 0

Vertex 4 ---> Color 1

Coloring of graph 2

Vertex 0 ---> Color 0

Vertex 1 ---> Color 1

Vertex 2 ---> Color 2

Vertex 3 ---> Color 0

Vertex 4 ---> Color 3

Chandigarh Engineering College 8 Dr. B K Verma

Artificial Intelligence Lab (BTCS-704) Nida 1603502

PRACTICAL-4
AIM: WAP of array structure.
#include <stdio.h>

struct Bookinfo

{
char[20] bname;

int pages;

int price;

}
book[3];
int main(int argc, char *argv[])

int i;

for(i=0;i<3;i++)

printf("\nEnter the Name of Book : ");

gets(book[i].bname);

printf("\nEnter the Number of Pages : ");

scanf("%d",book[i].pages);

printf("\nEnter the Price of Book : ");

scanf("%f",book[i].price);

} printf("\n--------- Book Details ------------ ");for(i=0;i<3;i++)

{
printf("\nName of Book : %s",book[i].bname);

printf("\nNumber of Pages : %d",book[i].pages);

printf("\nPrice of Book : %f",book[i].price);

Chandigarh Engineering College 9 Dr. B K Verma

Artificial Intelligence Lab (BTCS-704) Nida 1603502

}
return 0;
}

Output of the Structure Example:

Enter the Name of Book : ABC

Enter the Number of Pages : 100

Enter the Price of Book : 200

Enter the Name of Book : EFG

Enter the Number of Pages : 200

Enter the Price of Book : 300

Enter the Name of Book : HIJ

Enter the Number of Pages : 300

Enter the Price of Book : 500

--------- Book Details ------------

Name of Book : ABC

Number of Pages : 100

Price of Book : 200

Name of Book : EFG

Number of Pages : 200

Price of Book : 300

Name of Book : HIJ

Number of Pages : 300

Price of Book : 500

Chandigarh Engineering College 10 Dr. B K Verma

Artificial Intelligence Lab (BTCS-704) Nida 1603502

PRACTICAL-5
AIM: Write A Program on loop detection

/ C++ program to detect loop in a linked list

#include<bits/stdc++.h>
using namespace std;
  
/* Link list node */
struct Node
{
    int data;
    struct Node* next;
};
  void push(struct Node** head_ref, int new_data)
{
    /* allocate node */
    struct Node* new_node = new Node;
  
    /* put in the data  */
    new_node->data  = new_data;
  
    /* link the old list off the new node */
    new_node->next = (*head_ref);
  
    /* move the head to point to the new node */
    (*head_ref)    = new_node;
}
  
// Returns true if there is a loop in linked list
// else returns false.
bool detectLoop(struct Node *h)
{
    unordered_set<Node *> s;
    while (h != NULL)
    {
        // If this node is already present
        // in hashmap it means there is a cycle
        // (Because you we encountering the
        // node for the second time).
        if (s.find(h) != s.end())
            return true;
  
        // If we are seeing the node for
        // the first time, insert it in hash
    s.insert(h);

Chandigarh Engineering College 11 Dr. B K Verma

Artificial Intelligence Lab (BTCS-704) Nida 1603502

    h = h->next;
    }
  return false;
}
  
/* Drier program to test above function*/
int main()
{
    /* Start with the empty list */
    struct Node* head = NULL;
  
    push(&head, 20);
    push(&head, 4);
    push(&head, 15);
    push(&head, 10);
  
    /* Create a loop for testing */
    head->next->next->next->next = head;
  
    if (detectLoop(head))

cout<<”loop found”;

else

cout<<”loop not found”;

return 0;

Output: loop found

Chandigarh Engineering College 12 Dr. B K Verma

Artificial Intelligence Lab (BTCS-704) Nida 1603502

PRACTICAL-6
AIM: Write A Program to generate output for A*

Algorithm. S/W Requirement: LispWorks IDE, Emacs Editor and SLIME.

;;; ASTAR.CL
;;; A* Search for a shortest path.
;;; Here is the representation of the adjacency distance data,
;;; plus functions for getting at it and at solution path info.
;;; This code is identical to that in UNIFCOST.CL
(let ((distance-info (make- hash-table :size 20))
(path-predecessor-info (make-hash-table :size 20))
) (defun set-distances (x y)
(setf (gethash x distance-info) y) ) (defun
get-distances (x)
(gethash x distance- info) )
(defun set- predecessor (x y)
(setf (gethash x path-predecessor-info)
y) ) (defun get-predecessor (x) (gethash x
path-predecessor-info) )
)
;;; Here are actual inter-city distances from theMichelin map:
(set-distances 'brest '((rennes .244)))
(set-distances 'rennes '((caen . 176)(paris . 348)
(brest . 244)(nantes . 107)))
(set-distances 'caen '((calais . 120)(paris . 241)(rennes . 176)))
(set-distances 'calais '((nancy . 534)(paris . 297)(caen . 120)))
(set-distances 'nancy '((strasbourg . 145)(dijon . 201)
(paris . 372)(calais . 534))) (set-distances 'strasbourg
'((dijon . 335)(nancy . 145))) (set-distances 'dijon
'((strasbourg .
335)(lyon . 192)
(paris . 313)(nancy . 201)))
(set-distances 'lyon '((grenoble . 104)(avignon . 216)
(limoges . 389)(dijon . 192))) (set-distances 'grenoble '((avignon .
227)(lyon . 104))) (set-distances 'avignon '((grenoble .
227)(marseille . 99)
(montpellier . 121)(lyon . 216))) (set-distances

Chandigarh Engineering College 13 Dr. B K Verma

Artificial Intelligence Lab (BTCS-704) Nida 1603502

'marseille '((nice . 188)(avignon . 99))) (set-distances

'nice '((marseille . 188)))
(set-distances 'montpellier '((avignon . 121)(toulouse . 240)))
(set-distances 'toulouse '((montpellier .
240)(bordeaux . 253)
(limoges . 313)))
(set-distances 'bordeaux '((limoges . 220)(toulouse . 253)
(nantes . 329)))
(set-distances 'limoges '((lyon . 389)(toulouse . 313)
(bordeaux . 220)(nantes . 329)(paris .
396))) (set-distances 'nantes '((limoges . 329)
(bordeaux . 329)
(rennes . 107)))
(set-distances 'paris '((calais . 297)(nancy . 372)(dijon .313)
(limoge.396)(rennes . 348)(caen . 241)))
;;; And here is the hash table F-VALUES to
;;; remember the heuristic value at each node visited.
;;; We also need a hash table for G-
VALUES. (let ((f-values (make-hash- table
:size 20))
(g-values (make-hash-table :size 20)) ) (defun
set-f-value (x y)
(setf (gethash x f-values)
y) ) (defun get-f-value (x)
(gethash x f-values) ) (defun set-
g-value (x y) (setf (gethash x g-
values)
y) ) (defun get-g-value (x)
(gethash x g-values) )
)

;;; Next is the information about longitude, which is the same

;;; as that used in BESTFS2.CL
(let ((longitude-info (make-hash-table :size 20)))
(defun set-longitude (x y)
(setf (gethash x longitude-info) y) ) (defun

Chandigarh Engineering College 14 Dr. B K Verma

Artificial Intelligence Lab (BTCS-704) Nida 1603502

get-longitude (x)
(gethash x longitude-info) ))
;;; The longitude of each city is stored in tenths of a degree.
;;; We again use a local function with a LAMBDA form, since
;;; SET-LONGITUDE takes two arguments but we want a
;;; function that takes one argument for this use with MAPCAR.
(mapcar #'(lambda (pair) (apply #'set-longitude pair))
'((avignon 48)(bordeaux -6)(brest -45)(caen-4)
(calais 18)(dijon51)(grenobl57)(limoges 12) (lyon 48)
(marseille 53)(montpellier 36) (nantes -16)(nancy 62)(nice
73)(paris 23) (rennes -17)(strasbourg 77)(toulouse 14) ) )

;;; Now we are ready for the algorithm itself.

;;; A-STAR-SEARCH is the main searching procedure. (defun a-star-
search (start-node goal- node)
"Performs a search with the A*
algorithm." (set-goal goal-node) (let
((open (list start-node));
step1 (closed nil) x
successors)
(set-predecessor start-node nil)
(set-g-value start-node 0)
(set-f-value start-node (f start- node))
(loop
(if (nullopen)(return'failure));
step2 (setf x(select-bestopen));
step3 (setf open (remove xopen));
step4(push x closed)
(if (eql x (get-goal))
(return (extract-pathx));
step5 (setf successors (getsuccessorsx));
step6(dolist(ysuccessors);
step7 (if (not (or (memberyopen)
(memberyclosed) ))(progn(increment-
count)17)(strasbourg 77)(toulouse 14) ) );;;
Now we are ready for the algorithm itself.;;;

Chandigarh Engineering College 15 Dr. B K Verma

Artificial Intelligence Lab (BTCS-704) Nida 1603502

A-STAR-SEARCH is the main searching

procedure. (defun a-star-search (start-node
gonode)
"Performs a search with the A*
algorithm." (set-goal goal-node) (let
((open (list start-node));
step1 (closed nil) x
successors)
(set-predecessor start-node nil) (set-g-value start-node 0)
(set-f-value start-node (f start- node))
(loop
(if (nullopen)(return'failure);
step2 (setf x(select-bestopen));
step3 (setf open (remove xopen));
step4(push x closed)

(if (eql x (get-goal))

(return (extract-pathx)));
step5 (setf successors (get-successorsx));
step6(dolist(ysuccessors);
step7 (if (not (or (memberyopen)
(member y closed) ))
(progn(increment-count)
open)) (setf closed
(remove y closed) ) ) ) ) ) ) ) ); end of loop -------- this is implicitly
step8
)))
;; The supporting functions:
;;; Use local variable to keep track of the goal. (let
(goal)
(defun set-goal (the-goal) (setf goal the-goal)) (defun
get-goal () goal) )
;;; F is the sum of G and H. (defun f (n) "Computes
F value for node
N." (+ (get-g-value n) (h n)) )

Chandigarh Engineering College 16 Dr. B K Verma

Artificial Intelligence Lab (BTCS-704) Nida 1603502

;;; G computes the distance from the start node to NODE

;;; by adding the distance from X to NODE to X's distance.
(defun g (node x)
"Returns distance from START-NODE to NODE"
(+ (get-g-value x) (arc-dist x node)) )
;;; H evaluates the difference in longitude between
;;; the current node N and the goal node.
(defun h (n)
"Returns an estimate of the distance from N to
the goal."
(* 10 (longitude-diff n (get-goal))) )
;;; LONGITUDE-DIFF returns the absolute value of the
;;; difference in longitudes between nodes N1 and N2
;;; in tenths of a degree. (defun
longitude-diff (n1 n2)
"Computes difference in longitudes."
(abs (- (get-longitude n1) (get-longitude n2))) )
;;; SELECT-BEST chooses a node in step 3... (defun
select-best (lst)
"Returns the best node on LST for expansion."
(if (eql (first lst) (get-goal))
(first lst)
(better (first lst)(rest lst)) ) )
;;; The helping function BETTER for SELECT-BEST checks
;;; to see if there is a goal node on LST with FVALUE
;;; as low as that of ELT. If so, it returns the goal node.
;;; If not, it returns ELT. (defun
better (elt lst)
"Returns a goal-node on LST if it has an equal value,
otherwise ELT."
(cond ((null lst) elt)
((< (get-f-value elt)(get-f-value
(firstlst)))elt)
((eql (first lst) (get- goal))
(first lst) )

Chandigarh Engineering College 17 Dr. B K Verma

Artificial Intelligence Lab (BTCS-704) Nida 1603502

(t (better elt (rest lst))) ) )

;;; INSERT puts NODE onto LST, which is ordered;;; by
FVALUE.
(defun insert (node lst)
"Inserts NODE onto LST, according to FVALUE ordering."
(cond ((null lst)(list node))
((< (get-f-value node) (get-f-
value (first lst)) ) (cons node
lst)) (t (cons (first lst)
(insert node (rest lst)) )) ) )
;;; EXTRACT-PATH returns the sequence of cities found. (defun extract-path (n) count)
(format t "A-star-search solution:
~s.~%" (a-star-search 'rennes
'avignon) )
(format t "Path-length: ~s.~%" (get-f-
value 'avignon) ) (format t "~snodes
expanded.~%" (get-count) )) (test)

Output:

Chandigarh Engineering College 18 Dr. B K Verma