Important Algorithms

Vinod Jatav

·

Follow

2 min read

·

Oct 5, 2024

--

Listen

Share

Dynamic Programming and Graph Algorithms

1. Dynamic Programming — Optimization technique used to solve problems by breaking them into overlapping sub-problems.
2. DFS (Depth First Search) — A graph traversal technique that explores as far as possible along each branch before backtracking.
3. BFS (Breadth First Search) — A graph traversal method that explores all nodes at the present depth before moving on to the nodes at the next depth level.

Shortest Path Algorithms

1. Dijkstra’s Algorithm — Finds the shortest path from a source node to all other nodes in a weighted graph.
2. Floyd-Warshall Algorithm — Solves the all-pairs shortest path problem, finding the shortest paths between every pair of vertices in a graph.
3. Bellman-Ford Algorithm — Computes shortest paths from a single source vertex to all other vertices, allowing for negative edge weights.

Minimum Spanning Tree Algorithms

1. Kruskal’s Algorithm — A greedy algorithm to find a minimum spanning tree for a connected, weighted graph.
2. Prim’s Algorithm — Another greedy algorithm that builds a minimum spanning tree by adding the smallest edge at each step.

Other Graph Algorithms

1. Topological Sorting — A linear ordering of vertices such that for every directed edge from vertex u to vertex v, u comes before v in the ordering.
2. Floyd’s Cycle Detection Algorithm — Used to detect cycles in a sequence of iterated function values, commonly applied in linked lists.

Search and Sorting Algorithms

1. Binary Search — A search algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search interval in half.
2. Binary Search Tree (BST) Operations — Operations like insertion, deletion, and searching in a binary search tree.

Sorting Algorithms

1. Quick Sort — A divide-and-conquer sorting algorithm that picks a pivot and partitions the array into two halves.
2. Merge Sort — A divide-and-conquer algorithm that divides the array into two halves, recursively sorts them, and then merges the sorted halves.
3. Heap Sort — A comparison-based sorting algorithm that uses a binary heap data structure to sort elements.