Data Structure Algorithm

 

 What is an Algorithm?

An algorithm is a set of statements required to perform problem solving operations or to  execute specific task. 

 step by step strategy of solving a problem.
   An algorithm is a sequence of steps to solve a specific problem or an algorithm is a sequential set of clear steps that gives results and ends in a limited time.
  

The formal definition of an algorithm is that it consists of a limited set of instructions that are run in a specific order to perform a specific task. This is not a complete program or code; This is just a solution to the problem (logic), which can be presented as an informal description using a flowchart or pseudo code.

Characteristics of an Algorithm

The following are the characteristics of an algorithm:

• Input: The algorithm may or may not require input.

                     An algorithm has some input values. We can pass 0 or some other input value to an algorithm.

• Output: Each algorithm is expected to process at least one output.
• Unambiguity: An algorithm should be unambiguous, that means the instructions in an algorithm should be clear and simple.
• limitations: An algorithm should have finiteness or limitation. Here, The limitation means that the algorithm should include limited instructions, i.e., the instructions should be countable.
• Effectiveness: The algorithm must be effective because every suggestion in the algorithm affects the whole process.
• Language independent: The algorithm must be language-independent so that the instructions in the algorithm can be applied to any language with the same output.

Dataflow of an Algorithm

• Problem: The problem can be a real-world problem or a real-world problem for which you need to create a program or set of instructions. The sequence of steps is known as an algorithm.
• Algorithm:  An algorithm is a sequence of steps to solve a specific problem or an algorithm is a sequential set of clear steps that gives results and ends in a limited time.
• Input: we need to provide desired input to the algorithm after the algorithm design completed.
• Processing unit: Input will be given to the processing unit and the processing unit will generate the desired output.
• Output: The output is the outcome or the result of the program and displayed on screen.

Why do we need Algorithms?

We need algorithms because of the following reasons:

• Scalability: It helps us understand scalability. When you have a big real-world problem, you need to measure in small steps to easily analyze the problem.
• Performance: Real-world problems are not easily measure/ broken down into smaller steps. If the problem can be easily broken down into smaller steps it means the problem is viable.

Factors of an Algorithm

The following are the same factors that we need to consider it for designing an algorithm:

• Modularity: If we were given a problem and we could break it down into smaller modules or smaller steps, this is the basic definition of algorithm. This means that this feature is perfectly designed for algorithms.
• Accuracy : The accuracy of the algorithm is defined when the given inputs produce the desired output, meaning that the algorithm is designed algorithm. The algorithm has been properly analyzed.
• Maintainability: The Maintenance means that the algorithm should be designed in a very simple structured way so that when we redefine the algorithm.

            No major changes will be made to the algorithm.

• Functionality: Functionality it is a  various logical steps to solve the real-world problem.
• Robustness: Robustness means persistence. Persistence is how algorithms can clearly define your problem.
• User-friendly:  The algorithm should be User Friendly. If the algorithm should not be user-friendly, then the designer will not be able to explain algorithm to the programmer.
• Simplicity: The algorithm should be simple, so any one can be able to understand the algorithm easily.
• Extensibility: If other algorithm designers or programmers want to use your algorithm, it must be extensible.

Importance of Algorithms

1. Theoretical importance: When any real-world problem is given to us and we break the problem into small-small steps. To break down the problem, we have to know all the theoretical aspects.
2. Practical importance: As you know, theory cannot be complete without practical implementation. So, we have to know all the theoretical and practical aspects.

             the importance of algorithms can be considered both theoretical and practical.

Issues of Algorithms

The following are the same issues that come while designing an algorithm:

• How to design algorithms: You know that algorithm is a step-by-step process so you should follow some steps to design the algorithm.

Approaches of Algorithm

The following are the same approaches used after considering both the theoretical and practical importance to designing an algorithm:

• Brute force algorithm: General logic design is applied to design algorithms. It is also known as a complete search algorithm that explores all the possibilities to provide the required solution. Such algorithms are of two types:
  1. Optimizing: Finding all the solutions to the problem and then finding the best solution or knowing the value of the best solution will end if you know the best solution.
  2. Sacrificing: He will stop as soon as he finds the best solution.
• Divide and conquer: This is the very implementation of the algorithm. This allows you to design algorithms in step-by-step variations. It breaks down algorithms to solve problems in different ways. This allows you to divide the problem into different methods and create a valid output for valid input. This valid output is passed to another function.
• Greedy algorithm: This is an algorithm pattern that makes optimal choices on each iteration in the hope of finding the best solution. It's easy to implement and has a fast execution time. But, there are extremely rare cases in which it provides optimal satisfaction.
• Dynamic programming: This makes the algorithm more efficient by storing intermediate results. It follows five different steps to find the optimal solution to the problem:
  1. It breaks down the problem into a subproblem to find the optimal solution.
  2. After breaking down the problem, it finds the optimal solution out of these subproblems.
  3. Stores the result of the subproblems is known as memorization.
  4. Reuse the result so that it cannot be recomputed for the same subproblems.
  5. Finally, it computes the result of the complex program.
• Branch and Bound Algorithm: Branch and bound algorithms can only be applied to integer programming problems. This approach divides all sets of viable solutions into smaller subsets. These subsets are further evaluated to find the best solution.
• Randomized Algorithm:As you can see in the usual algorithm, we have the default input and the required output. Algorithms that have some defined set of inputs and required outputs and follow some described steps are known as determinant algorithms. What happens when a random variable is presented in a random algorithm ?. In a random algorithm, some random bits are represented by the algorithm and added to the input to create an output, which is of a random nature. Random algorithms are simpler and more efficient than determinant algorithms.
• Backtracking: Backtracking is an algorithmic technique that fixes a problem frequently and solves the problem if it does not solve the problem.

The major categories of algorithms are given below:

• Sort:  Algorithms were developed to classify objects in a specific order.
• Search:  An algorithm is developed to find items in a data structure.
• Delete:  An algorithm has been developed to remove existing elements from the data structure.
• Insert:  An algorithm has been developed for inserting items into a data structure.
• Update:  An algorithm has been developed to update existing components in the data structure.

Algorithm Analysis

The algorithm can be analyzed on two levels, namely, before the first algorithm is created and after the second algorithm is created.

The below are the two analysis of an algorithm:

• Priori Analysis: Priori analysis is the theoretical analysis of an algorithm that is performed before the algorithm is applied. Various factors can be considered before implementing an algorithm such as processor speed, which has no effect on the implementation area.
• Posterior Analysis: Posterior Analysis is a practical analysis of algorithms. Practical analysis is achieved by applying algorithms using any programming language. This analysis basically evaluates how much running time and space the algorithm takes.

Algorithm Complexity

The performance of the algorithm can be measured in two factors they are as follows:

• Time complexity: The time complexity of the algorithm is the time it takes to complete the implementation of the program. The time complexity of the algorithm is indicated by the large o notation.
• Space complexity: The space complexity of the algorithm is the amount of space required to solve the problem and create the output. Like the complexity of time, the complexity of space is also expressed in large o notation.

Types of Algorithms

The following are the types of algorithm:

• Search Algorithm
• Sort Algorithm

Search Algorithm

Search algorithms are designed to examine components or retrieve components from any data structure they store. ( here, Components means elements ).

There are mainly two types of techniques available to search the data in an array:

• Linear search

• Binary search

Linear Search / Sequential Search:

sequential search is a simple algorithm.

as name suggests Sequential Search is a process to search key elements form the starting of the array to the until the required element not found. It compares the searchable (Key) element with all the elements in the array, if a match is found it returns the index of the element otherwise it returns -1. This algorithm should applied to on unsorted list.

Binary Search

A Binary algorithm is the simplest algorithm.

 Which finds the element very quickly. It is used to find elements from a sorted list.

 To apply a binary algorithm, the elements must be stored in a sequential order. If the elements  are stored randomly, binary search cannot be applied. It is used to find the middle element in the list.

Sorting Algorithms

Sorting algorithms are used to rearrange elements in ascending or descending order in an array or in a given data structure. The comparison determines the new order of operator components.

Why do we need a sorting algorithm?

• An efficient sorting algorithm is required to optimize the functionality of other algorithms, such as the binary search algorithm, because the binary search algorithm must be sorted in a specific order, mainly in ascending order.
• It creates information in a sequence, which is a human readable format.
• Searching a particular element in a sorted list is faster than the unsorted list.

Recommended

Asympototic Analysis

DS Array

2D Array

Topics :

                Introduction

               Searching and Sorting

               Linked List 

               Stack

                Queue

                Tree

                Graph