Data Structures and Algorithms

Data Structures and Algorithms: An Overview

In the previous tutorial on Data Structures, we were introduced to the data structures - their need and types. In simple words, an algorithm is just a set of instructions to perform any task. Data Structures and Algorithms go hand in hand. In this DSA tutorial, we will look at algorithms- their characteristics, needs, factors, etc. For more detailed theoretical and practical understanding, consider our Data Structures And Algorithms Certification course.

What is an Algorithm?

An algorithm is defined as a set of rules or a step-by-step procedure that is executed in a specific order to get the desired output of a particular problem. In computer language, it is a finite set of instructions carried out at a specific time for specific problem-solving operations. We can say that it is not the complete program or code; it is just the logic of a problem. Algorithms can be represented as an informal description using a Flowchart or Pseudocode.

Features of a Good Algorithm

• Input: An algorithm must have an input.
• Output: every algorithm should have well-defined outputs
• Finiteness: Every algorithm must have a finite number of steps or instructions to perform any specific task. In other words, the steps or instructions must be countable.
• Unambiguity: An algorithm should be unambiguous which means that the instructions in an algorithm should be clear and simple and must produce the required output.
• Effectiveness: Every step of the algorithm must be effective enough to produce the required output. The selected algorithm must be the most effective one among many different ways to solve a problem.
• Language independent: An algorithm must not have any relation with the language of the code. the algorithm should work for all programming languages and give the same output.

Data Flow of an Algorithm

• Problem: A problem can be a real-world problem or any instance of a real-world problem for which we need to find a solution. It is the problem statement that gives the programmer an idea of the issue at hand, the available resources, and the plan to execute.
• Algorithm: It is the set of instructions prepared after analyzing the problem statement.
• Input: After the algorithm is prepared, the required and the desired inputs are provided to the algorithm.
• Processing unit: The input will be given to the processing unit, and the processing unit will produce the desired output.
• Output: The output is the outcome or the result of the program.

Let's look at Some Examples of Algorithms

Algorithm to find the average of 3 numbers

Step 1: Start
Step 2: Declare variables num1, num2, num3, sum, average. 
Step 3: Read values num1, num2, and num3.
Step 4: Add num1, num2, and num3 and assign the result to sum.
 sum←num1+num2+num3
Step 5: Divide the sum by 3 and assign the result to average.
 average←sum/3
Step 7: Print Average
Step 6: Stop

Algorithm to find the product of 2 numbers

Step 1: Start
Step 2: Declare variables num1, num2, and product. 
Step 3: Read values num1, num2.
Step 4: Multiply num1, and num2 and assign the result to product.
 product←num1*num2
Step 7: Print the Product
Step 6: Stop

Read More - Data Structure Interview Questions for Experienced

Why Algorithms?

There are two reasons why we need algorithms:

• Scalability: The breaking down of a complex real-world problem into small steps to thoroughly analyze it is scalability.
• Performance: The breaking down of a problem into smaller steps makes the problem feasible and thus increases the performance of the solution.

Points to Remember While Designing Algorithms

• Modularity- If a huge problem can be easily broken down into smaller modules or steps, means that your algorithm facilitates modularity.
• Correctness- If the inputs provided produce the desired output, it means your designed algorithm i correct. The algorithm should also work correctly for all possible test cases of the problem at hand. A test case is a specification of inputs, executing conditions, testing procedures, and expected results, which can be developed from the problem statement itself.
• Maintainability- The algorithm should be designed such that it is easy to maintain and modify without making any major change at any point in time.
• Functionality- The steps of an algorithm should successfully solve a real-world problem.
• User-friendly- It should be easily understood by the programmers.
• Simplicity- It should be the simplest possible solution to a problem. In other words, the algorithm should have the best-case time complexity. The approach of the algorithm should be simple and easy to understand. It should produce the desired results.
• Extensible- The algorithm should facilitate reusability. If any other programmer wants to reuse your desired algorithm, he must be able to do so without any issues.

Approaches To Problem-Solving

1. Brute Force Algorithm

It is the simplest and the first approach to a problem. It is also known as an exhaustive search algorithm that searches all the possibilities to provide the required solution.

We will see the brute force technique in detail in the section Brute-force Algorithm in Data Structures.

2. Recursion

It is the problem-solving technique in which a function calls itself, either directly or indirectly. In other words, when a function calls itself, it is known as recursion. The function that is calling itself is called the recursive function.

We will see the Recursion technique in detail in the section Recursion in Data Structures.

• Divide and Conquer

This algorithm breaks a problem into sub-problems, solves all the sub-problems using different methods, and merges the solutions to get the final solution. It consists of the following three steps:

• Divide
• Solve
• Combine

We will see the divide and conquer technique in detail in the section Divide and Conquer algorithm

• Greedy algorithm

It is an algorithm paradigm in which the solution is built part by part. It makes an optimal choice on each iteration with the hope of getting the best solution and the best solution of the next part is selected. It is easy to implement and has a faster execution time.

We will see the greedy algorithm technique in detail in the section Greedy Algorithm.

• Dynamic programming

This algorithm uses the already found solution to avoid repetitive calculation of the same part of the problem. It divides the problem into smaller overlapping subproblems, solves them, and stores the intermediate results.

We will see the Dynamic programming technique in detail in the section Dynamic Programming.

• Backtracking

This technique solves the problem recursively and removes the solution if it does not satisfy the constraints of a problem. Whenever a solution fails we trace back to the failure point, build on the next solution, and continue this process till we find the solution or all possible solutions are looked after.

We will see the Backtracking technique in detail in the section Backtracking.

3. Randomized Algorithm

It assumes a random number as an input and calculates the potential outcomes. Depending on the outcome, alternative ways to solve the solution can be considered. They are simpler and more efficient than the deterministic algorithm.

4. Searching Algorithms

It is used for searching the specific key in a particular sorted or unsorted data. Some common problems that can be solved through the Searching Algorithm are Binary searchand Linear search.

5. Sorting Algorithms

They are used to sort data in ascending or descending order. It is also used for arranging data in an efficient and useful manner. Some common problems that can be solved through the sorting Algorithm are Bubble sort, insertion sort, Merge sort, Selection sort, and Quick sort.

6. Hashing Algorithms

Hashing algorithms work the same as the Searching algorithm but they contain an index with a key ID i.e. a key-value pair. In hashing, we assign a key to specific data. These algorithms provide security to the data. The most widely used hashing algorithm is MD5.

We will see the hashing technique in detail in the section Hashing in Data Structures.

Algorithm Analysis

The algorithm can be analyzed on two levels, i.e., before creation, and after creation of the algorithm. The following are the two analyses of an algorithm:

• Priori Analysis: It is the theoretical analysis of an algorithm that is done before implementing the algorithm. Various factors can be considered before implementing the algorithm like processor speed, which does not affect the implementation part.
• Posterior Analysis: It is a practical analysis of an algorithm. It is achieved by implementing the algorithm using any programming language. This analysis evaluates how much running time and space is taken by the algorithm.

Advantages of Algorithms

• An algorithm helps to understand the process, the inputs, and the possible outcomes.
• An algorithm breaks down complex operations into finite simple processes and facilitates the programmer to convert them into functions.
• It features expandability in understanding the problem. It analyses the situation with relevance to the real world.
• It ensures efficiency in writing a computer program.
• It is easy to debug or detect errors in an algorithm.
• An algorithm assures optimization of memory space.
• An algorithm provides multiple ways to solve a problem and thus facilitates the user to choose the fastest algorithm (with the lowest time complexity).

Disadvantages of Algorithms

• Algorithms are not suitable to solve complicated problems.
• Algorithms may be time-consuming.
• Expressing repetitive tasks, conditional statements, and complex mathematical formulas, in an algorithm may be difficult.

Summary

This session is an explanatory answer to the question 'What is DSA'. We saw in detail what are algorithms, their characteristics, types of algorithms, etc. If you want to get a practical understanding, enroll in our Dsa Course Program.