Solving the Fractional Knapsack Problem
While the 0/1 Knapsack problem restricts you to take an item entirely, Fractional Knapsack problem allows you to take fractions of an item.
Category: Algorithms
Travelling Salesman Problem using Held-Karp Algorithm | Dynamic Programming
The Held-Karp algorithm is an efficient dynamic programming approach for solving the Travelling Salesman Problem (TSP). The algorithm builds up a table to store the optimal cost of visiting subsets of cities.
Travelling Salesman Problem using Nearest Neighbour Algorithm
Given a list of cities and the distances between each pair of cities, find the shortest possible route that visits each city exactly once and returns to the origin city.
Comparing Performance of Disjoint-Set Algorithms: Quick Union, Quick Find, and Weighted Quick Union
Disjoint-set data structures, commonly known as Union-Find, are fundamental data-structures in computer science for efficiently solving problems related to connectivity in graphs or set operations.
Mersenne Twister Algorithm vs rand(): Generating Random Numbers
Understanding the differences between the Mersenne Twister algorithm and rand() method helps in selecting the appropriate method based on specific programming needs.
Comparing Order Statistics Algorithm and Min Heap for Finding the Kth Smallest Element
Both methods provide effective solutions for finding the kth smallest element in a list of numbers. Understanding their strengths and trade-offs will help you select the most suitable approach for your use case.
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.
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.