CsitLabs
  • CSIT Labs
  • 1st Semester
    • Digital Logics
      • Lab 1
      • Lab 2
      • Lab 3
      • Lab 4
      • Lab 5
      • Lab6
    • IIT
    • Physics Lab Report Formet
  • 2nd Semester
    • Algorithms used in Discrete Structure class
    • Microprocessor
      • 8085 Microprocessor
        • Arithmetic and Logical Instruction Set
        • Branching Instruction Set
        • Data Transfer and Instruction Set
        • Multiply, Divide and Memory Block Operations
        • Rotate Instruction Set
        • Subroutine, Stack and BCD Conversion](Subroutine_Stack_BCD_Conversion
      • 8086 Microprocessor
        • Basic Arithmetic
        • Practice Programs for 8086 Microprocessor
        • String Processing
    • Object Oriented Programming using C++
      • File Access Pointers
      • Standard Exceptions in C++
    • Statistics-I
  • 3rd Semester
    • Computer Architecture
      • Practical labs
    • Computer Graphics
      • Practial
      • Simulation of Two Dimensional Transformation
      • Scan Conversion Algorithm
    • Data Structures and Algorithms
      • Array methods (Introduction)
      • Stack
      • Queue
      • Recursion
      • Linked List
      • Sorting Algorithms
      • Searching and Hashing Algorithms
      • Trees and Graphs
      • Lab practice
    • Numerical Method Labs
      • Lab practice
    • Statistics-II Labs
      • Confidence interval of mean assuming normal distribution
      • One Sample T test
      • Two Sample T test
      • Regression Analysis
      • Two Sample T test
      • Design_of_Experiment
        • CRD (Completely Randomized Design)
        • RBD (Randomized Block Design)
        • RBD (Randomized Block Design)
      • Non-parametric_test
        • Binomial Test
        • Cochran Q test
        • Kolmogorov-Smirnov one sample test
        • Run test
        • Friedman-F_test
          • Friedman F test
          • Friedman F test
        • Kruskal-Wallis-H_test
          • Kruskal Wallis H test
          • Kruskal Wallis H test
        • Mann-Whitney-U_test
          • Mann Whitney U test
          • Mann Whitney U test
        • Median_test
          • Median Test
          • Median Test
        • Wilcoxon-Matched-pair_signed_rank_test
          • Wilcoxon Matched pair signed rank test
          • Wilcoxon Matched pair signed rank test
  • 4th Semester
    • Artificial Intelligence
    • Computer Networks
      • Networking commands in CMD
    • DBMS Lab
    • Operating System
      • Linux Commands
    • Theory of Computation
      • Lab 1 (DFA)
      • Lab 2 (NFA)
  • 5th Semester
    • Cryptography
    • Design and Analysis of algorithms
    • Multimedia
      • Animation Creation with Blender
      • FL Studio - Simple Effect Creation
      • Macromedia FreeHand - Logo Creation
      • Audio Mixing
      • Adobe Photoshop - ID Card Creation
      • Video Editing with Adobe Premiere Pro
    • Simulation & Modeling
      • Lab 1: Random Number Generation
    • System Analysis and Design
    • Web Technology
      • Lab Assignment – I (HTML)
      • Lab Assignment – II (CSS)
      • Lab Assignment – III (JavaScript and XML)
      • Lab Assignment – IV (PHP)
      • Web Technology
        • php
          • Database connection using PHP and MySQL
          • Login form
          • Login form
  • 6th Semester
    • Compiler Design and Construction
    • NET Centric Computing
      • Class Codes
        • Authentication and Authorization in ASP.NET
        • C# Basics
      • Lab Codes
        • Practical 1
        • Practical 2
          • Number Operations Web App
          • User Registration Form
          • User Registration Console App
        • Practical 3
          • Authentication and Authorization (Claims, Roles and Policies)
          • Client side state management in ASP.NET
          • Entity Framework Core
          • Form Validation
            • React form validation
          • HTML Tag Helpers
          • MVC demonstration
          • Razor Syntax
          • Server Side State Management in ASP.NET
      • Self Projects
        • Do while programs
        • Role playing game battle challenge
        • Project overview
        • Authentication
          • wwwroot
            • lib
              • jquery-validation
                • The MIT License (MIT)
  • 7th Semester
    • Advanced Java Programming
      • Class Codes
        • Unit1-6&8
          • javafx-sdk-21.0.1
            • legal
              • javafx.graphics
                • Independent JPEG Group (IJG) JPEG v9e
                • Mesa 3-D Graphics Library v21.0.3
              • javafx.media
                • Microsoft DirectShow Samples v156905
                • GNU Glib v2.72.0
                • GStreamer v1.20.1
                • LibFFI v3.4.4
              • javafx.web
                • IBM International Components for Unicode (ICU4C) v73.1
                • xmlsoft.org: libxml2 v2.10.4
                • xmlsoft.org: libxslt v1.1.35
                • WebKit Open Source Project: WebKit v616.1
          • src
            • main
              • java
                • Unit 1: Programming in Java
                  • 2. Concepts and Topics
                • Unit 2: User Interface Components with Swing
                • Unit 3: Event Handling
                • Unit 4: Database Connectivity
                • Unit 5: Network Programming
                • Unit 6: GUI with JavaFX
        • Unit7
          • src
            • main
              • webapp
                • index
      • Lab Codes
        • Lab
          • src
            • main
              • java
                • Practical 1
                • Practical 2
                • Practical 3
                • Practical 4
                • Practical5
    • Data warehouse and Data mining
  • docs
    • Contributor Covenant Code of Conduct
Powered by GitBook
On this page
  • Programs
  • Theory
  • Breadth First Search
  • Depth First Search
  • Iterative Deepening Depth First Search
  • Greedy Best First Search
  • A* Search
  • n Queens Problem
  • Water Jug Problem
  • Tower of Hanoi
  • Alpha Beta Pruning
  • Hill climbing algorithm
  • Tic-Tac-Toe
  • Constraint Satisfaction Problem
  • NAND using Perceptron

Was this helpful?

  1. 4th Semester

Artificial Intelligence

Previous4th SemesterNextComputer Networks

Last updated 8 months ago

Was this helpful?

Programs

Theory

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key'[1]), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

Algorithm:

  1. Create a queue and enqueue source into it. Mark source as visited.

  2. While queue is not empty, do following

    1. Dequeue a vertex from queue. Let this be u.

    2. If u is the destination, then return true.

    3. Else, continue following steps

    4. Enqueue all adjacent vertices of u which are not yet visited.

    5. Mark them visited and continue from step 2.

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

Algorithm:

  1. Create a stack and push source into it. Mark source as visited.

  2. While stack is not empty, do following

    1. Pop a vertex from stack. Let this be u.

    2. If u is the destination, then return true.

    3. Else, continue following steps

    4. Push all adjacent vertices of u which are not yet visited.

    5. Mark them visited and continue from step 2.

Iterative deepening depth-first search (IDDFS) is an extension to the 'vanilla' depth-first search algorithm, with an added constraint on the total depth explored per iteration. IDDFS is optimal like breadth-first search, but uses much less memory; at each iteration, it visits the nodes in the search tree in the same order as depth-first search, but the cumulative order in which nodes are first visited is effectively breadth-first.

Algorithm:

  1. Perform a depth-first search to depth 1, starting from the root.

  2. Provided it didn't find the goal, perform a depth-first search to depth 2, starting from the root.

  3. Provided it didn't find the goal, perform a depth-first search to depth 3, etc., etc.

Greedy best-first search is a best-first search that uses heuristics to improve speed. It expands the most promising node chosen according to the heuristic function. Greedy best-first search algorithm is a search algorithm which is used to solve many problems among them the most common one is the 8-puzzle. It is an informed search algorithm as it uses information about path cost and also uses heuristics to find the solution. It is a best-first search algorithm in which the cost associated with a node is f(n) = h(n). It expands the node that is estimated to be closest to the goal. It is not optimal as it does not guarantee the shortest path. It is complete as it will always find a solution if one exists. It is faster than breadth-first search but slower than A* search.

Algorithm:

  1. Create a priority queue and enqueue source into it. Mark source as visited.

  2. While queue is not empty, do following

    1. Dequeue a vertex from queue. Let this be u.

    2. If u is the destination, then return true.

    3. Else, continue following steps

    4. Enqueue all adjacent vertices of u which are not yet visited.

    5. Mark them visited and continue from step 2.

A* is the most popular choice for pathfinding, because it’s fairly flexible and can be used in a wide range of contexts. A* is like Dijkstra’s Algorithm in that it can be used to find a shortest path. A* is like Greedy Best-First-Search in that it can use a heuristic to guide itself.

Algorithm:

  1. Create a priority queue and enqueue source into it. Mark source as visited.

  2. While queue is not empty, do following

    1. Dequeue a vertex from queue. Let this be u.

    2. If u is the destination, then return true.

    3. Else, continue following steps

    4. Enqueue all adjacent vertices of u which are not yet visited.

    5. Mark them visited and continue from step 2.

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. Given an integer n, print all distinct solutions to the n-queens puzzle. Each solution contains distinct board configurations of the n-queens’ placement, where the solutions are a permutation of [1,2,3..n] in increasing order, here the number in the ith place denotes that the ith-column queen is placed in the row with that number. For eg below figure represents a chessboard [3 1 4 2].

Algorithm:

  1. Start in the leftmost column

  2. If all queens are placed

    1. return true

  3. Try all rows in the current column. Do following for every tried row.

    1. 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.

    2. If placing the queen in [row, column] leads to a solution then return true.

  4. If all rows have been tried and nothing worked, return false to trigger backtracking.

  1. J1 and j2 are two jugs

  2. (x, y) : order pair

  3. x: maximum water storage capacity of jug1 is 4 gallons i.e. x=4

  4. y: maximum water storage capacity of jug2 is 3 gallons i.e. y=3

  5. No mark on jug

  6. Pump to fill the water into the jug

  7. How can you get exactly 2 gallon of water into the 4-gallons jug?

Solution:

The Tower of Hanoi is a mathematical game or puzzle. It consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks stacked on one rod in order of decreasing size, the smallest at the top, thus approximating a conical shape. 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 or on an empty rod.

  3. No larger disk may be placed on top of a smaller disk.

Algorithm:

  1. Move top n-1 disks from source to auxiliary tower.

  2. Move the nth disk from source to destination tower.

  3. Move the n-1 disks from auxiliary tower to destination tower.

Alpha–beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games (Tic-tac-toe, Chess, Go, etc.). It stops evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further. When applied to a standard minimax tree, it returns the same move as minimax would, but prunes away branches that cannot possibly influence the final decision.

Algorithm:

  1. Initialize alpha with -INFINITY and beta with +INFINITY.

  2. Maximizer and Minimizer are two players.

  3. Maximizer makes a move and calls Minimizer.

  4. Minimizer makes a move and calls Maximizer.

  5. Repeat the above two steps till any one of the player wins the game or the game ends.

  6. At each level, compare the value of alpha and beta.

  7. If alpha is greater than or equal to beta, stop further evaluation and return alpha.

  8. Else, return beta.

Hill climbing algorithm is a local search algorithm which continuously moves in the direction of increasing elevation/value to find the peak of the mountain or best solution to the problem. It terminates when it reaches a peak value where no neighbor has a higher value. Hill climbing algorithm is a technique which is used for optimizing the mathematical problems. One of the widely discussed examples of Hill climbing algorithm is Traveling-salesman Problem in which we need to minimize the distance traveled by the salesman. It is also called greedy local search as it only looks to its good immediate neighbor state and not beyond that. A node of hill climbing algorithm has two components which are state and value. Hill Climbing is mostly used when a good heuristic is available. In this algorithm, we don't need to maintain and handle the search tree or graph as it only keeps a single current state.

Algorithm:

  1. Evaluate the initial state, if it is goal state then return success and Stop.

  2. Loop Until a solution is found or there is no new operator left to apply.

  3. Select and apply an operator to the current state.

  4. Check new state:

    1. If it is goal state, then return success and quit.

    2. Else if it is better than the current state then assign new state as a current state.

    3. Else if not better than the current state, then return to step2.

  5. Exit.

Tic-tac-toe is a game played by two players on a 3x3 grid. In this game, the first player marks moves with a circle, the second with a cross. The player who has formed a horizontal, vertical, or diag-onal sequence of three marks wins. Your task is to write a program that determines the status of a tic-tac-toe game.

Algorithm:

  1. Create a 3x3 grid with all values 0.

  2. Take input from user for row and column.

  3. Check if the position is already filled or not.

  4. If not filled, then check if it is player 1 or player 2.

  5. If player 1, then fill the position with 1.

  6. If player 2, then fill the position with 2.

  7. Check if any player has won the game or not.

  8. If yes, then print the winner and exit.

  9. If no, then continue from step 2.

Game Rules:

  1. Traditionally the first player plays with "X". So you can decide who wants to go with "X" and who wants go with "O".

  2. Only one player can play at a time.

  3. If any of the players have filled a square then the other player and the same player cannot override that square.

  4. There are only two conditions that may match will be draw or may win.

  5. The player that succeeds in placing three respective marks (X or O) in a horizontal, vertical or diagonal row wins the game.

Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of intense research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families. CSPs often exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time. CSPs are applied in many areas including scheduling, planning, vehicle routing, configuration, and the design of communication networks.

Algorithm:

  1. Initialize all the variables with their domain values.

  2. Select a variable and assign it a value from its domain.

  3. Check if the assignment is consistent with the constraints.

  4. If yes, then select another variable and assign it a value from its domain.

  5. If no, then backtrack and select another value from the domain of the previous variable.

  6. Repeat steps 3 to 5 until all the variables are assigned with a value from their domain.

A perceptron is a single layer neural network. It is the simplest neural network model. It consists of a single layer of one or more perceptrons (neurons).

In the field of Machine Learning, the Perceptron is a Supervised Learning Algorithm for binary classifiers. The Perceptron Model implements the following function:

For a particular choice of the weight vector x and bias parameter b, the model predicts output y(cap) for the corresponding input vector x.

NAND logical function truth table for 2-bit binary variables, i.e, the input vector x: (x1,x2) and the corresponding output y –

x1
x2
y

0

0

1

0

1

1

1

0

1

1

1

0

We can observe that, NAND(x1,x2) = NOT (AND (x1,x2)) Now for the corresponding weight vector w: (w1,w2) of the input vector x: (x1,x2) to the AND node, the associated Perceptron Function can be defined as:

Later on, the output of AND node Y(cap)I is the input to the NOT node with weight wnot. Then the corresponding output Y(cap) is the final output of the NAND logic function and the associated Perceptron Function can be defined as:

Algorithm:

  1. Initialize the weights and bias with random values.

  2. Take inputs from the user.

  3. Calculate the weighted sum of inputs and weights.

  4. Pass the weighted sum through the activation function.

  5. Calculate the error.

  6. Update the weights and bias.

  7. Repeat steps 3 to 6 until the error is 0.

If placing queen doesn't lead to a solution then unmark this and go to step (a) to try other rows.

For the implementation, considered weight parameters are w1 = 1, w2 = 1, wnot = -1 and the bias parameters are band=-1.5, bnot = 0.5.

Breadth First Search
Depth First Search
Iterative Deepening Depth First Search
Greedy Best First Search
A* Search
n Queens Problem
Water Jug Problem
Tower of Hanoi
Alpha Beta search
Hill Climbing
Tic Tac Toe
Constraint Satisfaction Problem
Perceptron algorithm for NAND logic gate
Breadth First Search
Depth First Search
Iterative Deepening Depth First Search
Greedy Best First Search
A* Search
n Queens Problem
row, column
Water Jug Problem
Tower of Hanoi
Alpha Beta Pruning
Hill climbing algorithm
Tic-Tac-Toe
Constraint Satisfaction Problem
NAND using Perceptron
Breadth First Search
Depth First Search
Iterative Deepening Depth First Search
Greedy Best First Search
A* Search
n Queens Problem
Water Jug Problem
Tower of Hanoi
Alpha Beta pruning
Hill Climbing
Tic Tac Toe
Constraint Satisfaction Problem
Perceptron algorithm for NAND logic gate
Water Jug Problem
Water Jug Problem
WaterJug
tic-tac-toe
Perceptron
perceptron
perceptron