Basics of Data Structure Algorithms

If I ask you what is your morning routine, what will you answer? Let me answer it for you. You will wake up in the morning, freshen up, you’ll go for some exercise, come back, bath, have breakfast, and then you’ll get ready for the rest of your day.

If you observe closely these are a set of rules that you follow daily to get ready for your work or classes. If you skip even one step, you will not achieve your task, which is getting ready for the day.

These steps do not contain the details like, at what time you wake up or which toothpaste did you use or did you go for a walk or to the gym, or what did you have in your breakfast. But all they do contain are some basic fundamental steps that you need to execute to perform some task. This is a very basic example of algorithms. This is an algorithm for your everyday morning.

In this article, we will be learning algorithms, their characteristics, types of algorithms, and most important the complexity of algorithms.

What are Data Structure Algorithms?

Algorithms are a finite set of rules that must be followed for problem-solving operations. Algorithms are step-by-step guides to how the execution of a process or a program is done on a machine to get the expected output.

• Do not contain complete programs or details. They are just logical solutions to a problem.
• Algorithms are expressible in simple language or flowchart.

Characteristics of an Algorithm in Data Structure

No one would follow any written instructions to follow a daily morning routine. Similarly, you cannot follow anything available in writing and consider it as an algorithm. To consider some instructions as an algorithm, they must have some specific characteristics :

1. Input: An algorithm, if required, should have very well-defined inputs. An algorithm can have zero or more inputs.

2. Output: Every algorithm should have one or more very well-defined outputs. Without an output, the algorithm fails to give the result of the tasks performed.

3. Unambiguous: The algorithm should be unambiguous and it should not have any confusion under any circumstances. All the sentences and steps should be clear and must have only one meaning.

4. Finiteness: The steps in the algorithm must be finite and there should be no infinite loops or steps in the algorithm. In simple words, an algorithm should always end.

5. Effectiveness: An algorithm should be simple, practically possible, and easy to understand for all users. It should be executable upon the available resources and should not contain any kind of futuristic technology or imagination.

6. Language independent: An algorithm must be in plain language so that it can be easily implemented in any computer language and yet the output should be the same as expected.

Data flow of the Algorithm in Data Structure

1. Problem: To write a solution you need to first identify the problem. The problem can be an example of the real-world for which we need to create a set of instructions to solve it.

2. Algorithm: Design a step-by-step procedure for the above problem and this procedure, after satisfying all the characteristics mentioned above, is an algorithm.

3. Input: After creating the algorithm, we need to give the required input. There can be zero or more inputs in an algorithm.

4. Processing unit: The input is now forwarded to the processing unit and this processing unit will produce the desired result according to the algorithm.

5. Output: The desired or expected output of the program according to the algorithm.

Why do we need Data Structure Algorithm?

Suppose you want to cook chole ( or chickpeas) for lunch. Now you cannot just go to the kitchen and set utensils on gas and start cooking them. You must have soaked them for at least 12 hours before cooking, then chop desired vegetables and follow many steps after that to get the delicious taste, texture, and nutrition.

This is the need for algorithms. To get desired output, you need to follow some specific set of rules. These rules do not contain details like in the above example, which masala you are using or which salt you are using, or how many chickpeas you are soaking. But all these rules contain a basic step-by-step guide for best results.

We need algorithms for the following two reasons :

1. Performance: The result should be as expected. You can break the large problems into smaller problems and solve each one of them to get the desired result. This also shows that the problem is feasible.

2. Scalability: When you have a big problem or a similar kind of smaller problem, the algorithm should work and give the desired output for both problems. In our example, no matter how many people you have for lunch the same algorithm of cooking chickpeas will work every single time if followed correctly.

Let us try to write an algorithm for our lunch problem :

1. Soak chickpeas in the night so that they are ready till the next afternoon.

2. Chop some vegetables that you like.

3. Set up a utensil on gas and saute the chopped vegetables.

4. Add water and wait for boiling.

5. Add chickpeas and wait until you get the desired texture.

6. Chickpeas are now ready for your lunch.

The real-world example that we just discussed is a very close example of the algorithm. You cannot just start with step 3 and start cooking. You will not get the desired result. To get the desired result, you need to follow the specific order of rules. Also, each instruction should be clear in an algorithm as we can see in the above example.

Similarly, let’s try to write an algorithm to concatenate two Strings:

1. Start

2. Declare three variables str1, str2, and str3.

3. Initialize the variables str1 with “DATA” and str2 with “FLAIR”

4. Concatenate the strings str1 and str2 and store the result in str3.

5. Print str3

6. Stop

Concatenation syntax is different in different programming languages. But the expected output in all languages is the same i.e DATAFLAIR. The same algorithm is also expressed by a flow chart below:

Factors of DS Algorithm

There are some factors that we need to consider before designing an algorithm:

1. Modularity:  If we can break a given problem into smaller modules, which is the basic definition of an algorithm, then we can conclude that designing modularity for the algorithm is achieved.

2. Correctness: If the given input produces the desired output then we can say an algorithm is correctly designed.

3. Simplicity: An algorithm must be simple to understand.

4. Maintainability: Designing an algorithm is done keeping in mind that whenever we need to redefine the algorithm, no major changes are required.

5. User friendly: The algorithm should be user-friendly else the programmer will not be able to understand it.

6. Functionality: Consider all logical steps possible in solving the problem.

7. Extensibility: Any other algorithm designer or programmer should be able to use your algorithm.

8. Robustness: Robustness refers to how well an algorithm can clearly define the problem.

Approaches for DS Algorithms

There are different approaches for designing an algorithm :

1. Divide and Conquer: This approach breaks the bigger problem into very small problems and for each problem, you design an algorithm. This is directly an implementation of an algorithm. It is designed in a step-by-step process and produces valid output.

2. Dynamic programming: This algorithm stores the intermediate results.  It follows five different steps for finding the optimal solution to the problem:

• Breaks problems into smaller problems to find the optimal solution.
• Find the optimal solution out of these subproblems.
• Store the results of these problems. This is memorization.
• Reuse the result instead of recomputing, in case needed.
• Compute the result of the whole problem

3. Brute force algorithm: The brute force algorithm is an algorithm for the most basic logic possible for solving a problem. It is very extensive and searches for all the possibilities to provide the required solution. Two types of brute force algorithms:

a. Optimizing: Finding all possible solutions to a bigger problem and then not terminating until we find the best solution among them.

b. Sacrificing: Stop as soon as the algorithm finds the best solution.

4. Greedy algorithm: It finds an optimal solution on each iteration in a hope of getting the best solution for the bigger problem. It is easy to implement and has a faster execution time but very rarely provides an optimal solution.

5. Randomized algorithm: Unlike other algorithms, some random bits are introduced by the algorithm and added to the input to produce a random output. These algorithms are simple and more efficient than deterministic algorithms.

6. Backtracking: Solve the problems recursively and remove the solution if it is not satisfied by the constraints of the problem.

7. Branch and bound algorithm: The limitation of the branch and bound algorithm is that they can be applied only to integer programming problems. It divides all the feasible solutions into two subsets and then these subsets are evaluated to find the best solution.

Importance of Algorithms in Data Structures

1. Theoretical importance: To break down a bigger problem into many smaller models we should be aware of all the theoretical aspects.

2. Practical importance: Nothing is complete without practical implementation.

Hence, algorithms and their importance can be considered as both theoretical and practical.

Issues in Data Structure Algorithms

• Algorithm designing is a step-by-step process and following some specific steps while doing that is mandatory.
•  Analyzing an algorithm’s efficiency can be a challenging task sometimes.

DS Algorithm analysis

We can analyze algorithms before or after creating them:

1. Priori analysis: Theoretical analysis of the algorithm which is usually done before implementing the algorithm. Various factors before implementing like the processing speed which does not affect the implementation part and output.

2. Posterior analysis: Posterior analysis a practical analysis of the algorithms. Done after the implementation of the algorithm in any programming language, this analysis evaluates the execution time and the memory occupied.

DS Algorithm Complexity

We can measure the complexity of algorithms in two ways:

1. Time complexity: It is the execution time required to completely execute the algorithm. Denoted by the asymptotic big O notation, the time complexity is usually calculated by counting the number of steps to finish the execution.

2. Space complexity: Total memory required to solve a problem and produce the result is space complexity. Also expressed in big O notation.

Type of Data Structures Algorithms

In data structures, there are usually two types of algorithms:

1. Search algorithm: Search algorithms find an element in a large database stored in computer memory. Two types of search algorithms are there:

a. Linear search: The control pointer traverses from the starting record of the database and continues moving to the next record until it finds the record under search. This is a kind of a brute force algorithm and is less efficient.

b. Binary search: This is the simplest algorithm to find an element in a database given that the records in a database are already arranged in either ascending or descending order.

2. Sort algorithm: Arranging elements in ascending or descending order use sorting algorithms. An efficient sorting algorithm can increase the efficiency of binary search algorithms.

Conclusion

After this article, we hope you have a basic understanding of what an algorithm is, its characteristics, and its types. We also saw what is the need for an algorithm and what are the steps to design a good algorithm that gives us the desired results.

Different types of approaches available for creating algorithms to choose based on the type of problem. One of the major objectives is to calculate the complexity of the algorithm and reduce it as much as possible.