Category: Subjects

Genetic Algorithm in AI | Operators | Working

Artificial Intelligence

Genetic Algorithm-

 

In Artificial Intelligence,

  • Genetic Algorithm is one of the heuristic algorithms.
  • They are used to solve optimization problems.
  • They are inspired by Darwin’s Theory of Evolution.
  • They are an intelligent exploitation of a random search.
  • Although randomized, Genetic Algorithms are by no means random.

 

Algorithm-

 

Genetic Algorithm works in the following steps-

 

Step-01:

 

  • Randomly generate a set of possible solutions to a problem.
  • Represent each solution as a fixed length character string.

 

Step-02:

 

Using a fitness function, test each possible solution against the problem to evaluate them.

 

Step-03:

 

  • Keep the best solutions.
  • Use best solutions to generate new possible solutions.

 

Step-04:

 

Repeat the previous two steps until-

  • Either an acceptable solution is found
  • Or until the algorithm has completed its iterations through a given number of cycles / generations.

 

Basic Operators-

 

The basic operators of Genetic Algorithm are-

 

1. Selection (Reproduction)-

 

  • It is the first operator applied on the population.
  • It selects the chromosomes from the population of parents to cross over and produce offspring.
  • It is based on evolution theory of “Survival of the fittest” given by Darwin.

 

There are many techniques for reproduction or selection operator such as-

  • Tournament selection
  • Ranked position selection
  • Steady state selection etc.

 

2. Cross Over-

 

  • Population gets enriched with better individuals after reproduction phase.
  • Then crossover operator is applied to the mating pool to create better strings.
  • Crossover operator makes clones of good strings but does not create new ones.
  • By recombining good individuals, the process is likely to create even better individuals.

 

3. Mutation-

 

  • Mutation is a background operator.
  • Mutation of a bit includes flipping it by changing 0 to 1 and vice-versa.
  • After crossover, the mutation operator subjects the strings to mutation.
  • It facilitates a sudden change in a gene within a chromosome.
  • Thus, it allows the algorithm to see for the solution far away from the current ones.
  • It guarantees that the search algorithm is not trapped on a local optimum.
  • Its purpose is to prevent premature convergence and maintain diversity within the population.

 

Flow Chart-

 

The following flowchart represents how a genetic algorithm works-

 

 

Advantages-

 

Genetic Algorithms offer the following advantages-

 

Point-01:

 

  • Genetic Algorithms are better than conventional AI.
  • This is because they are more robust.

 

Point-02:

 

  • They do not break easily unlike older AI systems.
  • They do not break easily even in the presence of reasonable noise or if the inputs get change slightly.

 

Point-03:

 

While performing search in multi modal state-space or large state-space,

  • Genetic algorithms has significant benefits over other typical search optimization techniques.

 

To gain better understanding about Genetic Algorithm & its Working,

Watch this Video Lecture

 

Get more notes and other study material of Artificial Intelligence.

Watch video lectures by visiting our YouTube channel LearnVidFun.

DFA to Regular Expression | Arden’s Theorem

Theory of Automata & Computation

DFA to Regular Expression-

 

The two popular methods for converting a given DFA to its regular expression are-

 

 

  1. Arden’s Method
  2. State Elimination Method

 

In this article, we will discuss Arden’s Theorem.

 

Arden’s Theorem-

 

Arden’s Theorem is popularly used to convert a given DFA to its regular expression.

 

It states that-

Let P and Q be two regular expressions over ∑.

If P does not contain a null string ∈, then-

R = Q + RP has a unique solution i.e. R = QP*

 

Conditions-

 

To use Arden’s Theorem, following conditions must be satisfied-

  • The transition diagram must not have any ∈ transitions.
  • There must be only a single initial state.

 

Steps-

 

To convert a given DFA to its regular expression using Arden’s Theorem, following steps are followed-

 

Step-01:

 

  • Form a equation for each state considering the transitions which comes towards that state.
  • Add ‘∈’ in the equation of initial state.

 

Step-02:

 

Bring final state in the form R = Q + RP to get the required regular expression.

 

Important Notes-

 

Note-01:

 

Arden’s Theorem can be used to find a regular expression for both DFA and NFA.

 

Note-02:

 

If there exists multiple final states, then-

  • Write a regular expression for each final state separately.
  • Add all the regular expressions to get the final regular expression.

 

Also Read- State Elimination Method

 

PRACTICE PROBLEMS BASED ON CONVERTING DFA TO REGULAR EXPRESSION-

 

Problem-01:

 

Find regular expression for the following DFA using Arden’s Theorem-

 

 

Solution-

 

Step-01:

 

Form a equation for each state-

  • A = ∈ + B.1     ……(1)
  • B = A.0           ……(2)

 

Step-02:

 

Bring final state in the form R = Q + RP.

 

Using (1) in (2), we get-

B = (∈ + B.1).0

B = ∈.0 + B.1.0

B = 0 + B.(1.0)          ……(3)

 

Using Arden’s Theorem in (3), we get-

B = 0.(1.0)*

 

Thus, Regular Expression for the given DFA = 0(10)*

 

Problem-02:

 

Find regular expression for the following DFA using Arden’s Theorem-

 

 

Solution-

 

Step-01:

 

Form a equation for each state-

  • q1 = ∈                                        ……(1)
  • q2 = q1.a                                   ……(2)
  • q3 = q1.b + q2.a + q3.a            …….(3)

 

Step-02:

 

Bring final state in the form R = Q + RP.

 

Using (1) in (2), we get-

q2 = ∈.a

q2 = a              …….(4)

 

Using (1) and (4) in (3), we get-

 

q3 = q1.b + q2.a + q3.a

q3 = ∈.b + a.a + q3.a

q3 = (b + a.a) + q3.a        …….(5)

 

Using Arden’s Theorem in (5), we get-

q3 = (b + a.a)a*

 

Thus, Regular Expression for the given DFA = (b + aa)a*

 

Problem-03:

 

Find regular expression for the following DFA using Arden’s Theorem-

 

 

Solution-

 

Step-01:

 

Form a equation for each state-

  • q1 = ∈ + q1.b + q2.a                 ……(1)
  • q2 = q1.a + q2.b                       ……(2)

 

Step-02:

 

Bring final state in the form R = Q + RP.

 

Using Arden’s Theorem in (2), we get-

q2 = q1.a.b*             …….(3)

 

Using (3) in (1), we get-

q1 = ∈ + q1.b + q1.a.b*.a

q1 = ∈ + q1.(b + a.b*.a)          …….(4)

 

Using Arden’s Theorem in (4), we get-

q1 = ∈.(b + a.b*.a)*

q1 = (b + a.b*.a)*

 

Thus, Regular Expression for the given DFA = (b + a.b*.a)*

 

Problem-04:

 

Find regular expression for the following DFA using Arden’s Theorem-

 

 

Solution-

 

Step-01:

 

Form a equation for each state-

  • q1 = ∈ + q1.a + q3.a                 ……(1)
  • q2 = q1.b + q2.b + q3.b            ……(2)
  • q3 = q2.a                                  …….(3)

 

Step-02:

 

Bring final state in the form R = Q + RP.

 

Using (3) in (2), we get-

q2 = q1.b + q2.b + q2.a.b

q2 = q1.b + q2.(b + a.b)          …….(4)

 

Using Arden’s Theorem in (4), we get-

q2 = q1.b.(b + a.b)*    …….(5)

 

Using (5) in (3), we get-

q3 = q1.b.(b + a.b)*.a       …….(6)

 

Using (6) in (1), we get-

q1 = ∈ + q1.a + q1.b.(b + a.b)*.a.a

q1 = ∈ + q1.(a + b.(b + a.b)*.a.a)        …….(7)

 

Using Arden’s Theorem in (7), we get-

q1 = ∈.(a + b.(b + a.b)*.a.a)*

q1 = (a + b.(b + a.b)*.a.a)*

 

Thus, Regular Expression for the given DFA = (a + b(b + ab)*aa)*

 

Also Read- Minimization of DFA

 

To gain better understanding about Arden’s Theorem,

Watch this Video Lecture

 

Next Article- Non-Deterministic Finite Automata

 

Get more notes and other study material of Theory of Automata and Computation.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Machine Learning Algorithms | Machine Learning

Machine Learning

Machine Learning-

 

Learning is a continuous process of improvement over experience.

 

Machine learning is building machines that can adapt and learn from experience without being explicitly programmed.

 

In machine learning,

  • There is a learning algorithm.
  • Data called as training data set is fed to the learning algorithm.
  • Learning algorithm draws inferences from the training data set.
  • It generates a model which is a function that maps input to the output.

 

 

Machine Learning Applications-

 

Some important applications of machine learning are-

  • Spam Filtering
  • Fraudulent Transactions
  • Credit Scoring
  • Recommendations
  • Robot Navigation

 

Machine Learning Algorithms-

 

There are three types of machine learning algorithms-

 

 

  1. Supervised Learning
  2. Unsupervised Learning
  3. Reinforcement Learning

 

1. Supervised Learning-

 

In this type of machine learning algorithm,

  • The training data set is a labeled data set.
  • In other words, the training data set contains the input value (X) and target value (Y).
  • The learning algorithm generates a model.
  • Then, new data set consisting of only the input value is fed.
  • The model then generates the target value based on its learning.

 

 

Example-

 

Consider a sample database consisting of two columns where-

  • The first column specifies mails.
  • The second column specifies whether those emails are spam or not.

 

Mails (X) IsSpam (Y)
Mail-1 Yes
Mail-2 No
Mail-3 No
Mail-4 No

 

In this training data set, emails categorized as spam or not are done by a supervisor’s knowledge.

So, it is supervised learning algorithm.

 

Applications-

 

Some real-life applications are-

  • Spam Filtering
  • House Price Prediction
  • Credit Scoring (high risk or a low risk customer while lending loans by the banks)
  • Face Recognition etc

 

Types of Supervised Learning Algorithm-

 

There are two types of supervised learning algorithm-

 

 

  1. Regression
  2. Classification

 

Regression-

 

Here,

  • The target variable (Y) has continuous value.
  • Example- house price prediction

 

Classification-

 

Here,

  • The target variable (Y) has discrete values such as Yes or No, 0 or 1 and many more.
  • Example- Credit Scoring, Spam Filtering

 

2. Unsupervised Learning-

 

In this type of machine learning algorithm,

  • The training data set is an unlabeled data set.
  • In other words, the training data set contains only the input value (X) and not the target value (Y).
  • Based on the similarity between data, it tries to draw inference from the data such as finding patterns or clusters.

 

 

Applications-

 

Some real-life applications are-

  • Document Clustering
  • Finding fraudulent transactions

 

3. Reinforcement Learning-

 

In this type of machine learning algorithm,

  • The agent acts in an environment in order to maximize the rewards and minimize the penalty.
  • Unlike supervised learning, no data is provided to the agent.
  • The agent itself takes action or sequence of actions whether right or wrong to perform a task and learn from the experience.

 

Applications-

 

Some real-life applications are-

  • Game Playing
  • Robot Navigation

 

To gain better understanding about Machine Learning & its Algorithms,

Watch this Video Lecture

 

Next Article- Machine Learning Workflow

 

Get more notes and other study material of Machine Learning.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Heap Operations | Max Heap Operations | Examples

Data Structures

Heap Data Structure-

 

Before you go through this article, make sure that you have gone through the previous article on Heap Data Structure.

 

We have discussed-

  • Heap is a specialized data structure with special properties.
  • A binary heap is a binary tree that has ordering and structural properties.
  • A heap may be a max heap or a min heap.

 

In this article, we will discuss about heap operations.

 

Heap Operations-

 

The most basic and commonly performed operations on a heap are-

 

 

  1. Search Operation
  2. Insertion Operation
  3. Deletion Operation

 

Here, we will discuss how these operations are performed on a max heap.

 

Max Heap-

 

  • In max heap, every node contains greater or equal value element than its child nodes.
  • Thus, root node contains the largest value element.

 

Example-

 

The following heap is an example of a max heap-

 

 

Max Heap Operations-

 

We will discuss the construction of a max heap and how following operations are performed on a max heap-

  • Finding Maximum Operation
  • Insertion Operation
  • Deletion Operation

 

Max Heap Construction-

 

Given an array of elements, the steps involved in constructing a max heap are-

 

Step-01:

 

Convert the given array of elements into an almost complete binary tree.

 

Step-02:

 

Ensure that the tree is a max heap.

  • Check that every non-leaf node contains a greater or equal value element than its child nodes.
  • If there exists any node that does not satisfies the ordering property of max heap, swap the elements.
  • Start checking from a non-leaf node with the highest index (bottom to top and right to left).

 

Finding Maximum Operation-

 

  • In max heap, the root node always contains the maximum value element.
  • So, we directly display the root node value as maximum value in max heap.

 

Insertion Operation-

 

Insertion Operation is performed to insert an element in the heap tree.

 

The steps involved in inserting an element are-

 

Step-01:

 

Insert the new element as a next leaf node from left to right.

 

Step-02:

 

Ensure that the tree remains a max heap.

  • Check that every non-leaf node contains a greater or equal value element than its child nodes.
  • If there exists any node that does not satisfies the ordering property of max heap, swap the elements.
  • Start checking from a non-leaf node with the highest index (bottom to top and right to left).

 

Deletion Operation-

 

Deletion Operation is performed to delete a particular element from the heap tree.

 

When it comes to deleting a node from the heap tree, following two cases are possible-

 

Case-01: Deletion Of Last Node-

 

  • This case is pretty simple.
  • Just remove / disconnect the last leaf node from the heap tree.

 

Case-02: Deletion Of Some Other Node-

 

  • This case is little bit difficult.
  • Deleting a node other than the last node disturbs the heap properties.

 

The steps involved in deleting such a node are-

 

Step-01:

 

  • Delete the desired element from the heap tree.
  • Pluck the last node and put in place of the deleted node.

 

Step-02:

 

Ensure that the tree remains a max heap.

  • Check that every non-leaf node contains a greater or equal value element than its child nodes.
  • If there exists any node that does not satisfies the ordering property of max heap, swap the elements.
  • Start checking from a non-leaf node with the highest index (bottom to top and right to left).

 

PRACTICE PROBLEMS BASED ON MAX HEAP OPERATIONS-

 

Problem-01:

 

Construct a max heap for the given array of elements-

1, 5, 6, 8, 12, 14, 16

 

Solution-

 

Step-01:

 

We convert the given array of elements into an almost complete binary tree-

 

 

Step-02:

 

  • We ensure that the tree is a max heap.
  • Node 6 contains greater element in its right child node.
  • So, we swap node 6 and node 16.

 

The resulting tree is-

 

 

Step-03:

 

  • Node 5 contains greater element in its right child node.
  • So, we swap node 5 and node 12.

 

The resulting tree is-

 

 

Step-04:

 

  • Node 1 contains greater element in its right child node.
  • So, we swap node 1 and node 16.

 

The resulting tree is-

 

 

Step-05:

 

  • Node 1 contains greater element in its left child node.
  • So, we swap node 1 and node 14.

 

The resulting tree is-

 

 

This is the required max heap for the given array of elements.

 

Problem-02:

 

Consider the following max heap-

50, 30, 20, 15, 10, 8, 16

Insert a new node with value 60.

 

Solution-

 

Step-01:

 

We convert the given array of elements into a heap tree-

 

 

Step-02:

 

We insert the new element 60 as a next leaf node from left to right.

The resulting tree is-

 

 

Step-03:

 

  • We ensure that the tree is a max heap.
  • Node 15 contains greater element in its left child node.
  • So, we swap node 15 and node 60.

 

The resulting tree is-

 

 

Step-04:

 

  • Node 30 contains greater element in its left child node.
  • So, we swap node 30 and node 60.

 

The resulting tree is-

 

 

Step-05:

 

  • Node 50 contains greater element in its left child node.
  • So, we swap node 50 and node 60.

 

The resulting tree is-

 

 

This is the required max heap after inserting the node with value 60.

 

Problem-03:

 

Consider the following max heap-

50, 30, 20, 15, 10, 8, 16

Delete a node with value 50.

 

Solution-

 

Step-01:

 

We convert the given array of elements into a heap tree-

 

 

Step-02:

 

  • We delete the element 50 which is present at root node.
  • We pluck the last node 16 and put in place of the deleted node.

 

The resulting tree is-

 

 

Step-03:

 

  • We ensure that the tree is a max heap.
  • Node 16 contains greater element in its left child node.
  • So, we swap node 16 and node 30.

 

The resulting tree is-

 

 

This is the required max heap after deleting the node with value 50.

 

To gain better understanding about Heap Data Structure,

Watch this Video Lecture

 

Next Article- Introduction to Hashing

 

Get more notes and other study material of Data Structures.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Heap Data Structure | Binary Heap | Examples

Data Structures

Heap Data Structure-

 

In data structures,

  • Heap is a specialized data structure.
  • It has special characteristics.
  • A heap may be implemented using a n-ary tree.

 

In this article, we will discuss implementation of heap using a binary tree.

 

Binary Heap-

 

A binary heap is a Binary Tree with the following two properties-

 

 

  • Ordering Property
  • Structural Property

 

1. Ordering Property-

 

By this property,

  • Elements in the heap tree are arranged in specific order.
  • This gives rise to two types of heaps- min heap and max heap.

 

2. Structural Property-

 

By this property,

  • Binary heap is an almost complete binary tree.
  • It has all its levels completely filled except possibly the last level.
  • The last level is strictly filled from left to right.

 

Types of Binary Heap-

 

Depending on the arrangement of elements, a binary heap may be of following two types-

 

 

  1. Max Heap
  2. Min Heap

 

1. Max Heap-

 

  • Max Heap conforms to the above properties of heap.
  • In max heap, every node contains greater or equal value element than its child nodes.
  • Thus, root node contains the largest value element.

 

Example-

 

Consider the following example of max heap-

 

 

This is max heap because-

  • Every node contains greater or equal value element than its child nodes.
  • It is an almost complete binary tree with its last level strictly filled from left to right.

 

2. Min Heap-

 

  • Min Heap conforms to the above properties of heap.
  • In min heap, every node contains lesser value element than its child nodes.
  • Thus, root node contains the smallest value element.

 

Example-

 

Consider the following example of min heap-

 

 

This is min heap because-

  • Every node contains lesser value element than its child nodes.
  • It is an almost complete binary tree with its last level strictly filled from left to right.

 

Array Representation of Binary Heap-

 

A binary heap is typically represented as an array.

 

 

For a node present at index ‘i’ of the array Arr-

 

If indexing starts with 0,

  • Its parent node will be present at array location = Arr [ i/2 ]
  • Its left child node will be present at array location = Arr [ 2i+1 ]
  • Its right child node will be present at array location = Arr [ 2i+2 ]

 

If indexing starts with 1,

  • Its parent node will be present at array location = Arr [ ⌊i/2⌋ ]
  • Its left child node will be present at array location = Arr [ 2i ]
  • Its right child node will be present at array location = Arr [ 2i+1 ]

 

Important Notes-

 

Note-01:

 

  • Level order traversal technique may be used to achieve the array representation of a heap tree.
  • Array representation of a heap never contains any empty indices in between.
  • However, array representation of a binary tree may contain some empty indices in between.

 

Note-02:

 

Given an array representation of a binary heap,

  • If all the elements are in descending order, then heap is definitely a max heap.
  • If all the elements are not in descending order, then it may or may not be a max heap.
  • If all the elements are in ascending order, then heap is definitely a min heap.
  • If all the elements are not in ascending order, then it may or may not be a min heap.

 

Note-03:

 

  • In max heap, every node contains greater or equal value element than all its descendants.
  • In min heap, every node contains smaller value element that all its descendants.

 

PRACTICE PROBLEMS BASED ON HEAP DATA STRUCTURE-

 

Problems-

 

Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap? (GATE CS 2009)

  1. 25, 14, 16, 13, 10, 8, 12
  2. 25, 12, 16, 13, 10, 8, 14
  3. 25, 14, 12, 13, 10, 8, 16
  4. 25, 14, 13, 16, 10, 8, 12

 

Solutions-

 

Part-01: 25, 14, 16, 13, 10, 8, 12-

 

The given array representation may be converted into the following structure-

 

 

Clearly,

  • It is a complete binary tree.
  • Every node contains a greater value element than its child nodes.

 

Thus, the given array represents a max heap.

 

Part-02: 25, 12, 16, 13, 10, 8, 14-

 

The given array representation may be converted into the following structure-

 

 

Clearly,

  • It is a complete binary tree.
  • Every node does not contain a greater value element than its child nodes. (Node 12)
  • So, it is not a max heap.
  • Every node does not contain a smaller value element than its child nodes.
  • So, it is not a min heap.

 

Thus, the given array does not represents a heap.

 

Part-03: 25, 14, 12, 13, 10, 8, 16-

 

The given array representation may be converted into the following structure-

 

 

Clearly,

  • It is a complete binary tree.
  • Every node does not contain a greater value element than its child nodes. (Node 12)
  • So, it is not a max heap.
  • Every node does not contain a smaller value element than its child nodes.
  • So, it is not a min heap.

 

Thus, the given array does not represents a heap.

 

Part-04: 25, 14, 13, 16, 10, 8, 12-

 

The given array representation may be converted into the following structure-

 

 

Clearly,

  • It is a complete binary tree.
  • Every node does not contain a greater value element than its child nodes. (Node 14)
  • So, it is not a max heap.
  • Every node does not contain a smaller value element than its child nodes.
  • So, it is not a min heap.

 

Thus, the given array does not represents a heap.

 

To gain better understanding about Heap Data Structure,

Watch this Video Lecture

 

Next Article- Heap Operations

 

Get more notes and other study material of Data Structures.

Watch video lectures by visiting our YouTube channel LearnVidFun.