Tag: Algorithms Notes PDF

Binary Search Algorithm | Example | Time Complexity

Searching-

 

  • Searching is a process of finding a particular element among several given elements.
  • The search is successful if the required element is found.
  • Otherwise, the search is unsuccessful.

 

Searching Algorithms-

 

Searching Algorithms are a family of algorithms used for the purpose of searching.

The searching of an element in the given array may be carried out in the following two ways-

 

 

  1. Linear Search
  2. Binary Search

 

In this article, we will discuss about Binary Search Algorithm.

 

Binary Search-

 

  • Binary Search is one of the fastest searching algorithms.
  • It is used for finding the location of an element in a linear array.
  • It works on the principle of divide and conquer technique.

 

Binary Search Algorithm can be applied only on Sorted arrays.

 

So, the elements must be arranged in-

  • Either ascending order if the elements are numbers.
  • Or dictionary order if the elements are strings.

 

To apply binary search on an unsorted array,

  • First, sort the array using some sorting technique.
  • Then, use binary search algorithm.

 

Also Read- Linear Search

 

Binary Search Algorithm-

 

Consider-

  • There is a linear array ‘a’ of size ‘n’.
  • Binary search algorithm is being used to search an element ‘item’ in this linear array.
  • If search ends in success, it sets loc to the index of the element otherwise it sets loc to -1.
  • Variables beg and end keeps track of the index of the first and last element of the array or sub array in which the element is being searched at that instant.
  • Variable mid keeps track of the index of the middle element of that array or sub array in which the element is being searched at that instant.

 

Then, Binary Search Algorithm is as follows-

 

Begin

Set beg = 0

Set end = n-1

Set mid = (beg + end) / 2

while ( (beg <= end) and (a[mid] ≠ item) ) do

    if (item < a[mid]) then

        Set end = mid - 1

    else

        Set beg = mid + 1

    endif

Set mid = (beg + end) / 2

endwhile

if (beg > end) then

    Set loc = -1

else

    Set loc = mid

endif

End

 

Explanation

 

Binary Search Algorithm searches an element by comparing it with the middle most element of the array.

Then, following three cases are possible-

 

Case-01

 

If the element being searched is found to be the middle most element, its index is returned.

 

Case-02

 

If the element being searched is found to be greater than the middle most element,

then its search is further continued in the right sub array of the middle most element.

 

Case-03

 

If the element being searched is found to be smaller than the middle most element,

then its search is further continued in the left sub array of the middle most element.

 

This iteration keeps on repeating on the sub arrays until the desired element is found

or size of the sub array reduces to zero.

 

Time Complexity Analysis-

 

Binary Search time complexity analysis is done below-

  • In each iteration or in each recursive call, the search gets reduced to half of the array.
  • So for n elements in the array, there are log2n iterations or recursive calls.

 

Thus, we have-

 

Time Complexity of Binary Search Algorithm is O(log2n).

Here, n is the number of elements in the sorted linear array.

 

This time complexity of binary search remains unchanged irrespective of the element position even if it is not present in the array.

 

Binary Search Example-

 

Consider-

  • We are given the following sorted linear array.
  • Element 15 has to be searched in it using Binary Search Algorithm.

 

 

Binary Search Algorithm works in the following steps-

 

Step-01:

 

  • To begin with, we take beg=0 and end=6.
  • We compute location of the middle element as-

mid

= (beg + end) / 2

= (0 + 6) / 2

= 3

  • Here, a[mid] = a[3] = 20 ≠ 15 and beg < end.
  • So, we start next iteration.

 

Step-02:

 

  • Since a[mid] = 20 > 15, so we take end = mid – 1 = 3 – 1 = 2 whereas beg remains unchanged.
  • We compute location of the middle element as-

mid

= (beg + end) / 2

= (0 + 2) / 2

= 1

  • Here, a[mid] = a[1] = 10 ≠ 15 and beg < end.
  • So, we start next iteration.

 

Step-03:

 

  • Since a[mid] = 10 < 15, so we take beg = mid + 1 = 1 + 1 = 2 whereas end remains unchanged.
  • We compute location of the middle element as-

mid

= (beg + end) / 2

= (2 + 2) / 2

= 2

  • Here, a[mid] = a[2] = 15 which matches to the element being searched.
  • So, our search terminates in success and index 2 is returned.

 

Binary Search Algorithm Advantages-

 

The advantages of binary search algorithm are-

  • It eliminates half of the list from further searching by using the result of each comparison.
  • It indicates whether the element being searched is before or after the current position in the list.
  • This information is used to narrow the search.
  • For large lists of data, it works significantly better than linear search.

 

Binary Search Algorithm Disadvantages-

 

The disadvantages of binary search algorithm are-

  • It employs recursive approach which requires more stack space.
  • Programming binary search algorithm is error prone and difficult.
  • The interaction of binary search with memory hierarchy i.e. caching is poor.

(because of its random access nature)

 

Important Note-

 

For in-memory searching, if the interval to be searched is small,

  • Linear search may exhibit better performance than binary search.
  • This is because it exhibits better locality of reference.

 

To gain better understanding about Binary Search Algorithm,

Watch this Video Lecture

 

Next Article- Selection Sort

 

Get more notes and other study material of Design and Analysis of Algorithms.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Linear Search Algorithm | Example | Time Complexity

Searching-

 

  • Searching is a process of finding a particular element among several given elements.
  • The search is successful if the required element is found.
  • Otherwise, the search is unsuccessful.

 

Searching Algorithms-

 

Searching Algorithms are a family of algorithms used for the purpose of searching.

The searching of an element in the given array may be carried out in the following two ways-

 

 

  1. Linear Search
  2. Binary Search

 

In this article, we will discuss about Linear Search Algorithm.

 

Linear Search-

 

  • Linear Search is the simplest searching algorithm.
  • It traverses the array sequentially to locate the required element.
  • It searches for an element by comparing it with each element of the array one by one.
  • So, it is also called as Sequential Search.

 

Linear Search Algorithm is applied when-

  • No information is given about the array.
  • The given array is unsorted or the elements are unordered.
  • The list of data items is smaller.

 

Linear Search Algorithm-

 

Consider-

  • There is a linear array ‘a’ of size ‘n’.
  • Linear search algorithm is being used to search an element ‘item’ in this linear array.
  • If search ends in success, it sets loc to the index of the element otherwise it sets loc to -1.

 

Then, Linear Search Algorithm is as follows-

 

Linear_Search (a , n , item , loc)

 

Begin

for i = 0 to (n - 1) by 1 do

    if (a[i] = item) then

        set loc = i

        Exit

    endif

endfor

set loc = -1

End

 

Time Complexity Analysis-

 

Linear Search time complexity analysis is done below-

 

Best case-

 

In the best possible case,

  • The element being searched may be found at the first position.
  • In this case, the search terminates in success with just one comparison.
  • Thus in best case, linear search algorithm takes O(1) operations.

 

Worst Case-

 

In the worst possible case,

  • The element being searched may be present at the last position or not present in the array at all.
  • In the former case, the search terminates in success with n comparisons.
  • In the later case, the search terminates in failure with n comparisons.
  • Thus in worst case, linear search algorithm takes O(n) operations.

 

Thus, we have-

 

Time Complexity of Linear Search Algorithm is O(n).

Here, n is the number of elements in the linear array.

 

Linear Search Efficiency-

 

  • Linear Search is less efficient when compared with other algorithms like Binary Search & Hash tables.
  • The other algorithms allow significantly faster searching.

 

Linear Search Example-

 

Consider-

  • We are given the following linear array.
  • Element 15 has to be searched in it using Linear Search Algorithm.

 

 

Now,

  • Linear Search algorithm compares element 15 with all the elements of the array one by one.
  • It continues searching until either the element 15 is found or all the elements are searched.

 

Linear Search Algorithm works in the following steps-

 

Step-01:

 

  • It compares element 15 with the 1st element 92.
  • Since 15 ≠ 92, so required element is not found.
  • So, it moves to the next element.

 

Step-02:

 

  • It compares element 15 with the 2nd element 87.
  • Since 15 ≠ 87, so required element is not found.
  • So, it moves to the next element.

 

Step-03:

 

  • It compares element 15 with the 3rd element 53.
  • Since 15 ≠ 53, so required element is not found.
  • So, it moves to the next element.

 

Step-04:

 

  • It compares element 15 with the 4th element 10.
  • Since 15 ≠ 10, so required element is not found.
  • So, it moves to the next element.

 

Step-05:

 

  • It compares element 15 with the 5th element 15.
  • Since 15 = 15, so required element is found.
  • Now, it stops the comparison and returns index 4 at which element 15 is present.

 

To gain better understanding about Linear Search Algorithm,

Watch this Video Lecture

 

Next Article- Binary Search

 

Get more notes and other study material of Design and Analysis of Algorithms.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Shortest Path Problem | Shortest Path Algorithms | Examples

Shortest Path Problem-

 

In data structures,

  • Shortest path problem is a problem of finding the shortest path(s) between vertices of a given graph.
  • Shortest path between two vertices is a path that has the least cost as compared to all other existing paths.

 

Shortest Path Algorithms-

 

Shortest path algorithms are a family of algorithms used for solving the shortest path problem.

 

Applications-

 

Shortest path algorithms have a wide range of applications such as in-

  • Google Maps
  • Road Networks
  • Logistics Research

 

Types of Shortest Path Problem-

 

Various types of shortest path problem are-

 

 

  1. Single-pair shortest path problem
  2. Single-source shortest path problem
  3. Single-destination shortest path problem
  4. All pairs shortest path problem

 

Single-Pair Shortest Path Problem-

 

  • It is a shortest path problem where the shortest path between a given pair of vertices is computed.
  • A* Search Algorithm is a famous algorithm used for solving single-pair shortest path problem.

 

Single-Source Shortest Path Problem-

 

  • It is a shortest path problem where the shortest path from a given source vertex to all other remaining vertices is computed.
  • Dijkstra’s Algorithm and Bellman Ford Algorithm are the famous algorithms used for solving single-source shortest path problem.

 

Single-Destination Shortest Path Problem-

 

  • It is a shortest path problem where the shortest path from all the vertices to a single destination vertex is computed.
  • By reversing the direction of each edge in the graph, this problem reduces to single-source shortest path problem.
  • Dijkstra’s Algorithm is a famous algorithm adapted for solving single-destination shortest path problem.

 

All Pairs Shortest Path Problem-

 

  • It is a shortest path problem where the shortest path between every pair of vertices is computed.
  • Floyd-Warshall Algorithm and Johnson’s Algorithm are the famous algorithms used for solving All pairs shortest path problem.

 

Also Read- Floyd-Warshall Algorithm

 

Next Article- Dijkstra’s Algorithm

 

Get more notes and other study material of Design and Analysis of Algorithms.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Huffman Coding | Huffman Coding Example | Time Complexity

Huffman Coding-

 

  • Huffman Coding is a famous Greedy Algorithm.
  • It is used for the lossless compression of data.
  • It uses variable length encoding.
  • It assigns variable length code to all the characters.
  • The code length of a character depends on how frequently it occurs in the given text.
  • The character which occurs most frequently gets the smallest code.
  • The character which occurs least frequently gets the largest code.
  • It is also known as Huffman Encoding.

 

Prefix Rule-

 

  • Huffman Coding implements a rule known as a prefix rule.
  • This is to prevent the ambiguities while decoding.
  • It ensures that the code assigned to any character is not a prefix of the code assigned to any other character.

 

Major Steps in Huffman Coding-

 

There are two major steps in Huffman Coding-

  1. Building a Huffman Tree from the input characters.
  2. Assigning code to the characters by traversing the Huffman Tree.

 

Huffman Tree-

 

The steps involved in the construction of Huffman Tree are as follows-

 

Step-01:

 

  • Create a leaf node for each character of the text.
  • Leaf node of a character contains the occurring frequency of that character.

 

Step-02:

 

  • Arrange all the nodes in increasing order of their frequency value.

 

Step-03:

 

Considering the first two nodes having minimum frequency,

  • Create a new internal node.
  • The frequency of this new node is the sum of frequency of those two nodes.
  • Make the first node as a left child and the other node as a right child of the newly created node.

 

Step-04:

 

  • Keep repeating Step-02 and Step-03 until all the nodes form a single tree.
  • The tree finally obtained is the desired Huffman Tree.

 

Time Complexity-

 

The time complexity analysis of Huffman Coding is as follows-

  • extractMin( ) is called 2 x (n-1) times if there are n nodes.
  • As extractMin( ) calls minHeapify( ), it takes O(logn) time.

 

Thus, Overall time complexity of Huffman Coding becomes O(nlogn).

Here, n is the number of unique characters in the given text.

 

Important Formulas-

 

The following 2 formulas are important to solve the problems based on Huffman Coding-

 

Formula-01:

 

 

Formula-02:

 

Total number of bits in Huffman encoded message

= Total number of characters in the message x Average code length per character

= ∑ ( frequencyi x Code length)

 

PRACTICE PROBLEM BASED ON HUFFMAN CODING-

 

Problem-

 

A file contains the following characters with the frequencies as shown. If Huffman Coding is used for data compression, determine-

  1. Huffman Code for each character
  2. Average code length
  3. Length of Huffman encoded message (in bits)

 

Characters Frequencies
a 10
e 15
i 12
o 3
u 4
s 13
t 1

 

Solution-

 

First let us construct the Huffman Tree.

Huffman Tree is constructed in the following steps-

 

Step-01:

 

 

Step-02:

 

 

Step-03:

 

 

Step-04:

 

 

Step-05:

 

 

Step-06:

 

 

Step-07:

 

 

Now,

  • We assign weight to all the edges of the constructed Huffman Tree.
  • Let us assign weight ‘0’ to the left edges and weight ‘1’ to the right edges.

 

Rule

  • If you assign weight ‘0’ to the left edges, then assign weight ‘1’ to the right edges.
  • If you assign weight ‘1’ to the left edges, then assign weight ‘0’ to the right edges.
  • Any of the above two conventions may be followed.
  • But follow the same convention at the time of decoding that is adopted at the time of encoding.

 

After assigning weight to all the edges, the modified Huffman Tree is-

 

 

Now, let us answer each part of the given problem one by one-

 

1. Huffman Code For Characters-

 

To write Huffman Code for any character, traverse the Huffman Tree from root node to the leaf node of that character.

Following this rule, the Huffman Code for each character is-

  • a = 111
  • e = 10
  • i = 00
  • o = 11001
  • u = 1101
  • s = 01
  • t = 11000

 

From here, we can observe-

  • Characters occurring less frequently in the text are assigned the larger code.
  • Characters occurring more frequently in the text are assigned the smaller code.

 

2. Average Code Length-

 

Using formula-01, we have-

Average code length

= ∑ ( frequencyi x code lengthi ) / ∑ ( frequencyi )

= { (10 x 3) + (15 x 2) + (12 x 2) + (3 x 5) + (4 x 4) + (13 x 2) + (1 x 5) } / (10 + 15 + 12 + 3 + 4 + 13 + 1)

= 2.52

 

3. Length of Huffman Encoded Message-

 

Using formula-02, we have-

Total number of bits in Huffman encoded message

= Total number of characters in the message x Average code length per character

= 58 x 2.52

= 146.16

≅ 147 bits

 

To gain better understanding about Huffman Coding,

Watch this Video Lecture

 

To practice previous years GATE problems on Huffman Coding,

Watch this Video Lecture

 

Next Article- 0/1 Knapsack Problem

 

Get more notes and other study material of Design and Analysis of Algorithms.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Breadth First Search Algorithm | BFS Example

Breadth First Search-

 

  • Breadth First Search or BFS is a graph traversal algorithm.
  • It is used for traversing or searching a graph in a systematic fashion.
  • BFS uses a strategy that searches in the graph in breadth first manner whenever possible.
  • Queue data structure is used in the implementation of breadth first search.

 

BFS Example-

 

Consider the following graph-

 

 

The breadth first search traversal order of the above graph is-

A, B, C, D, E, F

 

Breadth First Search Algorithm-

 

BFS (V,E,s)

 

for each vertex v in V – {s}

do

color[v] ← WHITE

d[v] ← ∞

π[v] ← NIL

color[s] = GREY

d[s] ← 0

π[s] ← NIL

Q ← { }

ENQUEUE (Q,s)

While Q is non-empty

do v ← DEQUEUE (Q)

for each u adjacent to v

do if color[u] ← WHITE

then color[u] ← GREY

d[u] ← d[v] + 1

π[u] ← v

ENQUEUE (Q,u)

color[v] ← BLACK

 

Explanation-

 

The above breadth first search algorithm is explained in the following steps-

 

Step-01

 

Create and maintain 3 variables for each vertex of the graph.

For any vertex ‘v’ of the graph, these 3 variables are-

 

1. color[v]-

 

  • This variable represents the color of the vertex v at the given point of time.
  • The possible values of this variable are- WHITE, GREY and BLACK.
  • WHITE color of the vertex signifies that it has not been discovered yet.
  • GREY color of the vertex signifies that it has been discovered and it is being processed.
  • BLACK color of the vertex signifies that it has been completely processed.

 

2. Π[v]-

 

This variable represents the predecessor of vertex ‘v’.

 

3. d[v]-

 

This variable represents the distance of vertex v from the source vertex.

 

Step-02

 

For each vertex v of the graph except source vertex, initialize the variables as-

  • color[v] = WHITE
  • π[v] = NIL
  • d[v] = ∞

 

For source vertex S, initialize the variables as-

  • color[S] = GREY
  • π[S] = NIL
  • d[S] = 0

 

Step-03

 

Now, enqueue source vertex S in queue Q and repeat the following procedure until the queue Q becomes empty-

1. Dequeue vertex v from queue Q.

2. For all the adjacent white vertices u of vertex v,

do-

color[u] = GREY

d[u] = d[v] + 1

π[u] = v

Enqueue (Q,u)

3. Color vertex v to black.

 

BFS Time Complexity-

 

The total running time for Breadth First Search is O (V+E).

 

Also Read- Depth First Search

 

PRACTICE PROBLEM BASED ON BREADTH FIRST SEARCH-

 

Problem-

 

Traverse the following graph using Breadth First Search Technique-

 

 

Consider vertex S as the starting vertex.

 

Solution-

 

Step-01:

 

For all the vertices v except source vertex S of the graph, we initialize the variables as-

  • color[v] = WHITE
  • π[v] = NIL
  • d[v] = ∞

 

For source vertex S, we initialize the variables as-

  • color[S] = GREY
  • π[S] = NIL
  • d[S] = 0

 

We enqueue the source vertex S in the queue Q.

 

 

Step-02:

 

  • Dequeue vertex S from the queue Q
  • For all adjacent white vertices ‘v’ (vertices R and W) of vertex S, we do-

 

  1. color[v] = GREY
  2. d[v] = d[S] + 1 = 0 + 1 = 1
  3. π[v] = S
  4. Enqueue all adjacent white vertices of S in queue Q

 

  • color[S] = BLACK

 

 

Step-03:

 

  • Dequeue vertex W from the queue Q
  • For all adjacent white vertices ‘v’ (vertices T and X) of vertex W, we do-

 

  1. color[v] = GREY
  2. d[v] = d[W] + 1 = 1 + 1 = 2
  3. π[v] = W
  4. Enqueue all adjacent white vertices of W in queue Q

 

  • color[W] = BLACK

 

 

Step-04:

 

  • Dequeue vertex R from the queue Q
  • For all adjacent white vertices ‘v’ (vertex V) of vertex R, we do-

 

  1. color[v] = GREY
  2. d[v] = d[R] + 1 = 1 + 1 = 2
  3. π[v] = R
  4. Enqueue all adjacent white vertices of R in queue Q

 

  • color[R] = BLACK

 

 

Step-05:

 

  • Dequeue vertex T from the queue Q
  • For all adjacent white vertices ‘v’ (vertex U) of vertex T, we do-

 

  1. color[v] = GREY
  2. d[v] = d[T] + 1 = 2 + 1 = 3
  3. π[v] = T
  4. Enqueue all adjacent white vertices of T in queue Q

 

  • color[T] = BLACK

 

 

Step-06:

 

  • Dequeue vertex X from the queue Q
  • For all adjacent white vertices ‘v’ (vertex Y) of vertex X, we do-

 

  1. color[v] = GREY
  2. d[v] = d[X] + 1 = 2 + 1 = 3
  3. π[v] = X
  4. Enqueue all adjacent white vertices of X in queue Q

 

  • color[X] = BLACK

 

 

Step-07:

 

  • Dequeue vertex V from the queue Q
  • There are no adjacent white vertices to vertex V.
  • color[V] = BLACK

 

 

Step-08:

 

  • Dequeue vertex U from the queue Q
  • There are no adjacent white vertices to vertex U.
  • color[U] = BLACK

 

 

Step-09:

 

  • Dequeue vertex Y from the queue Q
  • There are no adjacent white vertices to vertex Y.
  • color[Y] = BLACK

 

 

Since, all the vertices have turned black and the queue has got empty, so we stop.

This is how any given graph is traversed using Breadth First Search (BFS) technique.

 

To gain better understanding about Breadth First Search Algorithm,

Watch this Video Lecture

 

Next Article- Prim’s Algorithm

 

Get more notes and other study material of Design and Analysis of Algorithms.

Watch video lectures by visiting our YouTube channel LearnVidFun.