Algorithm Lecture Notes PDF

Algorithm Searching Algorithm  Searching algorithms are used to find a specific element in an array, string, linked list, or some other data structure.  The most common searching algorithms are: Linear Search – In this searching algorithm, we check for the element iteratively...

Algorithm Searching Algorithm  Searching algorithms are used to find a specific element in an array, string, linked list, or some other data structure.  The most common searching algorithms are: Linear Search – In this searching algorithm, we check for the element iteratively from one end to the other. Binary Search – In this type of searching algorithm, we break the data structure into two equal parts and try to decide in which half we need to find for the element. Ternary Search – In this case, the array is divided into three parts, and based on the values at partitioning positions we decide the segment where we need to find the required element. Sorting Algorithm  Sorting Algorithm is used to rearrange a given array or list elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of element in the respective data structure.  There are a lot of different types of sorting algorithms. Some widely used algorithms are: Bubble Sort Selection Sort Insertion Sort Quick Sort Merge Sort Divide and Conquer Algorithm  Divide and Conquer is an algorithmic paradigm. A typical Divide and Conquer algorithm solves a problem using following three steps. 1. Divide: Break the given problem into subproblems of same type. 2. Conquer: Recursively solve these subproblems 3. Combine: Appropriately combine the answers  This is one interesting and important algorithm to be learned in your path of programming. As the name suggests, it breaks the problem into parts, then solves each part and after that again merges the solved subtasks to get the actual problem solved. Greedy Algorithms  This algorithm builds up the solution one piece at a time and chooses the next piece which gives the most obvious and immediate benefit i.e., which is the most optimal choice at that moment. So the problems where choosing locally optimal also leads to the global solutions are best fit for Greedy.  For example, consider the Fractional Knapsack Problem. The local optimal strategy is to choose the item that has maximum value vs weight ratio. This strategy also leads to a globally optimal solution because we are allowed to take fractions of an item. Recursion  Recursion is one of the most important algorithms which uses the concept of code reusability and repeated usage of the same piece of code. Backtracking Algorithm  Backtracking is an algorithmic technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time  The Backtracking algorithm is derived from the Recursion algorithm, with the option to revert if a recursive solution fails, i.e. in case a solution fails, the program traces back to the moment where it failed and builds on another solution. So basically it tries out all the possible solutions and finds the correct one. Dynamic Programming  The main concept of the Dynamic Programming algorithm is to use the previously calculated result to avoid repeated calculations of the same subtask which helps in reducing the time complexity.  Another crucial algorithm is dynamic programming. Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for the same inputs, we can optimize it using Dynamic Programming. Pattern Searching  The Pattern Searching algorithms are sometimes also referred to as String Searching Algorithms and are considered as a part of the String algorithms. These algorithms are useful in the case of searching a string within another string. Mathematical Algorithms  These algorithms are designed to solve Mathematical and Number Theory problems. They requires in-depth knowledge of different mathematical subjects like GCD and LCM Prime Factorization and Divisors Fibonacci Numbers Catalan Numbers Modular Arithmetic Euler Totient Function nCr Computations Set Theory Factorial Prime numbers and Primality Tests Sieve Algorithms, etc. Geometric Algorithms  These algorithms are designed to solve Geometric Problems. They requires in-depth knowledge of different mathematical subjects like:  Lines  Triangle  Rectangle  Square  Circle  3D Objects  Quadilateral  Polygon & Convex Hull  Bitwise Algorithms  The Bitwise Algorithms is used to perform operations at the bit-level or to manipulate bits in different ways. The bitwise operations are found to be much faster and are sometimes used to improve the efficiency of a program.  For example: To check if a number is even or odd. This can be easily done by using Bitwise-AND(&) operator. If the last bit of the operator is set than it is ODD otherwise it is EVEN. Therefore, if num & 1 not equals to zero than num is ODD otherwise it is EVEN. Randomized Algorithms  An algorithm that uses random numbers to decide what to do next anywhere in its logic is called Randomized Algorithm. For example, in Randomized Quick Sort, we use a random number to pick the next pivot (or we randomly shuffle the array). Typically, this randomness is used to reduce time complexity or space complexity in other standard algorithms. Branch and Bound Algorithm  Branch and bound is an algorithm design paradigm which is generally used for solving combinatorial optimization problems. These problems are typically exponential in terms of time complexity and may require exploring all possible permutations in worst case. The Branch and Bound Algorithm technique solves these problems relatively quickly.