WHAT IS DATA?

Data are individual facts, statistics, or items of information, often numeric. In a more technical sense, data are a set of values of qualitative or quantitative variables about one or more persons or objects, while a datum is a single value of a single variable.

• Data are the quantities, characters, or symbols on which operations are performed by a computer, which may be stored and transmitted in the form of electrical signals and recorded on magnetic, optical, or mechanical recording media.

Data types

• String (or str or text). Used for a combination of any characters that appear on a keyboard, such as letters, numbers and symbols.
• Character (or char). Used for single letters.
• Integer (or int). Used for whole numbers.
• Float (or Real). …
• Boolean (or bool)
• WHAT ARE DATA STRUCTURES.

In computer science, a data structure is a data organization, management, and storage format that enables efficient access and modification. 

More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data, i.e., it is an algebraic structure about data.

A data structure is a particular way of organizing data in a computer so that it can be used effectively.

For example, we can store a list of items having the same data-type using the array data structure.

WHAT ARE ALGORITHMS

In mathematics and computer science, an algorithm is a finite sequence of well-defined instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing

It is a process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer.”a basic algorithm for division”

An Algorithm is a sequence of steps that describe how a problem can be solved. Every computer program that ends with a result is basically based on an Algorithms, however, they are not just confined for use in computer programs; these can also be used to solve mathematical problems and on many matters of day-to-day life. Based on how they function, we can divide Algorithms into multiple types. Let’s take a look at some of the important ones.

Types of Algorithm

There are many types of Algorithms, but the fundamental types of Algorithms are:

1. Recursive Algorithm

This is one of the most interesting Algorithms as it calls itself with a smaller value as inputs which it gets after solving for the current inputs. In more simpler words, It’s an Algorithm that calls itself repeatedly until the problem is solved.

Problems such as the Tower of Hanoi or DFS of a Graph can be easily solved by using these Algorithms.

For example, here is a code that finds a factorial using a recursion Algorithm:

Fact(y)

If y is 0

return 1

return (y*Fact(y-1))  /* this is where the recursion happens*/

2. Divide and Conquer Algorithm

This is another effective way of solving many problems. In Divide and Conquer algorithms, divide the algorithm into two parts; the first parts divide the problem on hand into smaller subproblems of the same type. Then, in the second part, these smaller problems are solved and then added together (combined) to produce the problem’s final solution. Popular Course in this category

---

Merge sorting, and quick sorting can be done with divide and conquer algorithms. Here is the pseudocode of the merge sort algorithm to give you an example:

MergeSorting(ar[], l,  r)

If r > l

1. Find the mid-point to divide the given array into two halves:

middle m = (l+r)/2

2. Call mergeSorting for the first half:

Call mergeSorting(ar, l, m)

3. Call mergeSorting for the second half:

Call mergeSorting(ar, m+1, r)

4. Merge the halves sorted in step 2 and 3:

Call merge(ar, l, m, r)

3. Dynamic Programming Algorithm

These algorithms work by remembering the results of the past run and using them to find new results. In other words, a dynamic programming algorithm solves complex problems by breaking them into multiple simple subproblems and then it solves each of them once and then stores them for future use.

Fibonacci sequence is a good example for Dynamic Programming algorithms, you can see it working in the pseudo code:

Fibonacci(N) = 0                                                (for n=0)

= 0                                                                          (for n=1)

= Fibonacci(N-1)+Finacchi(N-2)                      (for n>1)

4. Greedy Algorithm

These algorithms are used for solving optimization problems. In this algorithm, we find a locally optimum solution (without any regard for any consequence in future) and hope to find the optimal solution at the global level.

The method does not guarantee that we will be able to find an optimal solution.

The algorithm has 5 components:

• The first one is a candidate set from which we try to find a solution.
• A selection function that helps choose the best possible candidate.
• A feasibility function that helps in deciding if the candidate can be used to find a solution.
• An objective function that assigns value to a possible solution or to a partial solution
• Solution function that tells when we have found a solution to the problem.

Huffman Coding and Dijkstra’s algorithm are two prime examples where the Greedy algorithm is used.

In Huffman coding, The algorithm goes through a message and depending on the frequency of the characters in that message; it assigns a variable-length encoding for each character. To do Huffman coding, we first need to build a Huffman tree from the input characters and then traverse through the tree to assign codes to the characters.

5. Brute Force Algorithm

This is one of the simplest algorithms in the concept. A brute force algorithm blindly iterates all possible solutions to search one or more than one solution that may solve a function. Think of brute force as using all possible combinations of numbers to open a safe.

Here is an example of Sequential Search done by using brute force:

Algorithm S_Search (A[0..n], X)

A[n] ← X

i ← 0

While A [i] ≠ X do

i ← i + 1

if  i < n return i

else  return -1

6. Backtracking Algorithm

Backtracking is a technique to find a solution to a problem in an incremental approach. It solves problems recursively and tries to solve a problem by solving one piece of the problem at a time. If one of the solutions fail, we remove it and backtrack to find another solution.

In other words, a backtracking algorithm solves a subproblem, and if it fails to solve the problem, it undoes the last step and starts again to find the solution to the problem.

N Queens problem is one good example to see Backtracking algorithm in action. The N Queen Problem states that there are N pieces of Queens in a chessboard, and we have to arrange them so that no queen can attack any other queen on the board once organized.

Now let’s take a look at the SolveNQ algorithm and Check Valid functions to solve the problem:

CheckValid(Chessboard, row, column)

Start

If there is a Queen at on the left of the current column, then return false.

If the queen is at the upper-left diagonal, then return false

If the queen is at the lower-left diagonal, then return false

Return true

End

SolveNQ(Board, Column)

Start

If all columns are full, then return true

For each row present in the chess board

Do

If, CheckValid( board, x, column), then

Set the queen at cell (x, column) on the board

If SolveNQ(board, column+1) = True, then return true.

Else, remove the queen from the cell ( x, column) from the board

Done

Return false

End

APPLICATION OF DATA STRUCTURE AND ALGORITHMS

From the origin of the first programming languages to the modern programming languages currently in use, computer programming has evolved quite a lot. It has now become more powerful, efficient, and advanced. However, the fundamental concepts and use of data structure and algorithms in computer programming have not changed. DSA has been the core of computer programming from the beginning.

You might have heard DSA being used mainly in the field of computer science. However, the use of DSA is not limited to the field of computing. We can also find the concept of DSA being used in day to day life. In this blog, we will discuss the common concept of DSA that is used in everyday life. But before that, let’s learn the basics of Data Structure and Algorithms first.

What is Data Structure and Algorithm (DSA)?

Data structure and algorithms is a branch of computer science that deals with creating machine-efficient and optimized computer programs. The term Data Structure refers to the storage and organization of data, and Algorithm refers to the step by step procedure to solve a problem. By combining “data structure” and “algorithm”, we optimize the codes in software engineering.

DSA in Software Development

Data structure and Algorithm (DSA) is applied in all disciplines of software development. DSA is the building block of the software development process. It is not limited to a single programming language. Although programming languages evolve or get dormant over time, DSA is incorporated into all of these languages.

The efficiency of software development depends on the choice of an appropriate data structure and algorithm.

There might be cases when you are provided with the most efficient data structure to work with a robust algorithm. However, if the two are not compatible with each other, the code will not produce the expected outcome. Thus, selecting an appropriate data structure for an algorithm is an essential part of software development.

Take, for example, the imperial system of measurement used in the US. Why is it so dreadful? The US has been using measuring units like inches, yard, miles, ounce, and pound for measurements. If you need to convert a yard into inches, you have to multiply it by 36. However, in the metric system, you can simply multiply by 1000 to convert meter into kilometer. It is thus easier for the mind to do the conversion in the metric system. That is why most people find the imperial system to be inconvenient. Another example of this inconvenience is that “ounce” is used for solid or liquid depending on the context.

The ease of conversion from one to another metric is the most important factor here. In this example, we can compare the measurement systems (i.e. the metric system and the Imperial system) to “data structures”, while the process of conversion from one unit to another can be thought of as the algorithm. This shows that choosing the right data structure has a great impact on the algorithm, and vice-versa.

Another critical facet of DSA usage in software development is the time and space constraints. These constraints check the availability of time and space for the algorithm. An optimized algorithm addresses both of these constraints based on the availability of resources. If memory is not an issue for the hardware, DSA focuses more on optimizing the running time of the algorithm. Similarly, if the hardware has both the constraints, then DSA must address both of them. You can learn more about the representation of these complexities on Asymtotics Analysis.

How can you relate DSA to your day to day life?

Let’s dive into some of the examples of the usage of DSA.

Data Structures

Stack Data Structure to Reverse a String

A stack is a linear data structure, “linear” meaning the elements are placed one after the other. An element can be accessed only after accessing the previous elements.

We can visualize a stack like a pile of plates placed on top of each other. Each plate below the topmost plate cannot be directly accessed until the plates above are removed. Plates can be added and removed from the top only.

Each plate is an element and the pile is the stack. In the programming terms, each plate is a variable and the pile is a data structure.

Why do we need a stack representation?

You might be wondering why a programmer needs to learn how to put a plate on a pile and take the plate out from the pile. Let’s find the answer to it. You are assigned a task of reversing a string. How would you do it?

Start selecting a character from the string and copy it into the new location one by one.

Now, let us copy these items from the top into the original location.

Great, we have successfully reversed a string using the property of stack (the new memory). Inserting and removing was only allowed from the top. This way stack is used in programming.

Queue Data Structure while Boarding a Bus

A Queue is also a linear data structure in which the elements are arranged based on FIFO (First In First Out) rule. It is like the passengers standing in a queue to board a bus. The person who first gets into the queue is the one who first gets on the bus. The new passengers can join the queue from the back whereas passengers get on the bus from the front.

Why do we need a Queue representation?

You may ask where a queue is used on a computer. Assume that you are in your office and there is a network of five computers. You have connected all these computers to a single printer. Suppose an employee wants to print his documents and sends a command to the printer through his computer. The printer receives the commands and starts printing the documents. At the same time, another employee sends commands to the printer. The printer puts the second command to the queue. The second command is executed only after the execution of the first command. This follows the FIFO rule.

Graph Data Structure in Social Media and Google Map

A Graph is a network of interconnected items. Each item is known as a node and the connection between them is known as the edge.

You probably use social media like Facebook, LinkedIn, Instagram, and so on. Social media is a great example of a graph being used. Social media uses graphs to store information about each user. Here, every user is a node just like in Graph. And, if one user, let’s call him Jack, becomes friends with another user, Rose, then there exists an edge (connection) between Jack and Rose. Likewise, the more we are connected with people, the nodes and edges of the graph keep on increasing.

Similarly, Google Map is another example where Graphs are used. In the case of the Google Map, every location is considered as nodes, and roads between locations are considered as edges. And, when one has to move from one location to another, the Google Map uses various Graph-based algorithms to find the shortest path. We will discuss this later in this blog.

Algorithms

Sorting Algorithm to Arrange Books in the Shelf

In simple terms, sorting is a process of arranging similar items systematically. For example, suppose you are arranging books on a shelf, based on the height of the books. In this case we can keep the taller books on the left followed by the shorter books or we can do vice versa.

This same concept is implemented in Sorting algorithms. Different sorting algorithms are available in DSA. Although the purpose of every algorithm remains the same, each algorithm works differently based on various criteria.

In the above example, if we want to sort the books as fast as we can then there are few points to be considered.

• Can the books be easily shuffled on the shelf? If the books are heavy, it may take us more time. Similarly, there may be other constraints. (accessibility)
• What is the number of books? (data size)
• How fast can we access them? (hardware’s ability)

Algorithms are built considering all these constraints to produce an optimal solution.

Searching Algorithm to Find a Book in a Shelf

Searching, as its name suggests, helps in finding an item.

Suppose you want to search for a specific book on a shelf. The books in the self are not arranged in a specific way. If you need to find the book in the shortest possible time, how would you do that? The solution to this is provided by DSA.

You may be thinking “I will look for the book from the beginning and locate it”. In this case, you will be searching for books one by one from the start to the end of the shelf. This same concept is implemented in Lineear search

But, what if the book is at the other end of the shelf? The above process might take a long time and will not provide a feasible solution.

Now, let’s try another procedure. Firstly, sort the books in ascending alphabetical order then search for the book in the middle. We are searching for a book that starts with J.

Since we are always looking at the middle position, the middle position between A and Z is M, not J.

Now, compare J with M. We know that J lies before M. So let’s start searching for J in the middle position of A and M. G is the mid element, again J is not found.

Since J lies between G and M, let’s find the mid element between them. Yeah, we have found J. Congratulations!!! .

And, you have just implemented Binary search

Shortest Path Finding Algorithms to Find the Shortest Path in Google Map

Have you ever thought about how Google Maps is able to show you the shortest path to your destination? Applications such as Google Maps are able to do that using a class of algorithms called Shortest Path Finding Algorithms.

These algorithms deal with finding the shortest path in a graph. As in the example discussed in the Graph data structure above, we can use graph algorithms to find the shortest path between two given locations on a map.

To illustrate the problem, let’s find the shortest distance between A and F in the following map.

What are the possible solutions to this problem? Let’s figure out the possible routes along with their path length.

We can see that the shortest path is Path-3. But, we have wasted time calculating other paths as well, which we are not going to use. In order to solve this problem without wasting time, we can start from A and check for the possible shortest neighboring paths (AC and AB). We have AC as the shortest path.

Now we are at C, again select the shortest path among its neighboring paths CE and CD, which is CD.

From D, we have a single path to F. From D, we can go to B as well but, B is already visited, so it is not considered. Select the path DF and we reach the destination.

Drop your comment