Search: Java
-
Prim's algorithm in Java
Prim's algorithm is used to find a minimum spanning tree. It is very similar to Kruskal's algorithm of finding shortest path in a graph. Prim's algorithm starts from a vertex and then keeps following the minimum distant edges to discover vertices, given that the vertex was not discovered before. Current implementation uses a simple and straight implementation in java. It can be further improved by improving sorting algorithm and using Min-Heap data structure for vertices. Those are not implemented to keep it simple enough to understand for all.
-
Kruskal's algorithm in Java
Kruskal's algorithm is well known for finding MST or minimum spanning tree. First it sorts all the edges in non-decreasing order. Then, it keeps taking edges from the sorted list given that, at least one of the vertices at two ends of the edge is not discovered before. Current implementation uses java and pretty straight forward approach. It can be further improved by imporving sorting algorithm and using a custom Set data structure for set operations.
-
Dijkstra in Java
Dijkstra's algorithm is a known graph algorithm.
Dijkstra calculates shortest path to all the vertices starting from a single vertex. It's running time can be improved by using efficient sorting and more efficient data structure. But, for simplicity to make the implementation easy to understand for all, current implementation in java follows very simple sorting algorithm and simple data structure.
-
0-1 Knapsack problem in Java
0-1 knapsack is very interesting and famous problem in computer science to describe DP. Here a thief enters a shop where there are only one piece of items. The thief has a bag with him where he has a maximum weight limit to cary (we dont care about the volume of the goods, only weight). Given each items weight and price in the shop, your task is to help the thief to maximize his profit. Current implementation in java uses DP to solve this problem.
-
Continuous knapsack in Java
Continuous knapsack is a famous problem in computer science to describe greedy algorithms. If a thief enters a shop to steal goods, where goods can be taken as fractions too (if needed). The thief has a maximum weight limit he can take with him. Given all the products weights and prices in the shop, you task is to help(!) the thief to maximize his profit.
Current implementation in java uses Greedy approach to solve.
-
LCS - Longest common substring
LCS or longest common substring is a very interesting problem in computer science. Here, we have to find the maximum matching length (and the matching itself) between two strings. Current implementation in java makes use of DP problem solving strategy.
-
DFS - depth first search
DFS or depth first search is a very common graph searching/traversing algorithm in graph theory. It is implemented using a stack. However, a recursive version is also possible. Current implementation in java makes use of Graph and Stack classes developed previously.
-
BFS (breadth first search) search algorithm
BFS or breadth first search is a very common graph searching/traversing algorithm in graph theory. It is implemented using a queue. However, a recursive version is also possible. Current implementation in java makes use of Graph and Queue classes developed previously.
-
Graph data structure
Graph is a data structure used in many algorithms. It's vertices are represented by a separate class, Vertex. There is a data (Object type) field in vertex class, which can be used to store any data. Vertex class can be modified to hold any information (e.g. Student, Account, etc.) by using the example.
-
BucketSort in Java
Bucket sort is a non-comparing sorting algorithm. It can be very efficient for sorting closed small ranged numbers. Because, it running time is O(dn), where d is the difference between minimum and maximum input value. It uses queue as bucket for each position. If the numbers are arbitrary without any range or the range is too high, this sorting algorithm is not preferred. Because, it will take huge amount of memory for inputs with large range.