Date: 02/08/09     Keywords: no keywords

Let's say you have an array, which is sorted, and then some small number of the elements become corrupt, so the array is not sorted anymore. Is there some efficient way to sort it again that doesn't involve resorting the whole array? (You may not necessarily know which elements are corrupt)

Source: http://algorithms.livejournal.com/101636.html

Date: 02/08/09     Keywords: no keywords

Let's say you have an array, which is sorted, and then some small number of the elements become corrupt, so the array is not sorted anymore. Is there some efficient way to sort it again that doesn't involve resorting the whole array? (You may not necessarily know which elements are corrupt)

Source: https://algorithms.livejournal.com/101636.html

Date: 01/30/09     Keywords: html, java

I’m hoping someone here might know why this is not working as expected. I’m attempting to generate pseudo-random throws of dice in Java. In each round I generate 15 values from 1 to 6. From the player’s perspective, 5 dice are rolled, and any or all of them may be re-rolled one or twice. I implement this by taking the first roll from the first 5 values, whichever dice are not held on the first re-roll from the corresponding 6th to 10th values, and whichever are not held on the second re-roll from the 11th to 15th values.

I became suspicious that something was not right, and I believe I have shown that to be so. I’ve tried two sources of random numbers: one is the Random class built into Java (which is a linear congruential generator); the other is an implementation of the Mersenne twister. Both exhibit the same anomalies, so I presume the fault must lie in the routine that reduces the range to six integers, which is common to both.

package randomtest;
import net.goui.util.MTRandom;  // http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/JAVA/MTRandom.java
import java.util.Random;        // http://java.sun.com/j2se/1.4.2/docs/api/java/util/Random.html

public class Main {
    
    static class Roller {
        Random rng = new Random();           // alternate: new MTRandom()
        static int roll[] = new int[15];
        Roller() {
        }
        public void start() {for (int i=0; i<15; ++i) roll[i] = rng.nextInt(6) + 1;}
    }

    static Roller roller = new Roller();
    static int freq12[]  = {0, 0, 0, 0, 0, 0, 0};
    static int freq13[]  = {0, 0, 0, 0, 0, 0, 0};
    static int freq23[]  = {0, 0, 0, 0, 0, 0, 0};
    static int freq123[] = {0, 0, 0, 0, 0, 0, 0};
    
    public static void main(String[] args) {
    
        for (int n = 0; n < 10000000; ++n) {
            roller.start();
            for (int i=0; i<5; ++i) {
                int r1 = Roller.roll[i];
                int r2 = Roller.roll[i+5];
                int r3 = Roller.roll[i+10];
                if (r1 == r2) ++freq12[Roller.roll[r1]];
                if (r1 == r3) ++freq13[Roller.roll[r1]];
                if (r2 == r3) ++freq23[Roller.roll[r2]];
                if (r1 == r2 && r2 == r3) ++freq123[Roller.roll[r2]];
            }
            if ((n+1)%1000000 == 0) System.out.println("Trial " + (n+1) + ".");
        }

        System.out.println("Expected is: 1388889 / 1388889 / 1388889 / 231481.");
        for (int n=1;n<7;++n)
            System.out.println("Frequency of " + n + " repeating = "
                + freq12[n] + " / " + freq13[n] + " / " + freq23[n] + " / " + freq123[n] + ".");
    }

}

================================================================

Using java.util.Random:

Expected is: 1388889 / 1388889 / 1388889 / 231481.
Frequency of 1 repeating = 1388407 / 1479475 / 1293479 / 230274.
Frequency of 2 repeating = 1388173 / 1479752 / 1295680 / 231701.
Frequency of 3 repeating = 1388272 / 1482455 / 1295064 / 231626.
Frequency of 4 repeating = 1389251 / 1482245 / 1299079 / 232087.
Frequency of 5 repeating = 1386727 / 1205065 / 1574504 / 231813.
Frequency of 6 repeating = 1387655 / 1201628 / 1573153 / 230599.

Expected is: 1388889 / 1388889 / 1388889 / 231481.
Frequency of 1 repeating = 1388231 / 1481334 / 1294928 / 231923.
Frequency of 2 repeating = 1389308 / 1480868 / 1296429 / 230650.
Frequency of 3 repeating = 1388965 / 1479818 / 1295699 / 230441.
Frequency of 4 repeating = 1390373 / 1483708 / 1295996 / 231994.
Frequency of 5 repeating = 1388448 / 1203915 / 1574332 / 232041.
Frequency of 6 repeating = 1387842 / 1204130 / 1573698 / 230794.

Expected is: 1388889 / 1388889 / 1388889 / 231481.
Frequency of 1 repeating = 1389463 / 1480259 / 1295834 / 231346.
Frequency of 2 repeating = 1390002 / 1481980 / 1295481 / 231499.
Frequency of 3 repeating = 1391705 / 1482439 / 1296473 / 232614.
Frequency of 4 repeating = 1387626 / 1481225 / 1296746 / 231314.
Frequency of 5 repeating = 1388892 / 1203113 / 1572535 / 231855.
Frequency of 6 repeating = 1389320 / 1205755 / 1573967 / 231393.

================================================================

Using net.goui.util.MTRandom:

Expected is: 1388889 / 1388889 / 1388889 / 231481.
Frequency of 1 repeating = 1387599 / 1483090 / 1297874 / 231546.
Frequency of 2 repeating = 1388028 / 1479094 / 1295584 / 230952.
Frequency of 3 repeating = 1388372 / 1481956 / 1295757 / 231383.
Frequency of 4 repeating = 1388979 / 1481177 / 1296873 / 231376.
Frequency of 5 repeating = 1389075 / 1204569 / 1573831 / 231396.
Frequency of 6 repeating = 1389061 / 1204809 / 1574539 / 232224.

Expected is: 1388889 / 1388889 / 1388889 / 231481.
Frequency of 1 repeating = 1389284 / 1481200 / 1296447 / 231230.
Frequency of 2 repeating = 1391831 / 1480311 / 1295396 / 231499.
Frequency of 3 repeating = 1388017 / 1483176 / 1295311 / 231774.
Frequency of 4 repeating = 1390365 / 1481329 / 1295701 / 231424.
Frequency of 5 repeating = 1388466 / 1204211 / 1573249 / 231480.
Frequency of 6 repeating = 1387819 / 1204227 / 1571301 / 230896.

Expected is: 1388889 / 1388889 / 1388889 / 231481.
Frequency of 1 repeating = 1386641 / 1481585 / 1294466 / 231443.
Frequency of 2 repeating = 1388663 / 1481050 / 1295534 / 231235.
Frequency of 3 repeating = 1389067 / 1481547 / 1296505 / 232172.
Frequency of 4 repeating = 1390075 / 1482439 / 1298168 / 232068.
Frequency of 5 repeating = 1388224 / 1203076 / 1574220 / 230492.
Frequency of 6 repeating = 1389230 / 1203987 / 1575746 / 231630.

I previously tested the frequencies of each number — they are as expected; but there seems to be correlation between values in certain positions in the 15-number groups I’m generating, and I don’t know why, nor how to go about eliminating it.

Any insight and/or advice would be greatly appreciated.

Source: http://community.livejournal.com/algorithms/101403.html

Date: 01/30/09     Keywords: html, java

I’m hoping someone here might know why this is not working as expected. I’m attempting to generate pseudo-random throws of dice in Java. In each round I generate 15 values from 1 to 6. From the player’s perspective, 5 dice are rolled, and any or all of them may be re-rolled one or twice. I implement this by taking the first roll from the first 5 values, whichever dice are not held on the first re-roll from the corresponding 6th to 10th values, and whichever are not held on the second re-roll from the 11th to 15th values.

I became suspicious that something was not right, and I believe I have shown that to be so. I’ve tried two sources of random numbers: one is the Random class built into Java (which is a linear congruential generator); the other is an implementation of the Mersenne twister. Both exhibit the same anomalies, so I presume the fault must lie in the routine that reduces the range to six integers, which is common to both.

package randomtest;
import net.goui.util.MTRandom;  // http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/JAVA/MTRandom.java
import java.util.Random;        // http://java.sun.com/j2se/1.4.2/docs/api/java/util/Random.html

public class Main {
    
    static class Roller {
        Random rng = new Random();           // alternate: new MTRandom()
        static int roll[] = new int[15];
        Roller() {
        }
        public void start() {for (int i=0; i<15; ++i) roll[i] = rng.nextInt(6) + 1;}
    }

    static Roller roller = new Roller();
    static int freq12[]  = {0, 0, 0, 0, 0, 0, 0};
    static int freq13[]  = {0, 0, 0, 0, 0, 0, 0};
    static int freq23[]  = {0, 0, 0, 0, 0, 0, 0};
    static int freq123[] = {0, 0, 0, 0, 0, 0, 0};
    
    public static void main(String[] args) {
    
        for (int n = 0; n < 10000000; ++n) {
            roller.start();
            for (int i=0; i<5; ++i) {
                int r1 = Roller.roll[i];
                int r2 = Roller.roll[i+5];
                int r3 = Roller.roll[i+10];
                if (r1 == r2) ++freq12[Roller.roll[r1]];
                if (r1 == r3) ++freq13[Roller.roll[r1]];
                if (r2 == r3) ++freq23[Roller.roll[r2]];
                if (r1 == r2 && r2 == r3) ++freq123[Roller.roll[r2]];
            }
            if ((n+1)%1000000 == 0) System.out.println("Trial " + (n+1) + ".");
        }

        System.out.println("Expected is: 1388889 / 1388889 / 1388889 / 231481.");
        for (int n=1;n<7;++n)
            System.out.println("Frequency of " + n + " repeating = "
                + freq12[n] + " / " + freq13[n] + " / " + freq23[n] + " / " + freq123[n] + ".");
    }

}

================================================================

Using java.util.Random:

Expected is: 1388889 / 1388889 / 1388889 / 231481.
Frequency of 1 repeating = 1388407 / 1479475 / 1293479 / 230274.
Frequency of 2 repeating = 1388173 / 1479752 / 1295680 / 231701.
Frequency of 3 repeating = 1388272 / 1482455 / 1295064 / 231626.
Frequency of 4 repeating = 1389251 / 1482245 / 1299079 / 232087.
Frequency of 5 repeating = 1386727 / 1205065 / 1574504 / 231813.
Frequency of 6 repeating = 1387655 / 1201628 / 1573153 / 230599.

Expected is: 1388889 / 1388889 / 1388889 / 231481.
Frequency of 1 repeating = 1388231 / 1481334 / 1294928 / 231923.
Frequency of 2 repeating = 1389308 / 1480868 / 1296429 / 230650.
Frequency of 3 repeating = 1388965 / 1479818 / 1295699 / 230441.
Frequency of 4 repeating = 1390373 / 1483708 / 1295996 / 231994.
Frequency of 5 repeating = 1388448 / 1203915 / 1574332 / 232041.
Frequency of 6 repeating = 1387842 / 1204130 / 1573698 / 230794.

Expected is: 1388889 / 1388889 / 1388889 / 231481.
Frequency of 1 repeating = 1389463 / 1480259 / 1295834 / 231346.
Frequency of 2 repeating = 1390002 / 1481980 / 1295481 / 231499.
Frequency of 3 repeating = 1391705 / 1482439 / 1296473 / 232614.
Frequency of 4 repeating = 1387626 / 1481225 / 1296746 / 231314.
Frequency of 5 repeating = 1388892 / 1203113 / 1572535 / 231855.
Frequency of 6 repeating = 1389320 / 1205755 / 1573967 / 231393.

================================================================

Using net.goui.util.MTRandom:

Expected is: 1388889 / 1388889 / 1388889 / 231481.
Frequency of 1 repeating = 1387599 / 1483090 / 1297874 / 231546.
Frequency of 2 repeating = 1388028 / 1479094 / 1295584 / 230952.
Frequency of 3 repeating = 1388372 / 1481956 / 1295757 / 231383.
Frequency of 4 repeating = 1388979 / 1481177 / 1296873 / 231376.
Frequency of 5 repeating = 1389075 / 1204569 / 1573831 / 231396.
Frequency of 6 repeating = 1389061 / 1204809 / 1574539 / 232224.

Expected is: 1388889 / 1388889 / 1388889 / 231481.
Frequency of 1 repeating = 1389284 / 1481200 / 1296447 / 231230.
Frequency of 2 repeating = 1391831 / 1480311 / 1295396 / 231499.
Frequency of 3 repeating = 1388017 / 1483176 / 1295311 / 231774.
Frequency of 4 repeating = 1390365 / 1481329 / 1295701 / 231424.
Frequency of 5 repeating = 1388466 / 1204211 / 1573249 / 231480.
Frequency of 6 repeating = 1387819 / 1204227 / 1571301 / 230896.

Expected is: 1388889 / 1388889 / 1388889 / 231481.
Frequency of 1 repeating = 1386641 / 1481585 / 1294466 / 231443.
Frequency of 2 repeating = 1388663 / 1481050 / 1295534 / 231235.
Frequency of 3 repeating = 1389067 / 1481547 / 1296505 / 232172.
Frequency of 4 repeating = 1390075 / 1482439 / 1298168 / 232068.
Frequency of 5 repeating = 1388224 / 1203076 / 1574220 / 230492.
Frequency of 6 repeating = 1389230 / 1203987 / 1575746 / 231630.

I previously tested the frequencies of each number — they are as expected; but there seems to be correlation between values in certain positions in the 15-number groups I’m generating, and I don’t know why, nor how to go about eliminating it.

Any insight and/or advice would be greatly appreciated.

Source: http://algorithms.livejournal.com/101403.html

Date: 01/30/09     Keywords: html, java

I’m hoping someone here might know why this is not working as expected. I’m attempting to generate pseudo-random throws of dice in Java. In each round I generate 15 values from 1 to 6. From the player’s perspective, 5 dice are rolled, and any or all of them may be re-rolled one or twice. I implement this by taking the first roll from the first 5 values, whichever dice are not held on the first re-roll from the corresponding 6th to 10th values, and whichever are not held on the second re-roll from the 11th to 15th values.

I became suspicious that something was not right, and I believe I have shown that to be so. I’ve tried two sources of random numbers: one is the Random class built into Java (which is a linear congruential generator); the other is an implementation of the Mersenne twister. Both exhibit the same anomalies, so I presume the fault must lie in the routine that reduces the range to six integers, which is common to both.

package randomtest;
import net.goui.util.MTRandom;  // http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/JAVA/MTRandom.java
import java.util.Random;        // http://java.sun.com/j2se/1.4.2/docs/api/java/util/Random.html

public class Main {
    
    static class Roller {
        Random rng = new Random();           // alternate: new MTRandom()
        static int roll[] = new int[15];
        Roller() {
        }
        public void start() {for (int i=0; i<15; ++i) roll[i] = rng.nextInt(6) + 1;}
    }

    static Roller roller = new Roller();
    static int freq12[]  = {0, 0, 0, 0, 0, 0, 0};
    static int freq13[]  = {0, 0, 0, 0, 0, 0, 0};
    static int freq23[]  = {0, 0, 0, 0, 0, 0, 0};
    static int freq123[] = {0, 0, 0, 0, 0, 0, 0};
    
    public static void main(String[] args) {
    
        for (int n = 0; n < 10000000; ++n) {
            roller.start();
            for (int i=0; i<5; ++i) {
                int r1 = Roller.roll[i];
                int r2 = Roller.roll[i+5];
                int r3 = Roller.roll[i+10];
                if (r1 == r2) ++freq12[Roller.roll[r1]];
                if (r1 == r3) ++freq13[Roller.roll[r1]];
                if (r2 == r3) ++freq23[Roller.roll[r2]];
                if (r1 == r2 && r2 == r3) ++freq123[Roller.roll[r2]];
            }
            if ((n+1)%1000000 == 0) System.out.println("Trial " + (n+1) + ".");
        }

        System.out.println("Expected is: 1388889 / 1388889 / 1388889 / 231481.");
        for (int n=1;n<7;++n)
            System.out.println("Frequency of " + n + " repeating = "
                + freq12[n] + " / " + freq13[n] + " / " + freq23[n] + " / " + freq123[n] + ".");
    }

}

================================================================

Using java.util.Random:

Expected is: 1388889 / 1388889 / 1388889 / 231481.
Frequency of 1 repeating = 1388407 / 1479475 / 1293479 / 230274.
Frequency of 2 repeating = 1388173 / 1479752 / 1295680 / 231701.
Frequency of 3 repeating = 1388272 / 1482455 / 1295064 / 231626.
Frequency of 4 repeating = 1389251 / 1482245 / 1299079 / 232087.
Frequency of 5 repeating = 1386727 / 1205065 / 1574504 / 231813.
Frequency of 6 repeating = 1387655 / 1201628 / 1573153 / 230599.

Expected is: 1388889 / 1388889 / 1388889 / 231481.
Frequency of 1 repeating = 1388231 / 1481334 / 1294928 / 231923.
Frequency of 2 repeating = 1389308 / 1480868 / 1296429 / 230650.
Frequency of 3 repeating = 1388965 / 1479818 / 1295699 / 230441.
Frequency of 4 repeating = 1390373 / 1483708 / 1295996 / 231994.
Frequency of 5 repeating = 1388448 / 1203915 / 1574332 / 232041.
Frequency of 6 repeating = 1387842 / 1204130 / 1573698 / 230794.

Expected is: 1388889 / 1388889 / 1388889 / 231481.
Frequency of 1 repeating = 1389463 / 1480259 / 1295834 / 231346.
Frequency of 2 repeating = 1390002 / 1481980 / 1295481 / 231499.
Frequency of 3 repeating = 1391705 / 1482439 / 1296473 / 232614.
Frequency of 4 repeating = 1387626 / 1481225 / 1296746 / 231314.
Frequency of 5 repeating = 1388892 / 1203113 / 1572535 / 231855.
Frequency of 6 repeating = 1389320 / 1205755 / 1573967 / 231393.

================================================================

Using net.goui.util.MTRandom:

Expected is: 1388889 / 1388889 / 1388889 / 231481.
Frequency of 1 repeating = 1387599 / 1483090 / 1297874 / 231546.
Frequency of 2 repeating = 1388028 / 1479094 / 1295584 / 230952.
Frequency of 3 repeating = 1388372 / 1481956 / 1295757 / 231383.
Frequency of 4 repeating = 1388979 / 1481177 / 1296873 / 231376.
Frequency of 5 repeating = 1389075 / 1204569 / 1573831 / 231396.
Frequency of 6 repeating = 1389061 / 1204809 / 1574539 / 232224.

Expected is: 1388889 / 1388889 / 1388889 / 231481.
Frequency of 1 repeating = 1389284 / 1481200 / 1296447 / 231230.
Frequency of 2 repeating = 1391831 / 1480311 / 1295396 / 231499.
Frequency of 3 repeating = 1388017 / 1483176 / 1295311 / 231774.
Frequency of 4 repeating = 1390365 / 1481329 / 1295701 / 231424.
Frequency of 5 repeating = 1388466 / 1204211 / 1573249 / 231480.
Frequency of 6 repeating = 1387819 / 1204227 / 1571301 / 230896.

Expected is: 1388889 / 1388889 / 1388889 / 231481.
Frequency of 1 repeating = 1386641 / 1481585 / 1294466 / 231443.
Frequency of 2 repeating = 1388663 / 1481050 / 1295534 / 231235.
Frequency of 3 repeating = 1389067 / 1481547 / 1296505 / 232172.
Frequency of 4 repeating = 1390075 / 1482439 / 1298168 / 232068.
Frequency of 5 repeating = 1388224 / 1203076 / 1574220 / 230492.
Frequency of 6 repeating = 1389230 / 1203987 / 1575746 / 231630.

I previously tested the frequencies of each number — they are as expected; but there seems to be correlation between values in certain positions in the 15-number groups I’m generating, and I don’t know why, nor how to go about eliminating it.

Any insight and/or advice would be greatly appreciated.

Source: https://algorithms.livejournal.com/101403.html

Date: 01/13/09     Keywords: java

Some backstory for those willing to kindly help me interpret the below java code.

The class is Computer Graphics. What we did in the class was to basically reinvent the wheel; well, the java Graphics2D and Graphics3D API (except... badly) In our projects we managed to master (dun dun DUN!) 3D cubes and viewpoints, hidden surfaces, shaded surfaces and hidden line removal (ta da!) and an insane amount of inheritance. For this question we have to discuss how we might represent a class to represent a cylinder using flat surfaces (where Surface3D inherits from many simple classes: Drawing3D, Line3D to Point3D) to approximate to the figure. 

So far I have established that the paramaters used to specify the cylinder will be: center point, diameter, length and position. An ArrayList data structure will be appropriate for the cylinder and how I will do the class in English. I had a look at the sample answer and I found some java code which I've since been puzzling over because I'm not 100% sure what on earth it's doing.

double cylinder_length = 4; will allow us to specify the length of the cylinder, the length between the two symetrical circles on the axis
double oldx = 1; old x and y co-ordinates that can be saved so we do calculations on previous co-ordinates not the first co-ords.
double oldy = 0;
int n = 32; the set number of points I want around the circle, can be increased to create a smoother surface.

 for (int i = n; i>=0; i--){

double theta = (double)(((double)i/n)*Math.PI *2); 
double x = (double)Math.cos (theta); 
double y = (double)Math.sin (theta); 

Surface3D temp = new Surface3D(); this is us creating a new surface of type surface3D. The "base surface"
cylinder.addGItem(temp);  hierarchy crap that I don't understand but know to do
temp.addPoint(oldx,oldy,0); we are adding the old x, y (0 on the z-axis because the cylinder will start on the xy corords, we aren't rotating it around z) to the circle... making the circle?
temp.addPoint(x,y,0); now adding the next points x and y on the circle calculated above ^
temp.addPoint(x,y,cylinder_length); adding the points x and y identically to the second circle down the z-axis (toward us or away from us depending on the view point)
temp.addPoint(oldx,oldy,cylinder_length); adding the second point on the z-axis that reflects the old xy and y coords
oldx = x; sex new co-ordinates x and y to the old so the new calulations can be done on the new co-ords not the first
oldy = y;

}//for i

Surface3D cylinder_front = new Surface3D(); defining the front of the cylinder that will be able to be seen as a new surface
Surface3D cylinder_back = new Surface3D(); same to the back that should be invisible
cylinder.addGItem(cylinder_front); adding both front and back to cylinder
cylinder.addGItem(cylinder_back);

/*

for (int i = n; i>=0; i--){
 

double theta = (double)(((double)i/n)*Math.PI *2);
double x = (double)Math.cos (theta);
double y = (double)Math.sin (theta);

System.out.println("theta: " +theta + ", x:"+x+", y:"+y); just printing the values of theta, x and y

cylinder_front.addPoint(x,y,0); I have no idea why we're doing this.... connecting the back co-ords to the front, perhaps? to create the cylinder?
cylinder_back.addPoint(x,y,cylinder_length);

oldx = x;
oldy = y;

}//for i
 

Source: http://community.livejournal.com/algorithms/101364.html

Date: 01/13/09     Keywords: java

Some backstory for those willing to kindly help me interpret the below java code.

The class is Computer Graphics. What we did in the class was to basically reinvent the wheel; well, the java Graphics2D and Graphics3D API (except... badly) In our projects we managed to master (dun dun DUN!) 3D cubes and viewpoints, hidden surfaces, shaded surfaces and hidden line removal (ta da!) and an insane amount of inheritance. For this question we have to discuss how we might represent a class to represent a cylinder using flat surfaces (where Surface3D inherits from many simple classes: Drawing3D, Line3D to Point3D) to approximate to the figure. 

So far I have established that the paramaters used to specify the cylinder will be: center point, diameter, length and position. An ArrayList data structure will be appropriate for the cylinder and how I will do the class in English. I had a look at the sample answer and I found some java code which I've since been puzzling over because I'm not 100% sure what on earth it's doing.

double cylinder_length = 4; will allow us to specify the length of the cylinder, the length between the two symetrical circles on the axis
double oldx = 1; old x and y co-ordinates that can be saved so we do calculations on previous co-ordinates not the first co-ords.
double oldy = 0;
int n = 32; the set number of points I want around the circle, can be increased to create a smoother surface.

 for (int i = n; i>=0; i--){

double theta = (double)(((double)i/n)*Math.PI *2); 
double x = (double)Math.cos (theta); 
double y = (double)Math.sin (theta); 

Surface3D temp = new Surface3D(); this is us creating a new surface of type surface3D. The "base surface"
cylinder.addGItem(temp);  hierarchy crap that I don't understand but know to do
temp.addPoint(oldx,oldy,0); we are adding the old x, y (0 on the z-axis because the cylinder will start on the xy corords, we aren't rotating it around z) to the circle... making the circle?
temp.addPoint(x,y,0); now adding the next points x and y on the circle calculated above ^
temp.addPoint(x,y,cylinder_length); adding the points x and y identically to the second circle down the z-axis (toward us or away from us depending on the view point)
temp.addPoint(oldx,oldy,cylinder_length); adding the second point on the z-axis that reflects the old xy and y coords
oldx = x; sex new co-ordinates x and y to the old so the new calulations can be done on the new co-ords not the first
oldy = y;

}//for i

Surface3D cylinder_front = new Surface3D(); defining the front of the cylinder that will be able to be seen as a new surface
Surface3D cylinder_back = new Surface3D(); same to the back that should be invisible
cylinder.addGItem(cylinder_front); adding both front and back to cylinder
cylinder.addGItem(cylinder_back);

/*

for (int i = n; i>=0; i--){
 

double theta = (double)(((double)i/n)*Math.PI *2);
double x = (double)Math.cos (theta);
double y = (double)Math.sin (theta);

System.out.println("theta: " +theta + ", x:"+x+", y:"+y); just printing the values of theta, x and y

cylinder_front.addPoint(x,y,0); I have no idea why we're doing this.... connecting the back co-ords to the front, perhaps? to create the cylinder?
cylinder_back.addPoint(x,y,cylinder_length);

oldx = x;
oldy = y;

}//for i
 

Source: http://algorithms.livejournal.com/101364.html

Date: 01/13/09     Keywords: java

Some backstory for those willing to kindly help me interpret the below java code.

The class is Computer Graphics. What we did in the class was to basically reinvent the wheel; well, the java Graphics2D and Graphics3D API (except... badly) In our projects we managed to master (dun dun DUN!) 3D cubes and viewpoints, hidden surfaces, shaded surfaces and hidden line removal (ta da!) and an insane amount of inheritance. For this question we have to discuss how we might represent a class to represent a cylinder using flat surfaces (where Surface3D inherits from many simple classes: Drawing3D, Line3D to Point3D) to approximate to the figure. 

So far I have established that the paramaters used to specify the cylinder will be: center point, diameter, length and position. An ArrayList data structure will be appropriate for the cylinder and how I will do the class in English. I had a look at the sample answer and I found some java code which I've since been puzzling over because I'm not 100% sure what on earth it's doing.

double cylinder_length = 4; will allow us to specify the length of the cylinder, the length between the two symetrical circles on the axis
double oldx = 1; old x and y co-ordinates that can be saved so we do calculations on previous co-ordinates not the first co-ords.
double oldy = 0;
int n = 32; the set number of points I want around the circle, can be increased to create a smoother surface.

 for (int i = n; i>=0; i--){

double theta = (double)(((double)i/n)*Math.PI *2); 
double x = (double)Math.cos (theta); 
double y = (double)Math.sin (theta); 

Surface3D temp = new Surface3D(); this is us creating a new surface of type surface3D. The "base surface"
cylinder.addGItem(temp);  hierarchy crap that I don't understand but know to do
temp.addPoint(oldx,oldy,0); we are adding the old x, y (0 on the z-axis because the cylinder will start on the xy corords, we aren't rotating it around z) to the circle... making the circle?
temp.addPoint(x,y,0); now adding the next points x and y on the circle calculated above ^
temp.addPoint(x,y,cylinder_length); adding the points x and y identically to the second circle down the z-axis (toward us or away from us depending on the view point)
temp.addPoint(oldx,oldy,cylinder_length); adding the second point on the z-axis that reflects the old xy and y coords
oldx = x; sex new co-ordinates x and y to the old so the new calulations can be done on the new co-ords not the first
oldy = y;

}//for i

Surface3D cylinder_front = new Surface3D(); defining the front of the cylinder that will be able to be seen as a new surface
Surface3D cylinder_back = new Surface3D(); same to the back that should be invisible
cylinder.addGItem(cylinder_front); adding both front and back to cylinder
cylinder.addGItem(cylinder_back);

/*

for (int i = n; i>=0; i--){
 

double theta = (double)(((double)i/n)*Math.PI *2);
double x = (double)Math.cos (theta);
double y = (double)Math.sin (theta);

System.out.println("theta: " +theta + ", x:"+x+", y:"+y); just printing the values of theta, x and y

cylinder_front.addPoint(x,y,0); I have no idea why we're doing this.... connecting the back co-ords to the front, perhaps? to create the cylinder?
cylinder_back.addPoint(x,y,cylinder_length);

oldx = x;
oldy = y;

}//for i
 

Source: https://algorithms.livejournal.com/101364.html

Date: 12/07/08     Keywords: no keywords

j2ee.
j2ee_ua

Source: http://community.livejournal.com/algorithms/100837.html

Date: 12/07/08     Keywords: no keywords

j2ee.
j2ee_ua

Source: http://algorithms.livejournal.com/100837.html

Date: 12/07/08     Keywords: no keywords

j2ee.
j2ee_ua

Source: https://algorithms.livejournal.com/100837.html

Date: 10/28/08     Keywords: no keywords

A well-known algorithm for generating humorous texts using Markov chains is exist.
For example:
http://www.eblong.com/zarf/markov/
This algorithm is very simple and it is working only at word level.
What if I would like to have such algorithm, which works not only at word level, but also at sentence level.
It can be said that this algorithm remix words randomly. So then, I would like to remix sentences first, then words inside of each sentences.
At top level, statistical table for sentences will be build. At lower level: table for words.
But how to connect these two levels?
Probably, something already exist in theory, not just for humorous texts.
Thanks in advance for any comment about where to read more.

Source: http://community.livejournal.com/algorithms/100435.html

Date: 07/04/08     Keywords: no keywords

I am coloring a graph's nodes, based on a set of initial conditions and rules of the form "if colors of a node's neighbours are like this, then color of the node is that": so, a cellular automaton on the graph.
For simplicity, let us consider the graph to be acyclic and restrict the rules so that a node's color depends only on the colors of its child nodes.

What are the methods of exploring convergence and soundness of such a system of rules?

To put it easier, how to know, for a given system of rules, whether there exists a unique coloring satisfying them, and whether it is reachable by the following algorithm: "take any node, apply rules to it, repeat until convergence"?

Source: http://community.livejournal.com/algorithms/99911.html

Date: 07/04/08     Keywords: no keywords

I am coloring a graph's nodes, based on a set of initial conditions and rules of the form "if colors of a node's neighbours are like this, then color of the node is that": so, a cellular automaton on the graph.
For simplicity, let us consider the graph to be acyclic and restrict the rules so that a node's color depends only on the colors of its child nodes.

What are the methods of exploring convergence and soundness of such a system of rules?

To put it easier, how to know, for a given system of rules, whether there exists a unique coloring satisfying them, and whether it is reachable by the following algorithm: "take any node, apply rules to it, repeat until convergence"?

Source: http://algorithms.livejournal.com/99911.html

Date: 07/04/08     Keywords: no keywords

I am coloring a graph's nodes, based on a set of initial conditions and rules of the form "if colors of a node's neighbours are like this, then color of the node is that": so, a cellular automaton on the graph.
For simplicity, let us consider the graph to be acyclic and restrict the rules so that a node's color depends only on the colors of its child nodes.

What are the methods of exploring convergence and soundness of such a system of rules?

To put it easier, how to know, for a given system of rules, whether there exists a unique coloring satisfying them, and whether it is reachable by the following algorithm: "take any node, apply rules to it, repeat until convergence"?

Source: https://algorithms.livejournal.com/99911.html

Date: 05/23/08     Keywords: database, google

Almost ever since I got acquainted with category theory it seemed to me like a perfect tool for formalizing database queries and their properties, and, consequently, for building optimization frameworks.
I am considering this for my thesis, but I can't find any work about applying category theory to query optimization, and this frightens me a bit: looks like someone has long ago proved that this is impossible (why would it be?), and now noone even tries.

Could you give me pointers to some works on the topic? I've googled the hell out of the internet, I found some works on formalizing data models with CT but nothing on exactly optimization.

Source: http://community.livejournal.com/algorithms/99763.html

Date: 05/23/08     Keywords: database, google

Almost ever since I got acquainted with category theory it seemed to me like a perfect tool for formalizing database queries and their properties, and, consequently, for building optimization frameworks.
I am considering this for my thesis, but I can't find any work about applying category theory to query optimization, and this frightens me a bit: looks like someone has long ago proved that this is impossible (why would it be?), and now noone even tries.

Could you give me pointers to some works on the topic? I've googled the hell out of the internet, I found some works on formalizing data models with CT but nothing on exactly optimization.

Source: http://algorithms.livejournal.com/99763.html

Date: 05/23/08     Keywords: database, google

Almost ever since I got acquainted with category theory it seemed to me like a perfect tool for formalizing database queries and their properties, and, consequently, for building optimization frameworks.
I am considering this for my thesis, but I can't find any work about applying category theory to query optimization, and this frightens me a bit: looks like someone has long ago proved that this is impossible (why would it be?), and now noone even tries.

Could you give me pointers to some works on the topic? I've googled the hell out of the internet, I found some works on formalizing data models with CT but nothing on exactly optimization.

Source: https://algorithms.livejournal.com/99763.html

Date: 04/24/08     Keywords: no keywords

So, I'm once again writing a ray-tracer. So far the only objects it supports are planes and spheres. My intent to support only polygons. So, I'm curious. A low-polygon polygonal object is going to look, pretty.. well- polygony (if you know what I mean). My plan was to take the ray-polygon intersections and blur the collision normal, depth (somehow) and other information between adjacent polygons. I was planing on doing this using the dot-product between the collision-to-adjacent-polygons-far-edge vector and the collision-to-adjacent-polygons-near-edge vector as a bias for bluring. Is this how smoothing polygon-meshes is normally done? It seems like there'd be a better solution. What do you people think?

Source: http://community.livejournal.com/algorithms/99145.html

Date: 04/24/08     Keywords: no keywords

So, I'm once again writing a ray-tracer. So far the only objects it supports are planes and spheres. My intent to support only polygons. So, I'm curious. A low-polygon polygonal object is going to look, pretty.. well- polygony (if you know what I mean). My plan was to take the ray-polygon intersections and blur the collision normal, depth (somehow) and other information between adjacent polygons. I was planing on doing this using the dot-product between the collision-to-adjacent-polygons-far-edge vector and the collision-to-adjacent-polygons-near-edge vector as a bias for bluring. Is this how smoothing polygon-meshes is normally done? It seems like there'd be a better solution. What do you people think?

Source: http://algorithms.livejournal.com/99145.html