A repo of algorithms and data structures implemented while learning/revising algorithms and data structures, reading Introduction to Algorithms, practicing technical interview questions, etc.
Some examples:
-
Bellman-Ford's algorithm Implemented this algorithm, as explained in CLRS 24.1, to detect a negative cycle in a given graph. This was in the context of solving, partially, the general infinite arbitrage problem. The goal was to detect whether it's possible to start with one unit of currency, perform a series of exchanges and get more than one unit of the same currency
-
Dijkstra's algorithm Implemented Dijkstra's algorithm, as explained in CLRS 24.3, to find the minimum cost of a series of flights from one city to another.
-
Strongly Connected Components Implemented an algorithm, as explained in CLRS 22.5, to count the number of SCCs in a graph. This was in the context of solving a problem to check whether any intersection in a city is reachable from any other.
-
Prim's algorithm Implemented Prim's algorithm, as explained in CLRS 23.2, to solve a problem to optimally connect cities such that the distance between any two cities as well as the length of the road network connecting all cities is optimal
-
Topological sort I implemented the topological sort procedure, as explained in CLRS 22.4, in the context of solving a problem to print a CS curriculum that was represented as a weighted graph.
-
Breadth first search A straightforward implementation of BFS to compute the minimum number of flight segments from one city to another.
-
Used DFS to determine if directed graph with weights contains a cycle. This was in the context of determining whether a given CS curriculum, represented as a directed graph, is valid.
-
Used DFS to determine if there's a path between 2 vertices. This was in the context of solving a problem to detect an exit from a maze.