rohithpeddi’s gists

rohithpeddi / Dijkstra.java

Created December 21, 2016 17:43

Dijkstra using - Bag, Indexmin PriorityQueue

	/************************************************
	BAG - data structure to store vertices
	*************************************************/

	class Bag<Item extends Comparable<Item>> implements Iterable<Item> {

	private Node first;
	private int N;

	/**********NODE CLASS**********/

rohithpeddi / MatrixExponentiation.java

Created December 21, 2016 11:59

Matrix exponentiation used in many areas - For finding recurrences, fibonocci sum, etc

	/*
	Can be used for bigger powers but be careful of long value overflow
	current[][] - is the initial state of the matrix used
	result[][] - is the final matrix after exponentiation
	power - in the argument tells the exponent of the matrix
	choose mod accordingly !
	*/

	public class MatrixExponentiation{

rohithpeddi / EdgeConnectivity.java

Created December 21, 2016 06:39

	public class EdgeConnectivity{


	/************* DEPTH FIRST SEARCH IMPLEMENTATION **************/

	public void dfs_cycle(Graph G, int v,int toConnect,int notFrom){

	if(v == toConnect){ testmarked[v] = true; return;}

	//StdOut.println("Checking for v:"+ v + " ,toConnect:"+ toConnect+ " ,notFrom:"+ notFrom);

rohithpeddi / Biconnected.java

Created December 21, 2016 06:18

In graph theory, a biconnected graph is a connected and "nonseparable" graph, meaning that if any vertex were to be removed, the graph will remain connected. Therefore a biconnected graph has no articulation vertices.

	public class Biconnected{
	private int[] low;
	private int[] pre;
	private int count;
	private boolean[] articulation;

	public Biconnected(Graph G){
	low = new int[G.V()]; pre = new int[G.V()]; articulation = new boolean[G.V()];
	for(int i=0; i<low.length;i++){
	low[i]=-1; pre[i]=-1;

rohithpeddi / LinearProbingHashST.java

Created December 20, 2016 19:06

HashTable - which can be used to modify hash function as required

	import java.util.Scanner;

	import edu.princeton.cs.algs4.StdOut;

	public class LinearProbingHashST<Key,Value>{

	public int N;
	public int M =16;
	public Key[] keys;
	public Value[] vals;

rohithpeddi / ImprovementsOnMethods.java

Last active December 20, 2016 19:40

Interpolation Search, counting sort, bottom up merge sort, heap sort (main loop),

	public class ImprovementsOnMethods{

	/*
	INTERPOLATION SEARCH - improvement on binary search
	searches for closer values than always choosing mid values
	Time : O(loglogn) - for sorted and uniformly distributed arrays
	*/

	int interpolationSearch(int[] A, int key){
	int lo=0,hi=A.length-1;

rohithpeddi / SuffixArray.java

Created December 17, 2016 14:54

Uses 3-way quick sort with a cut to insertion sort for sorting suffixes

	/*
	Suffix array takes
	Space proportional to O(N)
	Time proportional to O(NlogN) to build

	*/

	public class SuffixArray {

	private String[] suffixes;

rohithpeddi / FordFulkerson.java

Created December 17, 2016 13:12

Using Bag data structure

	class Bag<Item extends Comparable<Item>> implements Iterable<Item> {

	private Node first;
	private int N;

	/**********NODE CLASS**********/

	private class Node{
	Item item; Node next;
	Node(Item k){

rohithpeddi / SegmentTree.java

Last active December 16, 2016 14:51

Segment Tree with Lazy Propogation


	//For theory refer: https://www.hackerearth.com/practice/notes/segment-tree-and-lazy-propagation/

	public class SegmentTree {

	private Node[] heap;
	private int[] array;
	private int size;

	/*********************************************

rohithpeddi / IntervalTree.java

Created December 16, 2016 12:48

Interval Tree implementation


	class Interval1D implements Comparable<Interval1D> {

	public final int min,max;

	public Interval1D(int min, int max){
	if(min<=max){
	this.min = min;
	this.max = max;
	} else {

Rohith Peddi rohithpeddi