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) Algorithm

- 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

---

Single-Source Shortest Path VS

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)

---

Kadane’s Algorithm

- 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)