FOUNDAMENTALS IN AI and ML
School of Computer Science and Engineering
LECTURE-5
What Is Data Structure ?
Data Structure is a way of storing and organising the
data in computer’s memory in such a way that we can
perform operations on these data in an effective way.
What Is Data Structure ?
Given a basket of fruits and vegetables , how would
you find/search apples and oranges in it ?
As you can observe , since the basket is unorganized
, it seems to be very difficult for us to find our items.
What Is Data Structure ?
Now have a look at the arrangement of fruits and
vegetables shown below and think again about the
task?
As you can observe , since the food items are now
organized , it seems to be very easy for us to find our
items.
What Is Data Structure ?
So , what we have done in the second way ?
We have simply taken fruits and vegetables from the
first messy basket and organized them in a proper
way .
What Is Data Structure ?
The same concept applies to data structures .
Here also we are given some data and we have to do
some processing on it.
So before processing the data we organize this data
in such a way that we can easily access/
process/operate on this data.
What Is An Algorithm?
An Algorithm is a set of rules to follow to solve a
particular problem.
Example: Suppose we want to prepare SALAD for
lunch.
What Is An Algorithm?
What Is Data Structure ?
Organize the data in such a way that we can easily
access/ process/operate on this data.
Linear V/s Non Linear
A data structure is said to be Linear if its elements are
connected in a sequential manner by means of
logically or in sequence memory locations.
VIT, Bhopal
Linear V/s Non Linear
Nonlinear data structures are those data structure in
which data items are not arranged in a sequence.
VIT, Bhopal
VIT, Bhopal
TREE GRAPH
VIT, Bhopal
Graph
Problem Solving
Approach to Typical AI problems
Search Algorithms in Artificial Intelligence
Search algorithms are one of the most important areas of
Artificial Intelligence. This topic will explain all about the
search algorithms in AI.
Properties of Search Algorithms:
Following are the four essential properties of search algorithms to
compare the efficiency of these algorithms:
Completeness:
Optimality:
Time Complexity:
Space Complexity:
Search Algorithms in Artificial
Intelligence
Searching
Algorithm
Un-informed/ Blined Informed
Search Search
(Breadth First Depth First Hill
A* AO*
Search(BFS) Search(DFS) climbing
Best first
Search
Graph Traversal:
BFS
DFS
GRAPHS
BFS(ALGORITHM)
1. Initialize all nodes to the ready state(STATUS=1).
2. Put the starting node A in QUEUE and change its
status to the waiting state(STATUS=2).
3. Repeat Steps 4 and 5 until QUEUE is empty:
4. Remove the front node N of QUEUE. Process N
and change the status of N to the processed state
(STATUS=3).
5. Add to the rear of QUEUE all the neighbors of N
that are in the steady state (STATUS=1), and change
their status to the waiting state (STATUS=2).
[End of Step 3 loop] 19
6. Exit
BFS(ALGORITHM)
1. Initialize all nodes to the ready state(STATUS=1).
2. Put the starting node A in QUEUE and change its status
to the waiting state(STATUS=2).
3. If the first(front) element of the queue is goal node ,
return success and stop.
4. Repeat Steps 5 and 6 until QUEUE is empty:
5. Remove the front node N of QUEUE. Process N and
change the status of N to the processed state
(STATUS=3).
6. Add to the rear of QUEUE all the neighbors of N that
are in the steady state (STATUS=1), and change their
status to the waiting state (STATUS=2). Goto Step to 2.
7. [End of Step 3 loop] 20
8. Exit
BFS(ALGORITHM)
1. Not Processed
2. Wait in queue
3. Processed
21
DFS(ALGORITHM)
1. Initialize all nodes to the ready state(STATUS=1).
2. Push the starting node A onto STACK and change its
status to the waiting state(STATUS=2).
3. Repeat Steps 4 and 5 until STACK is empty:
4. Pop the top node N of STACK. Process N and change
the status of N to the processed state (STATUS=3).
5. Push onto STACK all the neighbors of N that are
still in the ready state (STATUS=1), and change
their status to the waiting state (STATUS=2).
6. [End of Step 3 loop]
7. Exit
DFS(ALGORITHM)
1. Initialize all nodes to the ready state(STATUS=1).
2. Push the starting node A onto STACK and change its
status to the waiting state(STATUS=2).
3. If the first(Top) element of the STACK is goal node,
return success and stop.
4. Repeat Steps 5 and 6 until STACK is empty:
5. Pop the top node N of STACK. Process N and change
the status of N to the processed state (STATUS=3).
6. Push onto STACK all the neighbors of N that are
still in the ready state (STATUS=1), and change
their status to the waiting state (STATUS=2).
7. [End of Step 3 loop]
8. Exit
DFS(ALGORITHM)
1. Not Processed
2. Wait in Stack
3. Processed
