# Code Packet

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

This should really be split into many articles, but for now, it's all spewed here.

## Area and Centroid

```//Requires Graham.java
import java.awt.*;  //Point
import java.util.*; //Vector, Iterator

public double Area(Vector hull){
//this will calculate the area of any polygon
//with it's points listed clockwise or
//counterclockwisein hull.
//It will even work for cancave polygons
Point p, p2;
Iterator i = hull.iterator();
double area = 0;
if (hull != null && !hull.isEmpty()){
i = hull.iterator();
p = (Point)i.next();
while (i.hasNext()){
p2 = (Point)i.next();
area += p.x * p2.y; // area of polygon
area -= p.y * p2.x; // formula
p = p2;
}
//last edge
p2 = (Point)CH.get(0);
area += p.x * p2.y; // area of polygon
area -= p.y * p2.x; // formula
area /= 2.0;
}
return Math.abs(area);
}

public Point Centroid(Vector hull){
//this will calculate the centroid of any polygon
//with it's points listed clockwise or
//counterclockwise in hull.
//A centroid is the "center of mass" of a polygon.
//That is, the aveage point.
Point p, p2, centroid;
centroid = new Point(0,0);
Iterator i = hull.iterator();
double area = 0;
if (hull != null && !hull.isEmpty()){
i = hull.iterator();
p = (Point)i.next();
while (i.hasNext()){
p2 = (Point)i.next();
centroid.x+=(p.x+p2.x)*(p.x*p2.y-p2.x*p.y); //centroid
centroid.y+=(p.y+p2.y)*(p.x*p2.y-p2.x*p.y); //formula
p = p2;
}
//last edge
p2 = (Point)CH.get(0);
centroid.x+=(p.x+p2.x)*(p.x*p2.y-p2.x*p.y); //centroid
centroid.y+=(p.y+p2.y)*(p.x*p2.y-p2.x*p.y); //formula
centroid.x /= 6*Area(hull);
centroid.y /= 6*Area(hull);
}
return centroid;
}
```

## Closest Points

```// Find closest pair of points in the plane
// Only needed if naive O(n^2) algorithm is too slow
// Requires MergeSort (should be included with this)
// by Prof. Sartaj Sahni or his students?

public class ClosestPoints
{
// top-level nested classes
/** point in 2D */
public static class Point
{
// data members
double x, y;    // point coordinates

// constructor
public Point(double theX, double theY)
{
x = theX;
y = theY;
}
}

/** point with id, implements Comparable using x-coordinates */
public static class Point1 extends Point
implements Comparable
{
// data member
int id;         // point identifier

// constructor
public Point1(double theX, double theY, int theID)
{
super(theX, theY);
id = theID;
}

public int compareTo(Object x)
{
double xx = ((Point1) x).x;
if (this.x < xx)
return -1;
if (this.x == xx)
return 0;
return 1;
}

public boolean equals(Object x)
{return this.x == ((Point1) x).x;}
}

/** point with an integer field, implements Comparable using y-coordinates */
public static class Point2 extends Point
implements Comparable
{
int p;          // index to same point in array X

// constructor
public Point2(double theX, double theY, int theP)
{
super(theX, theY);
p = theP;
}

public int compareTo(Object x)
{
double xy = ((Point2) x).y;
if (this.y < xy)
return -1;
if (this.y == xy)
return 0;
return 1;
}

/** @return true iff this.y == x.y */
public boolean equals(Object x)
{return this.y == ((Point2) x).y;}
}

/** pairs of points and their distance */
public static class PointPair
{
// data members
Point1 a;       // one of the points
Point1 b;       // the other point
double dist;   // distance between a and b

// constructor
public PointPair(Point1 theA, Point1 theB, double theDist)
{
a = theA;
b = theB;
dist = theDist;
}
}

/** @return distance between points u and v */
public static double dist(Point u, Point v)
{
double dx = u.x - v.x;
double dy = u.y - v.y;
return Math.sqrt(dx * dx + dy * dy);
}

/** @param x[l:r] points sorted by x-coordinate, r > l
* @param y[l:r] points sorted by y-coordinate
* @param z[l:r] is used for work space
* @return closest pair of points in x[l:r] */
private static PointPair closestPair(Point1 [] x, Point2 [] y,
Point2 [] z, int l, int r)
{
if (r - l == 1)  // only two points
return new PointPair(x[l], x[r], dist(x[l], x[r]));

if (r - l == 2)
{// three points
// compute distance between all pairs
double d1 = dist(x[l], x[l + 1]);
double d2 = dist(x[l + 1], x[r]);
double d3 = dist(x[l], x[r]);
// find closest pair
if (d1 <= d2 && d1 <= d3)
return new PointPair(x[l], x[l + 1], d1);
if (d2 <= d3)
return new PointPair(x[l + 1], x[r], d2);
else
return new PointPair(x[l], x[r], d3);
}

// more than three points, divide into two
int m = (l + r) / 2;    // x[l:m] in A, rest in B

// create sorted-by-y lists in z[l:m] & z[m+1:r]
int f = l,      // cursor for z[l:m]
g = m + 1;  // cursor for z[m+1:r]
for (int i = l; i <= r; i++)
if (y[i].p > m) z[g++] = y[i];
else z[f++] = y[i];

// solve the two parts
PointPair best = closestPair(x, z, y, l, m);
PointPair right = closestPair(x, z, y, m + 1, r);

// make best closer pair of the two
if (right.dist < best.dist)
best = right;

MergeSort.merge(z, y, l, m, r);   // reconstruct y

// put points within best.d of midpoint in z
int k = l;                        // cursor for z
for (int i = l; i <= r; i++)
if (Math.abs(x[m].x - y[i].x) < best.dist)
z[k++] = y[i];

// search for closer category 3 pair
// by checking all pairs from z[l:k-1]
for (int i = l; i < k; i++)
{
for (int j = i + 1; j < k && z[j].y - z[i].y < best.dist; j++)
{
double dp = dist(z[i], z[j]);
if (dp < best.dist) // closer pair found
best = new PointPair(x[z[i].p], x[z[j].p], dp);
}
}
return best;
}

/** @return closest pair of points in array x
* @return null if fewer than two points in x */
public static PointPair closestPair(Point1 [] x)
{
if (x.length < 2) return null;

// sort on x-coordinate
MergeSort.mergeSort(x);

// create a point array sorted on y-coordinate
Point2 [] y = new Point2 [x.length];
for (int i = 0; i < x.length; i++)
// copy point i from x to y and index it
y[i] = new Point2(x[i].x, x[i].y, i);
MergeSort.mergeSort(y);  // sort on y-coordinate

// create a temporary array
Point2 [] z = new Point2 [x.length];

// find closest pair
return closestPair(x, y, z, 0, x.length - 1);
}

/** test program */
public static void main(String [] args)
{
// define the input stream to be the standard input stream
MyInputStream keyboard = new MyInputStream();

System.out.println("Enter number of points");
Point1 [] x = new Point1 [n];

for (int i = 0; i < n; i++)
{
System.out.println("Enter point " + (i + 1));
x[i] = new Point1(xcoord, ycoord, i + 1);
}

PointPair best = closestPair(x);
System.out.println("Closest points are " + best.a.id +
" and " + best.b.id);
System.out.println("Their distance is " + best.dist);
}
}
```

## Euclid

```//GCD, LCM, DIOPHANTINE AX+BY=GCD, CHINESE REMAINDER THEOREM
//This code can be changed, very easily, to handle longs
//For ACM-ICPC Programming Teams
//Kevin Lawler, kevin.lawler@cs.nyu.edu

import java.util.*;
import java.io.*;

public class Euclid
{

//GREATEST COMMON DIVISOR
public int gcd(int a, int b)
{
if(a < 0) a *= -1;
if(b < 0) b *= -1;

if (a < b) {int t = a; a = b; b = t;}

if (b == 0) return a;
else return(gcd(b, a % b));
}

//LEAST COMMON MULTIPLE, uses fact ab = gcd(a,b)*lcm(a,b)
public int lcm(int a, int b)
{
if (a == 0 || b == 0)
return 0;

int t = (a / gcd(a,b)) * b;
if (t<0) t *= -1;

return t;
}

//Solves DIOPHANTINE EQUATIONS of the form ax + by = gcd(a,b),
//including negative inputs. Returns String "x,y"

public String dio(int a, int b)
{ if(a == 0 && b == 0) return "0,0";
if(a == 0) return new String("0," + gcd(a,b) / b);
if(b == 0) return new String(gcd(a,b) / a + ",0");

int [] q = new int [99]; //we can do this because (long) size is capped
int [] r = new int [99]; //copy-paste
int [] x = new int [99];
int [] y = new int [99];
int [] n = new int [99];

if (a >= 0) n[0] = a;
else n[0] = -a;
if (b >=0) n[1] = b;
else n[1] = -b;

x[0] = 1; y[0] = 0;
x[1] = 0; y[1] = 1;

int i;
for(i=0; n[i+1] != 0; i++)
{ q[i+1] = n[i] / n[i+1];
r[i+1] = n[i] % n[i+1];
n[i+2] = r[i+1];
if(i > 0)
{ x[i+1] = x[i-1] - (q[i] * x[i]);
y[i+1] = y[i-1] - (q[i] * y[i]);
}
}

if(a < 0) x[i] *= -1;
if(b < 0) y[i] *= -1;

return new String(x[i] + "," + y[i]);
}

//CHINESE REMAINDER THEOREM: solves simultaneous linear congruences, i.e.,
//where n = v_0 mod m_0, n = v_1 mod m_1, etc.
//Handles positive, pairwise coprime mods. Will try, but might
//return -1, on anything else. vals.length obviously == mods.length.

public int crt(int [] vals, int [] mods)  //Relies on LCM & DIO
{
int n = 0;
int bigprod = 1;

for (int i=0; i < mods.length; i++)
bigprod = lcm(bigprod, mods[i]);

for (int i=0; i < vals.length; i++) // Handles negative vals
if (vals[i] < 0)
vals[i] = mods[i] + vals[i];

for (int i=0; i < mods.length; i++)
{ String [] str = dio(bigprod / mods[i], mods[i]).split(",");
int inverse = Integer.parseInt(str[0]);   //Long.parseLong(str[0]);
n += (bigprod/mods[i]) * inverse * vals[i];
n %= bigprod;
}

for (int i=0; i < mods.length; i++)
if (n % mods[i] != vals[i] % mods[i])
return -1;

return n;
}

public void doStuff() throws Exception
{
//PrintWriter fout = new PrintWriter(new FileWriter("euclid.out"));

Random r = new Random();

for (int k=0; k <= 20; k++)
{
int i = r.nextInt(101);
int j = r.nextInt(101);
System.out.println(i + "," + j + " gcd:" + gcd(i,j) + ", lcm:" + lcm(i,j) + ", dio:" + dio(i,j));
}

int [] v = {6, 5, 2};
int [] m = {10, 11, 13};
System.out.println(crt(v, m));

int [] u = {3, 2}; //no soln
int [] n = {9, 6};
System.out.println(crt(u, n));

int [] x = {2, 3, 2};
int [] y = {3, 5, 7};
System.out.println(crt(x, y));

//fin.close();
//fout.close();

}

public static void main (String [] args) throws Exception
{Euclid e = new Euclid(); e.doStuff();}

}
```

## Pre-Flow Algorithm

```// Pre-Flow algorithm implemented by Chien-I Liao
// Problem: Given a directed graph, a source node s and a sink node t
//          Find the maximum flow value from s to t
// Input: g is the adjacency matrix of the graph
//        s is the index of sourse node
//        t is the index of sink node
//        N in the number of nodes
// Return Value: The maximum flow value,
//               the flow matrix is recored in local matrix f[][]

import java.io.*;
import java.util.*;

class Main{
int flow(int [][] g, int s, int t, int N){
int [] h= new int[N];
int [] c= new int[N];
int [][] f= new int[N][N];
int [][] e= new int[N][N];
int [] ne= new int [N];
int i,j,tot,node,next,r;
int [] q = new int [N*N*10];
int st,ed;
for(i=0;i<N;i++){
h[i]=c[i]=ne[i]=0;
for(j=0;j<N;j++)
f[i][j]=0;
}
for(i=0;i<N;i++){
for(j=0;j<N;j++){
if(g[i][j]>0){
e[i][ne[i]]=j;
ne[i]++;
}
}
}
h[s]=N;
tot=0;
st=ed=0;
for(i=0;i<ne[s];i++){
tot+=g[s][e[s][i]];
if(c[e[s][i]]==0 && e[s][i]!=t){
q[ed]=e[s][i];
ed++;
}
c[e[s][i]]+=g[s][e[s][i]];
f[s][e[s][i]]+=g[s][e[s][i]];
f[e[s][i]][s]-=g[s][e[s][i]];
}
c[s]=-tot;
while(st!=ed){
node=q[st];
st++;
while(c[node]>0){
next=Integer.MAX_VALUE;
for(i=0;i<N;i++){
if(h[node]-h[i]==1 && g[node][i]>f[node][i]){
if(c[i]==0 && i!=s && i!=t){
q[ed]=i;
ed++;
}
r=g[node][i]-f[node][i];
if(c[node]<r)
r=c[node];
f[i][node]-=r;
f[node][i]+=r;
c[node]-=r;
c[i]+=r;
}
else if(h[node]<=h[i] && h[i]<next &&  node!=i)
next=h[i];
}
if(c[node]==0)
break;
else
h[node]=next+1;
}
}
return c[t];
}

void doStuff(){
Scanner in = new Scanner(System.in);
int V = in.nextInt();
int [][] g = new int [V][V];
for(int i=0;i<V;i++){
for(int j=0;j<V;j++){
g[i][j] = in.nextInt();
}
}
System.out.println(flow(g,0,V-1,V));
}
public static void main(String argv[]) throws Exception{
Main my = new Main();
my.doStuff();
}
}
```

## Convex Hull

```//CONVEX HULL
import java.util.*; //Vector, Stack, Iterator

private static Vector Graham(Vector points){
//Order points.size()*(2+log(points.size()) : logorithmic time
Stack hull = new Stack();
if (points.isEmpty()) return hull;
Iterator i;
Point anchor, next, top;
anchor = getAnchor(points);
QuickSort(anchor,points,0,points.size()-1); //n*lg(n) comparisons
int i=1; //points.get(0) = anchor
//remove colinear in anchor
while( i < points.size()-1 ){ //n comparisons
top = (Point)points.get(i);
next = (Point)points.get(i+1);
if ( angle( anchor , top , next ) == 0){
if ( top == farther(anchor,top,next) ){
points.remove(next);
}else{
points.remove(top);
}
}else{
i++;
}
}
if ( points.size() < 3 ){
return hull;
}
//find hull
i = points.iterator();
hull.push(anchor);
hull.push(i.next());
hull.push(i.next());
while (i.hasNext()){ //n comparisons
next = (Point)i.next();
top = (Point)hull.pop();
while ( angle((Point) hull.peek(), top, next ) >= 0 )
top = (Point)hull.pop();
//if top and next are colinear we take next, it is farther
hull.push(top);
hull.push(next);
}
return hull; //counterclockwise order
}

private static Vector Jarvis(Vector points){
//Order points.size()*hull.size() : best case - linear , worst case - quadratic
Vector hull = new Vector();
if (points.isEmpty()) return hull;
Point anchor, now, test;
anchor = getAnchor(points);
int turn;
do{
now = (Point)points.get(0);
for (int i=1;i<points.size();i++){ //n comparisons
test = (Point)points.get(i);
turn = angle(anchor,now,test);
if ( turn < 0 ){
now = test;
}else if ( turn == 0 ){
//take the farther
now = farther(anchor,now,test);
}
}
//now is the point with the lowest polar coordinate to anchor
anchor = now;
}while( !anchor.equals(hull.get(0)) ); //h loops
return hull; //counterclockwise order
}

private static int angle(Point a, Point b, Point c){
//Order 1 : constant time
//reorient as if a were the origin
Point p1 = new Point( b.x - a.x , b.y - a.y );
Point p2 = new Point( c.x - a.x , c.y - a.y );
//compute the cross product
int cp = p2.x*p1.y - p1.x*p2.y;
//positive, right turn; negative, left turn; zero, colinear
return cp; //signed area
}

private static Point getAnchor(Vector points){
//Order points.size() : linear time
//always the lowest, rightmost in a tie
Point anchor, tmp;
Iterator i = points.iterator();
anchor = (Point)i.next();
while ( i.hasNext() ){
tmp = (Point)i.next();
if ( anchor.getY() > tmp.getY() ){
anchor = tmp;
}else if ( anchor.getY() == tmp.getY()
&& anchor.getX() > tmp.getX() ){
anchor = tmp;
}
}
return anchor;
}

private static void QuickSort(Point anchor, Vector S, int first, int last){
// Order (last - first)*log(last-first) : logarithmic time
//recursively sorts S between index first and last (called by Graham)
//if anchor == getAnchor(S) then the result is that the points in S
//are in polar order with respect to anchor and with anchor first.
Point pivot;
int scanDown, scanUp;
if (first >= last){
return;
}
pivot = (Point)S.get(last);
if (pivot == anchor){
//pivot cannot be the anchor, so put anchor in front and get new pivot
pivot = (Point)S.set(first, S.set(last, S.get(first)));
}
scanUp = first;
scanDown = last-1;
while ( scanUp <= scanDown ){
while ( scanUp <= scanDown && angle(anchor,(Point)S.get(scanUp),pivot) <= 0 ){
scanUp++;
}
while ( scanUp <= scanDown && angle(anchor,(Point)S.get(scanDown),pivot) > 0 ){
scanDown--;
}
if (scanUp < scanDown){
//swap elements
S.set(scanDown, S.set(scanUp, S.get(scanDown)));
}
}
//insert the pivot
S.set(last, S.get(scanUp));
S.set(scanUp, pivot);
if ( scanUp-first < last-scanUp ){
//sort the smaller partition first (keeps stack small)
QuickSort(anchor,S,first,scanUp-1);
QuickSort(anchor,S,scanUp+1,last);
}else{
QuickSort(anchor,S,scanUp+1,last);
QuickSort(anchor,S,first,scanUp-1);
}
}

private static Point farther(Point anchor, Point a, Point b){
//Order 1 : constant time
//three colinear points
//returns a or b farther from anchor
double d1 = a.getX()-anchor.getX();
double d2 = b.getX()-anchor.getX();
if ( d1 < 0 ) d1 *= -1;
if ( d2 < 0 ) d2 *= -1;
if (d1 == d2){
d1 = a.getY()-anchor.getY();
d2 = b.getY()-anchor.getY();
if ( d1 < 0 ) d1 *= -1;
if ( d2 < 0 ) d2 *= -1;
}
if (d1 > d2)
return a;
return b;
}
```

## Graph

```//GRAPH ALGORITHMS:
//SINGLE SOURCE SHORTEST PATH WITH FEWEST HOPS, COMPONENT BREAKDOWN,
//MINIMUM SPANNING TREE, "PATH FROM X TO Y?"
//For ACM-ICPC Programming Teams
//Kevin Lawler, kevin.lawler@cs.nyu.edu

//All these work on doubly-scripted adjacency matrices
//of varying types. Graphs are directed unless otherwise noted.
//Undirected graphs should be symmetric along the diagonal (no laziness)

import java.io.*;
import java.util.*;

public class Graph
{

//Returns an int [] where each index contains
//the component# of the corresponding vertex.
//component#s start numbering from 0 (vertex 0).
//This easily extends to paths, connectedness, etc.
public int [] components(boolean [][] g)
{
int v = g.length;
int [] c = new int [v];
int curcom = -1;
for (int i=0; i < v; i++)
c[i] = -1;

for(int i=0; i < v; i++)
{ if (c[i] < 0)
{ curcom++;
ArrayList a = new ArrayList();
while(! a.isEmpty())
{ int guy = ((Integer) a.remove(0)).intValue();
c[guy] = curcom;
for (int j=0; j < v; j++)
if (g[guy][j] && c[j] < 0)
}
}
}
return c;
}

public boolean isPath(boolean[][] g, int x, int y)
{
int v = g.length;
boolean [] visited = new boolean[v];
visited[x] = true;
ArrayList a = new ArrayList();

while(! a.isEmpty())
{
int cur = ((Integer) a.remove(0)).intValue();
for (int i = 0; i < v; i++)
{ if(g[cur][i] && !visited[i])
{visited[i] = true;
}
}
if (visited[y]) return true;
}

return false;
}

//Returns ArrayList of v-1 Strings of edges "weight,v1,v2"
//Assumes: int graph is connected & undirected
//Assumes: unconnected edges have weight Integer.MAX_VALUE
public ArrayList minSpanTree(int [][] z)
{
int v = z.length;
int [][] g = new int[v][v];
for (int i=0; i < v; i++)
for (int j=0; j < v; j++)
g[i][j] = z[i][j];

boolean [][] dumb = new boolean [v][v];
boolean [] used = new boolean [v];

ArrayList w = new ArrayList();
ArrayList e = new ArrayList();

for(int i=0; i < v; i++)
for(int j=i+1; j < v; j++) //ASSUME SYMMETRIC

Collections.sort(w);

while(e.size() < v - 1)
{ int weight = ((Integer)w.remove(0)).intValue();
int m = 0;
while( g[m/v][m%v] != weight)
m++;
if (!isPath(dumb, m/v, m%v))
{
e.add(new String(weight + "," + (m/v) + "," + (m%v)));
dumb[m/v][m%v] = true;
dumb[m%v][m/v] = true;
}
g[m/v][m%v] = Integer.MAX_VALUE;
g[m%v][m/v] = Integer.MAX_VALUE;
}

return e;
}

//SINGLE SOURCE ALL DESTINATIONS DIRECTED SHORTEST PATH
//Returns an AL of Strings of size of set reachable from source
//Each string i (start 0) contains a smallest weighted path,
//of the fewest hops, of the form:
//"DISTANCEOFPATH,source,p1,p2,...,i"
//Will not terminate on negative cycles
public ArrayList shortestPaths(int [][] g, int source)
{
int v = g.length;
int [] best = new int [v];
int [] hops = new int [v];
int [] previous = new int [v];

for(int i =0; i < v; i++)
best[i] = Integer.MAX_VALUE;

best[source] = 0;
hops[source] = 0;
previous[source] = -1;

ArrayList q = new ArrayList();

while(! q.isEmpty())
{
int curnode = ((Integer)q.remove(0)).intValue();
for (int i=0; i < v; i++)
{
if(g[curnode][i] < Integer.MAX_VALUE)
if(best[curnode] + g[curnode][i] < best[i]
|| ( best[curnode] + g[curnode][i] == best[i]
&&   hops[curnode] + 1 < hops[i] ))
{
previous[i] = curnode;
best[i] = best[curnode] + g[curnode][i];
hops[i] = hops[curnode] + 1;
}
}
}

ArrayList paths = new ArrayList();

for (int i=0; i < v; i++)
if(best[i] < Integer.MAX_VALUE)
{ int t = i;
String str = (new Integer(best[i])).toString();
str = str + "," + (new Integer(source)).toString();

java.util.Stack s = new java.util.Stack(); //not Sahni Stacks...
while(previous[t] != -1)
{ s.push(new Integer(t));
t = previous[t];
}

while(!s.empty())
str = str + "," + s.pop().toString();
}

return paths;

}

public void doStuff() throws Exception
//PrintWriter fout = new PrintWriter( new FileWriter("graph.out"));

boolean [][] g = new boolean[15][15];

System.out.println(g.length); //g.length == 15;

g[0][1] = true;
g[0][2] = true;
g[3][4] = true;
g[4][5] = true;
g[5][6] = true;
g[5][7] = true;
g[8][9] = true;
g[10][10] = true;

int [] c = components(g);

for (int i=0; i < c.length; i++)
System.out.println("Vertex " + i + " in component " + c[i]);

System.out.println("Is path from 3 to 7?: " + isPath(g, 3, 7));
System.out.println("Is path from 7 to 8?: " + isPath(g, 7, 8));

int [][] h = new int [15][15];

for (int i=0; i < 15; i++)
for (int j=0; j < 15; j++)
h[i][j] = Integer.MAX_VALUE;

h[0][1] = 2;
h[1][2] = 101;
h[2][3] = 102;
h[3][4] = 103;
h[4][5] = 104;
h[5][6] = 5;
h[6][7] = 8;
h[7][8] = 105;
h[8][9] = 106;
h[9][10] = 107;
h[10][11] = 108;
h[11][12] = 109;
h[12][13] = 110;
h[13][14] = 111;
h[0][9] = 1;
h[1][9] = 1;
h[2][9] = 7;
h[3][9] = 4;
h[4][9] = 5;
h[5][9] = 6;
h[8][9] = 20;

ArrayList t = minSpanTree(h);

for (int i=0; i < t.size(); i++)
System.out.println(t.get(i));

System.out.println();

ArrayList w = shortestPaths(h, 0);

for (int i=0; i < w.size(); i++)
System.out.println(w.get(i));

//fin.close();
//fout.close();
}

public static void main (String [] args) throws Exception
{Graph f = new Graph(); f.doStuff();}

}
```

## Knapsack

```
//        0/1-KNAPSACK SOLVER
//Modification for 'unlimited' item 0/1-Knapsack:
//add d duplicates of each item i to the input,
//where d = (capacity / weight_i) - 1
//For ACM-ICPC Programming Teams
//Kevin Lawler, kevin.lawler@cs.nyu.edu

import java.io.*;
import java.util.*;

public class Knapsack
{

//Input is sack's capacity and AL of Strings of form "weight,profit"
//Returns a String of the form (items numbered from 0 on):
// "TOTALPROFIT,included_1, included_2,...,included_k"
public String solveSack(int capacity, ArrayList items)
{
int n = items.size();
int [] w = new int [n];
int [] p = new int [n];

for(int i=0; i < n; i++)
{ String[] str = ((String) items.get(i)).split(",");
w[i] = Integer.parseInt(str[0]);
p[i] = Integer.parseInt(str[1]);
}

int [][] table = new int[n][capacity + 1];  // PLUS 1 THROUGHOUT
for(int i= w[0]; i < capacity + 1; i++) //w[0] != 0, chum!!!
table[0][i] = p[0];

for (int i=1; i < n; i++)
for (int j=0; j < capacity + 1; j++)
{
if(j < w[i]) table[i][j] = table[i-1][j];
else
table[i][j] = Math.max(table[i-1][j], p[i] + table[i-1][j-w[i]]);
}

String soln = new String(new Integer(table[n-1][capacity]).toString());

java.util.Stack s = new java.util.Stack();

for (int i=n-1; i > 0; i--) //TRACEBACK
if(table[i-1][capacity] != table[i][capacity])
{ s.push(new Integer(i));
capacity -= w[i];
}

if (table[0][capacity] > 0)
s.push(new Integer(0));

while(!s.empty())
soln = soln + "," + ((Integer) s.pop()).toString();

return soln;
}

public void doStuff() throws Exception
//PrintWriter fout = new PrintWriter(new FileWriter("knapsack.out"));

ArrayList a = new ArrayList();

for (int i=0; i <= 24; i++)
System.out.println(i + ": " + solveSack(i, a));

//fin.close();
//fout.close();
}

public static void main (String [] args) throws Exception
{Knapsack k = new Knapsack(); k.doStuff(); }
}
```

## Hungarian Algorithm

```// Hungarian Algorithm to solve maximum matching problem
// Input:
// N = size of matrix
// S[N][N] = score matrix
// S[i][j] = score gained when pairing girl i with boy j
// Match[N] = store the result of pairing
// Output:
// return maximum total score
// The matching result will be stored in Match[N],
// i.e. Match[i]=j means you should pair girl i with boy j

import java.io.*;
import java.util.*;

class Main{
int Hungarian_Algorithm(int N, int [][] S, int [] Match)
{
int i,j;
int [][] g = new int [N][N];
int [] u = new int[N];
int [] v = new int[N];
int [] s = new int[N];
int [] t = new int[N];
int ns=0;
int nt=0;
int [] use1 = new int [N];
int [] use2 = new int [N];
int [] from1= new int [N];
int [] from2= new int [N];
int [] match1 = new int [N];
int [] match2 = new int [N];
int MAX,oldMAX;
int temp,pt1,pt2;
int MINover;
int total;

for(i=0;i<N;i++){						// precaculate u[i] and v[i]
u[i]=v[i]=0;
for(j=0;j<N;j++){
if(S[i][j]>u[i])
u[i]=S[i][j];
}
}
while(true){
for(i=0;i<N;i++){					// initialize match graph
for(j=0;j<N;j++){
if(S[i][j]==u[i]+v[j])
g[i][j]=1;
else
g[i][j]=0;
}
}
MAX=0;
for(i=0;i<N;i++){
use1[i]=use2[i]=0;
from1[i]=from2[i]=match1[i]=match2[i]=-1;
}
for(i=0;i<N;i++){					// Greedy Method for bipartite matching
for(j=0;j<N;j++){
if(use2[j]==1)
continue;
if(g[i][j]==1){
match1[i]=j;
match2[j]=i;
use1[i]=1;
use2[j]=1;
MAX++;
break;
}
}
}
while(true){							// Find augamenting path to improve matching
ns=0;
nt=0;
oldMAX=MAX;
for(i=0;i<N;i++){
from2[i]=-1;
if(use1[i]==0){
s[ns]=i;
ns++;
}
t[i]=0;
}
for(i=0;i<ns;i++){
for(j=0;j<N;j++){
if(g[s[i]][j]==1 && use2[j]==0){
pt1=s[i];pt2=j;use2[j]=1;
while(use1[pt1]==1){
temp=match1[pt1];
match1[pt1]=pt2;
match2[pt2]=pt1;
pt2=temp;
pt1=from2[temp];
}
use1[pt1]=1;
match1[pt1]=pt2;
match2[pt2]=pt1;
MAX++;
i=ns;
j=N;
break;
}
if(g[s[i]][j]==1 && from2[j]==-1){
t[nt]=j;
nt++;
from2[j]=s[i];
s[ns]=match2[j];
ns++;
}
}
if(i==ns)
break;
}
if(MAX==oldMAX)
break;
}
if(MAX==N){								// Maximum achieved
for(i=0;i<N;i++)
Match[i]=match1[i];
break;
}
for(i=0;i<N;i++){						// Find MINover to decrease total score
use1[i]=1;
use2[i]=0;
}
for(i=0;i<ns;i++)
use1[s[i]]=0;
for(i=0;i<nt;i++)
use2[t[i]]=1;
MINover=Integer.MAX_VALUE;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
if(use1[i]==0 && use2[j]==0 && u[i]+v[j]-S[i][j]<MINover)
MINover=u[i]+v[j]-S[i][j];
for(i=0;i<ns;i++)						// Update u[i] and v[i]
u[s[i]]-=MINover;
for(i=0;i<nt;i++)
v[t[i]]+=MINover;
total=0;
for(i=0;i<N;i++){
total+=u[i];
total+=v[i];
}
}
total=0;
for(i=0;i<N;i++){
total+=u[i];
total+=v[i];
}
}

void doStuff(){
Scanner in = new Scanner(System.in);
int i,j;
while(in.hasNextInt()){
int N=in.nextInt();
int [][] map = new int[N][N];
for(i=0;i<N;i++)
for(j=0;j<N;j++)
map[i][j]=in.nextInt();
int [] match = new int [N];
System.out.println("Score : " + Hungarian_Algorithm(N,map,match));
System.out.print("Pairs formed :");
for(i=0;i<N;i++)
System.out.print(" ("+i+","+match[i]+")");
System.out.println();
}
}
public static void main(String argv[]) throws Exception{
Main my = new Main();
my.doStuff();
}
}
```

## Merge Sort

```
/** iterative merge sort */

public class MergeSort
{
/** sort the elements a[0 : a.length - 1] using
* the merge sort method */
public static void mergeSort(Comparable [] a)
{
Comparable [] b = new Comparable [a.length];
int segmentSize = 1;
while (segmentSize < a.length)
{
mergePass(a, b, segmentSize); // merge from a to b
segmentSize += segmentSize;
mergePass(b, a, segmentSize); // merge from b to a
segmentSize += segmentSize;
}
}

/** merge adjacent segments from x to y */
public static void mergePass(Comparable [] x, Comparable [] y,
int segmentSize)
{
int i = 0;   // start of the next segment
while (i <= x.length - 2 * segmentSize)
{// merge two adjacent segments from x to y
merge(x, y, i, i + segmentSize - 1, i + 2 * segmentSize - 1);
i = i + 2 * segmentSize;
}

// fewer than 2 full segments remain
if (i + segmentSize < x.length)
// 2 segments remain
merge(x, y, i, i + segmentSize - 1, x.length - 1);
else
// 1 segment remains, copy to y
for (int j = i; j < x.length; j++)
y[j] = x[j];
}

/** merge two adjacent segments from c to d */
public static void merge(Comparable [] c, Comparable [] d,
int startOfFirst, int endOfFirst, int endOfSecond)
{
int first = startOfFirst,       // cursor for first segment
second = endOfFirst + 1,    // cursor for second
result = startOfFirst;      // cursor for result

// merge until one segment is done
while ((first <= endOfFirst) && (second <= endOfSecond))
if (c[first].compareTo(c[second]) <= 0)
d[result++] = c[first++];
else
d[result++] = c[second++];

// take care of leftovers
if (first > endOfFirst)
for (int q = second; q <= endOfSecond; q++)
d[result++] = c[q];
else
for (int q = first; q <= endOfFirst; q++)
d[result++] = c[q];
}

/** test program */
public static void main(String [] args)
{
Integer [] a = {new Integer(3),
new Integer(2), new Integer(4),
new Integer(1), new Integer(6),
new Integer(9), new Integer(8),
new Integer(7), new Integer(5),
new Integer(0)};

// output elements to be sorted
System.out.println("The elements are");
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
System.out.println();

// sort the elements
mergeSort(a);

// output in sorted order
System.out.println("The sorted order is");
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
System.out.println();
}
}
```

## Permutation

```//Implementation of 'Generating All Permutations in Lexicographical Order'
//Found in Knuth, fascicle 2b - http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz
//For ACM-ICPC Programming Teams
//Kevin Lawler, kevin.lawler@cs.nyu.edu

import java.io.*;
import java.util.*;

public class Perm
{

public void swap(ArrayList a, int x, int y)
{   Comparable temp = (Comparable) a.get(x);
a.set(x, a.get(y));
a.set(y, temp);
}

//note: this is a void, it makes "a" the next permutation lexicographically
public void nextperm (ArrayList a)
{
int n = a.size() - 1;

int j = n - 1;

while (j > -1 && ((Comparable) a.get(j)).compareTo((Comparable) a.get(j+1)) >= 0)
j--;

if (j == -1) //In reverse lexicographical order
{  for (int p=0; p <= (n / 2); p++)                //swap everything
swap(a, p, n-p);
return;
}

int l = n;  //The letter /ELL/ follows, not the numeral 1

while (l > 0 && ((Comparable) a.get(j)).compareTo((Comparable) a.get(l)) >= 0)
l--;

swap(a,j,l);

int k = j + 1; //j + one
l = n;
while(k < l)
{ swap(a, k, l);
k++;
l--;
}
}

public boolean inreverse(ArrayList a)
{int j = a.size() - 2;

while (j > -1 && ((Comparable) a.get(j)).compareTo((Comparable) a.get(j+1)) >= 0)
j--;

if (j < 0)
return true;
return false;
}

public int fac(int n)
{
if (n==1 || n == 0) return 1;
else return (n * fac(n-1));
}

public void doStuff() throws Exception //exhibits fooling around with nextperm
{
//PrintWriter fout = new PrintWriter(new FileWriter("perm.out"));

ArrayList a = new ArrayList();

for (int i=0; i < 4; i++)

System.out.println(a); //initial permutation

for (int i=0; i < fac(4) + 2; i++) // will show THREE after reverse order
{
nextperm(a);
System.out.println(a);
}

System.out.println("\n\n\n");
a.clear();

Collections.sort(a); //How To Sort an ArrayList

System.out.println(a);

while(!inreverse(a))
{ nextperm(a);
System.out.println(a);
}

System.out.println("And the wraparound...");

nextperm(a);
System.out.println(a);

//fin.close();
//fout.close();
}

public static void main (String [] args) throws Exception
{Perm c = new Perm(); c.doStuff();}

}
```