Skip to content

Instantly share code, notes, and snippets.

View RitamChakraborty's full-sized avatar
💭
Smug smiling 😏

Ritam Chakraborty RitamChakraborty

💭
Smug smiling 😏
  • Cresen Solutions
  • India
View GitHub Profile
@RitamChakraborty
RitamChakraborty / KNFAlgorithm
Last active August 11, 2019 17:28
Knuth-Morris-Pratt string matching algorithm
import java.util.Arrays;
import java.util.HashMap;
public class KNFAlgorithm {
private static int[] getTable(String s) {
char[] chars = s.toCharArray();
int n = chars.length;
HashMap<Character, Integer> map = new HashMap<>();
int[] table = new int[n];
@RitamChakraborty
RitamChakraborty / StringMatching.java
Created August 11, 2019 17:17
Basic solution for string matching algorithm.
public class StringMatching {
private static boolean contains(String a, String b) {
int i = 0;
int n1 = a.length();
int n2 = b.length();
char[] ch1 = a.toCharArray();
char[] ch2 = b.toCharArray();
while (i < n1) {
@RitamChakraborty
RitamChakraborty / SumOfSubsets.java
Created August 7, 2019 17:37
Sum of Subsets problem implemented in java
import java.util.Arrays;
public class SumOfSubsets {
private static int required;
private static int[] arr;
private static int n;
private static void fun(int i, int[] sol, int sum, int remaining) {
if (remaining >= 0 && sum <= required) {
if (sum == required && remaining == 0) {
@RitamChakraborty
RitamChakraborty / NQueensProblem.java
Created August 7, 2019 16:02
N-Queens Problem implemented in java
import java.util.*;
public class NQueensProblem {
private static int n;
private static char[][] arr;
private static LinkedHashSet<String> finalSolution;
static {
finalSolution = new LinkedHashSet<>();
}
@RitamChakraborty
RitamChakraborty / LongestCommonSubsequenceWithDynamicProgramming.java
Created August 6, 2019 19:12
Longest Common Subsequence problem with Dynamic Programming.
mport java.util.*;
public class LongestCommonSubsequenceWithDynamicProgramming {
public static void main(String[] args) {
char[] A = "bd".toCharArray();
char[] B = "abcd".toCharArray();
int[][] arr = new int[A.length + 1][B.length + 1];
for (int i = 1; i <= A.length; i++) {
@RitamChakraborty
RitamChakraborty / LongestCommonSubsequenceWithMemorization.java
Created August 6, 2019 19:11
Longest Common Subsequence problem using recursion with memorization.
import java.util.Arrays;
public class LongestCommonSubsequenceWithMemorization {
private static char[] A;
private static char[] B;
private static int[][] arr;
private static int longestCommonSubsequent(int i, int j) {
if (i == A.length || j == B.length) {
return 0;
@RitamChakraborty
RitamChakraborty / LongestCommonSubsequenceWithoutMemorization.java
Created August 6, 2019 19:09
Longest Common Subsequence problem using recursion without using memorization.
public class LongestCommonSubsequenceWithoutMemorization {
private static char[] A;
private static char[] B;
private static int longestCommonSubsequent(int i, int j) {
if (i == A.length || j == B.length) {
return 0;
} else if (A[i] == B[j]) {
return 1 + longestCommonSubsequent(i + 1, j + 1);
} else {
@RitamChakraborty
RitamChakraborty / TravellingSalesmanProblem.java
Created August 6, 2019 04:54
Travelling Salesman Problem implemented in java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class TravellingSalesmanProblem {
private static final int startingIndex;
private static final int[][] arr = {{0, 10, 15, 20}, {5, 0, 9, 10}, {6, 13, 0, 12}, {8, 8, 9, 0}};
@RitamChakraborty
RitamChakraborty / BFSandDFS.java
Created July 29, 2019 19:40
Breath First Search and Depth First Search implementation of a given graph in Java
import java.util.ArrayDeque;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import java.util.stream.Collectors;
import java.util.stream.Stream;
class Node {
int data;
List<Node> neighbours;
@RitamChakraborty
RitamChakraborty / ZeroOneKnapsackProblem.java
Last active July 29, 2019 19:39
Solution for 0-1 Knapsack Problem.
import java.util.Arrays;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class ZeroOneKnapsackProblem {
public static void main(String[] args) {
int max = 8;
int n = 4;
int[] p = {1, 2, 5, 6};
int[] w = {2, 3, 4, 5};