Top 10 most used algorithm ppt template.pptx

This algorithm is especially popular in the fields of robotics, game development, and geographical information systems. The explanation will cover the algorithm's purpose, theoretical background, implementation details, and practical applications.

1. Segment Tree 1 Page Introduction Segment Tree  is a data structure that stores information about a range of elements in its nodes. It allows users to modify the array and perform range queries in smaller complexity Consider an array [1, 3, 5, 7, 9, 11]. A Segment Tree for this array would represent the following intervals: [1, 3], [4, 5], [6, 6], [7, 7], [8, 8], [9, 9], [10, 11] The tree would store aggregated information (e.g., sum, minimum, maximum) for each interval, allowing efficient queries and updates. Example: Real-time Application: Range Queries in Arrays: Answering queries like finding the sum, minimum, or maximum of elements in a given range efficiently. I nterval Overlaps: Detecting overlapping intervals or finding the first non-overlapping interval in a set. Time Complexity : O( nlogn ) Space Complexity : O(n)

2. Bellman-Ford Algorithm 2 Page Introduction Bellman-Ford algorithm is an example of dynamic programming It also find shortest path from single vertices to all vertices It also work for negative edge weights It is executed in iterations in which every edge is reached in every iterations Example A B C D Initial INF INF INF INF I = 1 A 10 A 100 A INF N I = 2 A 5 C 100 A 13 B I = 3 A 5 C 100 A 8 B I = 4 A 5 C 100 A 8 B

3. Bellman-Ford Algorithm 3 Page Time complexity Time complexity = (number of edges to be visited) * (number of iterations) = O(E*V) As E = V*(V-1)/2 , So E = O(V 2 ) Hence, Time Complexity = O(V 2 *V) = O(V 3 ) If the graph contain negative edge weight but not negative edge cycle then Dijstra’s algorithm may give wrong answer but Bellman-ford will give correct answer It will find all negative edge weight cycles present in the given graph if it is reachable from the source If any vertex is part of negative edge weight cycle then Bellman-ford algorithm will give shortest path as infinity Conclusion Real Time Application GPS Navigation Systems: Routing with traffic information: Bellman-Ford can incorporate real-time traffic data, where negative weights represent delays. It finds the shortest path considering both distance and potential congestion • Network Routing Protocols : Routing Information Protocol (RIP): A distance-vector routing protocol that uses Bellman-Ford to find the shortest paths between routers in a network. It handles potential negative weights due to link costs or delays. Space Complexity: O(V)

4. Knapsack Problem 4 Page Introduction The knapsack problem is a combinatorial optimization problem that involves selecting a subset from a larger set to maximize a specific value, subject to a constraint on the sum of the weights of the selected items. Types Fractional Knapsack In order to maximize the value we are allowed to break items and take fractions of them. Greedy algo followed 0/1 Knapsack We are not allowed to break the items, either take the full item or leave it. Dynamic programming algo followed Example Consider a knapsack with capacity = 20 and fractions are allowed. Consider three items are I1, I2 and I3 with following weight and profit. Then to find maximum profit using fractional knapsack following steps will be followed Step1:- Sort the items according to their per unit profit. Step2:- Now pick them up in that order and break them in fraction if they have more weight than knapsack capacity. Step3:- Keep picking them until knapsack is full.

5. Knapsack Problem 5 Page Time Complexity : Fractional Knapsack Time complexity, T(n) = Sorting according to priority + Picking up objects = nlogn +n T(n) = O( nlogn ) 0/1 Knapsack By greedy, Time complexity, T(n) = O(2 n ) Time Complexity, T(n) = O(m*n) REAL TIME APPLICATION Machine learning feature selection:  Choose the most informative features for a machine learning model to improve its accuracy while reducing model complexity. Cryptocurrency mining:  Select transactions for inclusion in a block to maximize the block's value while respecting size and difficulty constraints. Cloud computing resource allocation:  Distribute virtual machines or containers across physical servers to optimize resource utilization and meet service-level agreements. Space Complexity: O(n) Dynamic Solutions for 0/1 Knapsack problem

6. Priority Queue 6 Page Introduction A priority queue is a type of queue that arranges element based on their priority It may be prioritize according higher value as higher priority or lower value as lower priority There are several ways to implement a priority queue using an array, linked list, binary search tree or heap. Generally heap is used as priority queue algorithm as its time complexity is lowered. Example In Smaller value Higher priority, Min Heap algorithm used In Higher value Higher priority, Max Heap algorithm used REAL TIME APPLICATION Operating systems:  Process scheduling prioritizes tasks based on priority levels (e.g., system processes, user applications, background tasks) to optimize CPU usage and responsiveness. Sorting algorithm:  Uses a priority queue (specifically a heap) to repeatedly extract the maximum or minimum element, resulting in a sorted array. COMPLEXITY ANALYSIS Time Complexity: O(N* logN ) Space Complexity: O(N)

7. Longest path in a directed acyclic graph 7 Page Introduction The Longest Path in a Directed Acyclic Graph (DAG) aims to find the maximum length of a path from a source to a destination in a graph without cycles. REAL TIME APPLICATION Finding optimal routes :  Determining the path with the highest bandwidth, lowest delay, or minimum cost in data networks, communication systems, and transportation networks . Scheduling tasks:  Optimizing task sequences to minimize project duration and manage dependencies between tasks. COMPLEXITY ANALYSIS Time Complexity: O(V+E) Space Complexity: O(V+E) Example

8. Tarjan’s Algorithm 8 Page Introduction Tarjan's Algorithm is a graph traversal algorithm for finding strongly connected components (SCCs) in a directed graph Real-time Application: Compiler Optimization: Helps identify and optimize code structures with inherent parallelism. Network Routing: Identifies interconnected components in communication networks. Circuit Design: Ensures efficient design by recognizing interconnected modules. Time Complexity COMPLEXITY ANALYSIS Time Complexity: O(V+E) Space Complexity: O(V) Named after its creator, Robert Tarjan , introduced in 1972. Conclusion Tarjan's Algorithm is a key tool for analyzing the structure of directed graphs, emphasizing strongly connected components. Applied in compiler optimization, network routing, and circuit design for identifying and optimizing interconnected structures. Offers a balanced time complexity, making it suitable for real-world graph analysis tasks.

9. Prim’s Algorithm 9 Page Introduction In Prim’s algorithm we build the minimum cost spanning tree vertex by vertex Algorithm Take any vertex and find adjacent of that vertex and take minimum from them Find adjacent of new vertex and check for minimum here and previously left out vertices Repeat previous step to get the spanning tree Example A C F D E B A B C D E F A INF N INF N INF N INF N INF N A 7 A 2 A 6 A INF N INF N C 6 C 6 A 8 C 5 C F 6 C 3 F 7 F D 6 C 7 F B 4 B E Prim’s Table MST

10. Prim’s Algorithm 10 Page Time Complexity Time Complexity = (Build Heap) + (Choosing Min from Heap every time) + (Performing decrease key) = O(V)+O( logV )+O( ElogV ) = O((E+V)* logV )) = O(E* logV ) Space Complexity : O(V) REAL TIME APPLICATION Delivery and logistics : Optimizing delivery routes for trucks or drones to minimize travel time and fuel costs. GPS navigation systems : Finding the shortest or fastest routes between locations, considering factors like distance, traffic congestion, and road conditions.

11. Karatsuba Algorithm 11 Page Introduction The Karatsuba algorithm is a fast multiplication algorithm that divides the process of multiplying two numbers into smaller, recursive steps. Real-time Application: Large Number Multiplication: Efficiently multiplies large numbers in cryptography, signal processing, and scientific computing. Polynomial Multiplication: Accelerates polynomial operations in algebraic applications. Time Complexity Example Time Complexity: O(N^2) Space Complexity: O(V+E)

12. Fenwick Tree 12 Page Introduction The Fenwick Tree, or Binary Indexed Tree (BIT), is a data structure designed to efficiently perform range queries and updates on an array. Real-time Application: Prefix Sum Queries: Efficiently calculates the sum of elements in a range. Frequency Counting: Counts the number of occurrences of elements in a given range. Dynamic Programming: Used in algorithms like the Stock Span Problem for quick cumulative calculations. Time Complexity Construction Time: O(n*log(n)) Query/Update Time: O(log(n)) Hence, Time complexity = O(n*logn) Space Complexity : O(n) Example

13. Palindrome Partitioning 13 Page Introduction The Palindrome Partitioning Algorithm is a dynamic programming algorithm A palindrome is a sequence of characters that reads the same forwards and backward. Palindrome Partitioning is a classic algorithmic problem that involves breaking a given string into substrings in such a way that each substring is a palindrome Example Real-time Application: Data Validation: Ensuring data integrity by identifying and isolating palindromic segments in a sequence. Genomic Analysis: Analyzing DNA sequences and identifying palindromic patterns for genetic research. Image Processing: Identifying and isolating palindromic structures in images for pattern recognition. String Abba Output ["a", "b", "b", "a"] or["a", "bb", "a"] COMPLEXITY ANALYSIS Time Complexity: O(N 2 ) Space Complexity: O(V+E)