Understanding P, NP, and NP-Complete
This so-called P ≠ NP question has been one of the deepest, most perplexing open research problems in theoretical computer science.
Category: Algorithms
Knuth-Morris-Pratt (KMP) | String Searching Algorithm
The KMP algorithm improves the efficiency of string searching by utilizing the information gathered from previous character comparisons. It avoids unnecessary character comparisons by exploiting the knowledge of the pattern itself.
Permutations of a string
Each of these permutations represents a unique arrangement of the elements. Total number of permutations of a set will always be n!
Understanding Prim’s Algorithm for Minimum Spanning Tree in C++
Prim’s Algorithm is a popular greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, weighted graph.
Minimum Spanning Tree (MST) | Kruskal’s Algorithm in C++
Kruskal’s algorithm is one of the popular algorithms used to find an MST in a connected weighted graph. This algorithm is efficient, easy to understand, and guarantees the construction of a minimum-weight spanning tree.
Bellman-Ford Algorithm | Single source shortest path
This algorithm uses Relaxation, to find the shortest path between the source vertex and other vertices. It gradually expands the search space until the shortest path to the destination node is found.
Dijkstra’s Algorithm | Single source shortest path
Dijkstra’s algorithm works based on the principle of Greedy-approach, gradually expanding the search space until the shortest path to the destination node is found.
Order Statistics | Selection Algorithm
“Order Statistics” is a concept discussed in the book “Introduction to Algorithms”. It pertains to finding the ith order statistics of a set of n elements in linear time. ith order statistics is the ith smallest element in a set of n elements.
LRU (Least Recently Used) Cache | Algorithm & Implementation
LRU (Least Recently Used) Cache is a type of cache replacement algorithm, where the least recently used item is evicted when the cache is full.
Data Structures for Disjoint Sets | Union Find Algorithm
This data structure is useful in situations where we need to group items together based on certain criteria, and then perform operations on these groups.