DEV Community

Lakkireddy Pulla Reddy

Posted on

Recap the use of some Algorithms

Binary Search Algorithm

``````
- Efficient algorithm for finding an item from a **sorted list**
of items

- The time complexity of the binary search algorithm is O(log n)
``````

``````- Breadth–first search (BFS) is an algorithm for traversing or searching tree or graph data structures.
- It uses a queue.
- The time complexity of BFS traversal is O(V + E), where V and E are the total number of vertices and edges in the graph.
``````

Depth First Search (DFS) Algorithm

``````- Depth–first search (DFS) is an algorithm for traversing or searching tree or graph data structures.
- It uses a stack.
- The time complexity of DFS traversal is O(V + E), where V and E are the total number of vertices and edges in the graph.
``````

Merge Sort Algorithm

``````- Merge sort is an efficient sorting algorithm that produces a stable sort, which means that if two elements have the same value, they hold the same relative position in the sorted sequence as they did in the input
- Merge sort is a Divide and Conquer algorithm
- The worst case time complexity of merge sort is O(n log(n))

``````

Quicksort Algorithm

``````
- Quicksort is an efficient in-place sorting algorithm, which usually performs about two to three times faster than merge sort and heapsort when implemented well.
- Time complexity of Quicksort is O(n log(n)).

``````

Kruskal’s Algorithm

``````
- Kruskal’s Minimum Spanning Tree algorithm, a greedy algorithm to find a minimum spanning tree for a connected weighted graph.
- Kruskal's algorithm's time complexity is O(E log V), V being the number of vertices

``````

All-Pairs Shortest Path

``````
- The Single-Source Shortest Path (SSSP) problem consists of finding the shortest paths between a given vertex v and all other vertices in the graph.
- The All-Pairs Shortest Path(APSP) problem is the determination of the shortest graph distances between every pair of vertices in a given graph
``````

Floyd Warshall Algorithm

``````
- The Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem. The problem is to find shortest distances between every pair of vertices in a given edge weighted directed Graph.
- The Floyd-Warshall all-pairs shortest path runs in O(n^3) time.

``````

Dijkstra’s Algorithm

``````
- Dijkstra's algorithm is the iterative algorithmic process to provide us with the shortest path from one specific starting node to all other nodes of a graph

- Time Complexity of Dijkstra's Algorithm is O(V^2)
``````

``````
- Simply putting for writing a logic to find the sum of contiguous subarray  within a one-dimensional array of numbers that has the largest sum, we use Kadane’s Algorithm.

``````

Lee Algorithm

``````
- The Lee algorithm is one possible solution for maze routing problems based on breadth-first search.

- It always gives an optimal solution, if one exists, but is slow and requires considerable memory
``````

Floyd’s Cycle Detection Algorithm

``````As the name it self states, Floyd's Cycle detection algorithm or Hair Tortoise algorithm is used to detect if there is a cycle in a linked list
``````

Union Find Algorithm

``````- Recap Dis Joint Data Structure.
- A union-find algorithm is an algorithm that performs two useful operations find and union.
- Find: Determine which subset a particular element is in.
- Union: Join two subsets into a single subset.
``````

KMP Algorithm

``````- The Knuth–Morris–Pratt string-searching algorithm (or KMP algorithm) searches for occurrences of a "word" W within a main "text string" S.

- It is a Pattern Matching Algorithm
``````

Sorting Algorithms

``````
- A Sorting Algorithm is used to rearrange a given array or list elements according to a comparison operator on the elements.

- Examples
1. Insertion Sort Algorithm
2. Selection Sort Algorithm
3. Counting Sort Algorithm
4. Heap Sort Algorithm ​

``````

Euclid’s Algorithm

``````
-  Efficient algorithm for computing the greatest common divisor (GCD)
``````