Learn Algorithms
Once you have cleared the concepts of Data Structures, now its time to start your journey through the Algorithms. Based on the type of nature and usage, the Algorithms are grouped together into several categories, as shown below:
Searching algorithms are used to locate specific data within a larger set of data. It helps find the presence of a target value within the data. There are various types of searching algorithms, each with its own approach and efficiency.
- Most common searching algorithms:
- Linear Search: Iterative search from one end to the other.
- Binary Search: Divide-and-conquer search on a sorted array, halving the search space at each iteration.
- Ternary Search: Divide-and-conquer search on a sorted array, dividing the search space into three parts at each iteration.
- Other searching algorithms:
- Related Topics:
Sorting algorithms are used to arranging the elements of a list in a specific order, such as numerical or alphabetical. It organizes the items in a systematic way, making it easier to search for and access specific elements.
There are a lot of different types of sorting algorithms. Some widely used algorithms are:
Sorting Algorithm | Description |
---|---|
Bubble Sort | Iteratively compares adjacent elements and swaps them if they are out of order. The largest element “bubbles” to the end of the list with each pass. |
Selection Sort | Finds the minimum element in the unsorted portion of the list and swaps it with the first element. Repeats this process until the entire list is sorted. |
Insertion Sort | Builds the sorted list one element at a time by inserting each unsorted element into its correct position in the sorted portion. |
Quick Sort | A divide-and-conquer algorithm that selects a pivot element, partitions the list into two sublists based on the pivot, and recursively applies the same process to the sublists. |
Merge Sort | Another divide-and-conquer algorithm that recursively divides the list into smaller sublists, sorts them, and then merges them back together to obtain the sorted list. |
Related Topics:
Divide and conquer algorithms follow a recursive strategy to solve problems by dividing them into smaller subproblems, solving those subproblems, and combining the solutions to obtain the final solution.
Steps:
- Divide: Partition the problem into smaller, independent subproblems.
- Conquer: Recursively solve each subproblem.
- Combine: Merge the solutions of the subproblems to obtain the final solution.
Examples:
- Merge Sort: Divides the array into two halves, sorts each half recursively, and merges the sorted halves.
- Quick Sort: Selects a pivot element, partitions the array into two subarrays based on the pivot, and recursively sorts each subarray.
- Binary Search: Divides the search space in half repeatedly until the target element is found or the search space is exhausted.
Related Articles:
As the name suggests, 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.
Some Important Problem of Greedy Algorithms are:
Algorithm | Description |
---|---|
Fractional Knapsack | Find the maximum total value of items that can be placed in the knapsack, allowing fractional inclusion of items. |
Dijkstra’s Algorithm | Finds the shortest path from a source vertex to all other vertices in a weighted graph. |
Kruskal’s Algorithm | Finds the minimum spanning tree of a weighted graph. |
Huffman Coding | Creates an optimal prefix code for a set of symbols, minimizing the total encoding length. |
Related Articles:
Recursion is a programming technique where a function calls itself within its own definition. It is usually used to solve problems that can be broken down into smaller instances of the same problem. For Example: Towers of Hanoi (TOH), Factorial Calculation and Fibonacci Sequence etc.
Steps:
- Base Case: Define a condition that stops the recursive calls and provides a solution.
- Recursive Case: Define the steps to break down the problem into smaller instances and make recursive calls.
- Return: Return the solution from the recursive calls and combine them to solve the original problem.
The point which makes Recursion one of the most used algorithms is that it forms the base for many other algorithms such as Tree traversals, Graph traversals, Divide and Conquers Algorithms and Backtracking algorithms.
Related Topics:
As mentioned earlier, 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.
Some important and most common problems of backtracking algorithms, that you must solve before moving ahead, are:
Problem | Description |
---|---|
Knight’s tour problem | Finding a sequence of moves by a knight on a chessboard such that it visits every square exactly once. |
Rat in a Maze | Finding a path from the starting position to the exit in a maze, with obstacles represented as walls. |
N-Queen Problem | Placing N queens on an N×N chessboard such that no two queens attack each other. |
Subset Sum Problem | Determining whether there exists a subset of the given set with a given sum. |
Sudoku | Solving a 9×9 grid puzzle with numbers from 1 to 9 such that each row, column, and 3×3 subgrid contains all the digits without repetition. |
Related Article:
Dynamic Programming is a method used in mathematics and computer science to solve complex problems by breaking them down into simpler subproblems. By solving each subproblem only once and storing the results, it avoids redundant computations, leading to more efficient solutions for a wide range of problems.
Key Concepts:
- Optimal Substructure: The optimal solution to a problem can be constructed from the optimal solutions to its subproblems.
- Overlapping Subproblems: Subproblems are often repeated in the larger problem, leading to redundant computations.
- Memoization / Tabulation: Storing the solutions to subproblems to avoid recomputation.
Some important and most common problems of dynamic programming algorithms, that you must solve before moving ahead, are:
Problem | Description |
---|---|
Fibonacci Sequence | Generating Fibonacci numbers using dynamic programming to avoid redundant calculations. |
Longest Common Subsequence | Finding the longest subsequence common to two sequences. |
Longest Increasing Subsequence | Finding the longest subsequence of a given sequence in which the elements are sorted in increasing order. |
0/1 Knapsack Problem | Determining the maximum value that can be obtained by selecting items with given weights and values, while not exceeding a specified weight limit. |
Rod Cutting Problem | Maximizing the profit by cutting a rod of given length into pieces and selling them according to given prices. |
Coin Change Problem | Determining the number of ways to make change for a given amount using a given set of coin denominations. |
Edit Distance | Finding the minimum number of operations (insertion, deletion, substitution) required to convert one string into another. |
Subset Sum Problem | Determining whether there exists a subset of a given set with a given sum. |
Longest Palindromic Subsequence | Finding the longest subsequence of a given sequence that is a palindrome. |
Maximum Subarray Sum | Finding the contiguous subarray with the largest sum within a given one-dimensional array. |
Partition Equal Subset Sum | Determining whether it is possible to partition a given set into two subsets with equal sum. |
Minimum Cost Path | Finding the minimum cost path from the top-left corner to the bottom-right corner of a given grid. |
Maximum Product Subarray | Finding the contiguous subarray with the largest product within a given one-dimensional array. |
Related Articles:
8. Graph Algorithms:
Graph algorithms in data structures and algorithms (DSA) are a set of techniques and methods used to solve problems related to graphs, which are a collection of nodes and edges. These algorithms are designed to perform various operations on graphs, such as searching, traversing, finding the shortest path, and determining connectivity. They are essential for solving a wide range of real-world problems, including network routing, social network analysis, and resource allocation.
Topic |
Topic’s Description |
Algorithm | Algorithm’s Description |
---|---|---|---|
Graph Traversal |
Techniques for visiting all vertices in a graph. |
Depth-First Search (DFS) | Explores as far as possible along each branch before backtracking. |
Breadth-First Search (BFS) | Explores neighbor vertices before moving to the next level of vertices. | ||
Minimum Spanning Trees |
Minimum Spanning Trees are the smallest trees that connect all nodes in a graph without forming cycles, achieved by adding the shortest edges possible. |
It finds a minimum spanning tree for a connected weighted graph. It adds the smallest weight edge that does not form a cycle. |
|
It also finds a minimum spanning tree for a connected weighted graph. It adds the smallest weight edge that connects two trees. |
|||
Topological Sorting |
Topological sorting is a linear ordering of the vertices in a directed acyclic graph (DAG) such that for every directed edge from vertex u to vertex v, u comes before v in the ordering. |
Kahn’s Algorithm | Kahn’s Algorithm finds a topological ordering of a directed acyclic graph (DAG). |
DFS-based Algorithm | DFS-based Algorithm use Depth-First Search to perform topological sorting in a directed acyclic graph (DAG). | ||
Shortest Path |
A shortest path in a graph is the path between two vertices in a graph that has the minimum sum of weights along its edges compared to all other paths between the same two vertices. |
Greedy algorithm to find the shortest path between all nodes in O(E * V logV) time. |
|
Finds the shortest path between all pairs of nodes in O(V^3) time. |
|||
Finds the shortest path from a single source in O(V * E) time. |
|||
Finds the shortest paths between all pairs of vertices in O(V^2 logV + V * E) time. |
|||
Strongly Connected Components |
A strongly connected component (SCC) of a directed graph is a maximal set of vertices such that there is a path from every vertex in the set to every other vertex in the set. |
Kosaraju’s Algorithm is a two-pass algorithm that efficiently finds the strongly connected components (SCCs) of a directed graph. |
|
Tarjan’s Algorithm is another efficient algorithm for finding SCCs in a directed graph |
Related Topics:
Pattern searching is a fundamental technique in DSA used to find occurrences of a specific pattern within a given text.
Below are some some standard pattern searching algorithms:
Algorithm | Description | Time Complexity |
---|---|---|
Brute-Force | It compares the pattern with every substring of the text | O(mn) |
Knuth-Morris-Pratt | It uses a precomputed failure function to skip unnecessary comparisons | O(m + n) |
Boyer-Moore | It compares the pattern from right to left, skipping characters based on the last mismatch | O(mn) |
Rabin-Karp | It uses hashing to quickly check for potential matches | O(m + n) |
Related Topics:
Mathematical algorithms are a class of algorithms that solve problems related to mathematical concepts. They are widely used in various fields, including Computer graphics, Numerical analysis, Optimization and Cryptography.
Algorithm | Description |
---|---|
GCD and LCM | Find the greatest common divisor and least common multiple of two numbers. |
Prime Factorization | Decompose a number into its prime factors. |
Fibonacci Numbers | Generate the Fibonacci sequence, where each number is the sum of the two preceding ones. |
Catalan Numbers | Count the number of valid expressions with a given number of pairs of parentheses. |
Modular Arithmetic | Perform arithmetic operations on numbers modulo a given value. |
Euler Totient Function | Count the number of positive integers less than a given number that are relatively prime to it. |
nCr Computations | Calculate the binomial coefficient, which represents the number of ways to choose r elements from a set of n elements. |
Prime Numbers and Primality Tests | Determine whether a given number is prime and find prime numbers efficiently. |
Sieve Algorithms | Find all prime numbers up to a given limit. |
Related Topics:
Geometric algorithms are a class of algorithms that solve problems related to geometry. Geometric algorithms are essential for solving a wide range of problems in computer science, such as:
Algorithm | Description |
---|---|
Convex Hull | Finds the smallest convex polygon that contains a set of points. |
Closest Pair of Points | Finds the two points in a set that are closest to each other. |
Line Intersection | Determines whether two lines intersect and, if so, finds the point of intersection. |
Point in Polygon | Determines whether a given point is inside or outside a polygon. |
Related Topics:
Bitwise algorithms are algorithms that operate on individual bits of numbers. These algorithms manipulate the binary representation of numbers to perform tasks such as bit manipulation, bitwise logical operations (AND, OR, XOR), shifting bits, and setting or clearing specific bits within a number. Bitwise algorithms are commonly used in low-level programming, cryptography, and optimization tasks where efficient manipulation of individual bits is required.
Topic | Description |
---|---|
Bit Shifting | Shifts bits to the left or right by a specified number of positions. |
Left shift (<<) | Shifts bits to the left, effectively multiplying the number by 2. |
Right shift (>>) | Shifts bits to the right, effectively dividing the number by 2. |
Extract bits | Using masks to extract specific bits from an integer. |
Setting bits | Using masks to set specific bits to 1 in an integer. |
Clearing bits | Using masks to set specific bits to 0 in an integer. |
Toggling bits | Using XOR (^) to toggle specific bits in an integer. |
Counting Set bits | Counting the number of set bits (1s) in an integer. |
Related Topics:
Randomized algorithms are algorithms that use randomness to solve problems. They make use of random input to achieve their goals, often leading to simpler or more efficient solutions.
Types of Randomized Algorithms:
- Las Vegas: Always produces a correct result, but the running time is random.
- Monte Carlo: May produce an incorrect result with a small probability, but the running time is usually faster.
Important Algorithms that uses Randomization Algorithms:
Algorithm | Description |
---|---|
QuickSort | A randomized sorting algorithm with an average-case time complexity of O(n log n). |
Skip List | A randomized data structure that provides fast search and insertion operations. |
Bloom Filter | A probabilistic data structure for efficient set membership testing. |
The Branch and Bound Algorithm is a method used in combinatorial optimization problems to systematically search for the best solution. It works by dividing the problem into smaller subproblems, or branches, and then eliminating certain branches based on bounds on the optimal solution. This process continues until the best solution is found or all branches have been explored.
Standard Problems on Branch and Bound Algorithm:
Unique Problem | Description |
---|---|
0/1 Knapsack using Branch and Bound | Implementation details of the branch and bound approach for solving the 0/1 Knapsack problem. |
0/1 Knapsack using Least Cost Branch and Bound | Solving the 0/1 Knapsack problem using the least cost branch and bound technique. |
8 puzzle Problem using Branch and Bound | Application of branch and bound to solve the 8 puzzle problem, a popular sliding puzzle game. |
N Queen Problem using Branch and Bound | Utilizing branch and bound to find solutions to the N Queens problem, a classic chess problem. |
Related Topics:
Learn Data Structures and Algorithms | DSA Tutorial
Data Structures and Algorithms (DSA) refer to the study of methods for organizing and storing data and the design of procedures (algorithms) for solving problems, which operate on these data structures. DSA is one of the most important skills that every computer science student must have. It is often seen that people with good knowledge of these technologies are better programmers than others and thus, crack the interviews of almost every tech giant. This DSA tutorial aims to help you learn Data Structures and Algorithms (DSA) quickly and easily.
Table of Content
- DSA Full Form
- What is DSA?
- How to learn DSA?
- Learn Data Structures
- Array
- String
- Linked Lists
- Matrix/Grid
- Stack
- Queue
- Heap
- Hash
- Tree
- Graph
- Learn Algorithms
- Searching Algorithm
- Sorting Algorithm
- Divide and Conquer Algorithm
- Greedy Algorithms
- Recursion
- Backtracking Algorithm
- Dynamic Programming
- Graph Algorithms:
- Pattern Searching
- Mathematical Algorithms
- Geometric Algorithms
- Bitwise Algorithms
- Randomized Algorithms
- Branch and Bound Algorithm
- Learn about Complexities
- Practice Problem Cheat Sheets
Contact Us