My Algorithms
-
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.
-
RadixSort Algorithm in Java
Radix sort is a non comparing sort. It's performance is O(kn), where k is the maximum number of digits in inputs's decimal representation. It uses a queue to store number for each decimal digit. At each pass, it simply classifies inputs depending on the current decimal digit, starting from the least significant one.
-
Merge Sort in Java
Merge sort is a popular sorting algorithm with running time of O(n long n). It recursively splits the array in parts, sorts each part, then merges them. This strategy is known as divide an conquer algorithm.
-
Java QuickSort
Quick sort is very famous and efficient algorithm for sorting an arbitrary array. It first partitions the array with any pivot value then sorts each partitions recursively. It has worst case running time of O(n^2). But, an average case running time of O(n log n). Quick sort even out performs other sorting algorithms that have average case running time of O(n log n).
-
Bubble Sort Algorithm in Java
Bubble sort is very popular and one of the easiest sorting algorithms available. It passes over the array several times (actually less than the number of elements in the array). At each pass, it compares two consecutive elements and swaps them if necessary. It has worst case running time of O(n^2) and best case running time of O(n).
-
Java Binary Search
Binary search Algorithm is a very effective search algorithm for a sorted array. It has worst case running time of O(log n). This java implementation of binary search assumes input to be an integer array and the array is sorted in ascending order.
-
Binary Heap
Binary heap is a tree type data structure. It has all the properties of binary search trees including the following ones-
1) All the levels of the binary tree must be filled except the last one. Levels are filled from left to right order. This property is known as shape property.
2) Each node's value must be less than or equal to all it's child nodes values [for min-heap]. Or, Each node's value must be greater than or equal to all it's child nodes values [for max-heap]. This property is known as heap property.
-
Binary Search Tree (BST) in Java
Binary search tree is a tree type data structure. Each node can have at most two immediate children. Binary search tree (BST) also have some special properties- 1) For any node, the node value will be greater than the values of all the nodes of the left subtree (if any). 2) For any node, the node value will be less than (or equal to) the values of all the nodes of the right subtree (if any). 3) For any node, it's left and right subtrees (if any) will also be binary search trees.
Here is an implementation example of BST in Java.
-
Queue demo in Java
Queue is a FIFO (First In First Out) type data structure. The first item to enter queue always comes out of the queue first. In queue, data is inserted (enqueue) in its "rear" and extracted (dequeue) from its "front".
Here is an implementation of queue using Java. It stores integer type data. It's simple and easy to understand.
-
Single Sided Linked List in Java
Singly linked list (also known as, linked list) is a data structure that serves the purpose of a dynamic array. Every item in that list contains two parts- data, and pointer to next item. The first item is pointed by a pointer known as "head". And, the last item has "null" to its next, which means the end of list.
There can various of methods in a linked list, such as- goFirst(), insert(), remove(), etc. Here is an implementation of linked list in Java with basic functionality. It can hold integer type data.
-
Stack in Java
Stack is a LIFO (Last In First Out) type data structure. The last item to enter stack always comes out of the stack first. This data structure is very useful in implementing many algorithms.
Here is an implementation of stack using Java. It stores integer type data so it's a very simple implementation. Good as a tutorial for data structures 101.
-
Doubly Linked List in Java
Doubly linked list is a data structure that serves the purpose of a dynamic array. Every item in that list contains three parts- data, pointer to next item and pointer to previous item. The first and last items are pointed by pointers known as "head" and "tail" respectively. The last item has "null" to its next, which means the end of list. Similarly, the first item has "null" to its previous, which means starting of the list. Unlike singly linked list, this list is able to move in both forward and backward direction.
My Algorithm Requests
No requests posted yet.