Date: 03/04/09     Keywords: no keywords

what's the best asymptotic time complexity for a n-th order statistics algorithm on the immutable array of size N with memory consumption less then or equal to O(log N)? median of medians algorithm gives O(N) time complexity in the worst case, but I'm not sure about it's memory boundaries for the r/o array

UPD: anyway, it would be much interesting too for the case of the memory consumption less then or equal to O(sqrt N); or even O(K * N) where 0 < K << 1

Source: http://community.livejournal.com/algorithms/101906.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: http://community.livejournal.com/algorithms/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/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: 12/07/08     Keywords: no keywords

j2ee.
j2ee_ua

Source: http://community.livejournal.com/algorithms/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: 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: 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/01/08     Keywords: no keywords

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

Date: 03/30/08     Keywords: programming

Edit: Error was located and corrected. I love how programming can turn programmers temporarily blind :) I'll leave it here in the hope that perhaps others with the same problem can find it and think "OOOOooooOooh" before publically admitting to a community that they can't keep track of their pointers. :)

Thank you all for your help to my previous post! I've started to pick up C syntax really quickly since, and I've been integrating my two programs; the one with the functions to push, pop and create arrays, with the program lightning_rose suggested that I should write. So far my array seems to work and I'm sure that my push function is working, but when I ask it to print the contents of the stack, it prints 0. My aim isn't to iterate down the entire array, but to print that they've been pushed once they've been pushed.

Here is the buggy bit - where I expect the error is:

/* else, it will be an integer.*/
            else
            {
                int temp = atoi(argv[i]);
                push (temp);              
                //int i = 0;
              
                printf("Stack: %d", stack[top]);
              
                //printf("Integer: %d\n",atoi(argv[i]));
            }

/*
 * **** HISTORY *****
 *
 * Filename: test.c
 * Synopsis: test
 *
 * This is a simple program that will take input from the keyboard and then
 * print each line of input to screen.
 * Version 0.1 - Program simply returned a string of characters that had been
 * entered using printf.
 * version 0.2 - program differentiated between a string of characters and an
 * integer.
 * version 0.3 - Fixed a bug in the code that caused a 0 integer to be printed
 * after characters. Originally believed it to be a null byte, later discovered
 * that it was, in fact, a flaw in my if statements since I hadn't used else.
 * the use of else and else if in the testing area of the program are important
 * so that characters aren't printed as characters then passed down to be converted
 * into integers.
 * version 0.4 - program began to differentiate between characters, an operand
 * and the specific operators +, -, /, x and =. I was able to tell that the
 * differentiation had been made by asking the program to print out which each
 * was, for example: If I had entered: test 1 a + the program would output:
 * Integer: 1, Character: a, Symbol +.
 * version 0.5 - Array was defined from code that had been written in p3.c which was
 * written at an earlier date. This is where p3.c and test.c began to merge as
 * the final solution to p3.c with p3.c merging into test.c.
 */

 #include 
 #include 

 
 /*
 * define is used to make modification of each easier. It is also good for readability.
 * Characters A - D will be assigned values that the user wishes to store so that they
 * can later be used by, for example, 2 A +.
 */
 
 #define stack empty
 #define MemoryA A
 #define MemoryB B
 #define MemoryC C
 #define MemoryD D

/*
 * I need to define my array that will be used in a similar way to how I understand a
 * stack. The type of array that I will use is a fixed-length array so that the program
 * size will have a limit of 20 elements.
 *              See Page 112 - C In a Nutshell
 */

    int top = 0;                /*Pointer to keep track of where the top of the stack/array is*/
    //int maxstack = 20;  /*Allocates the maximum value of the stack-array */
    int stack[50];      /*sets the array stack equal of the maximum value of the stack*/

    void push(int x);

/*
 * The push function will push a new entry onto the stack at the stack pointer "top".
 * Once the entry (passed in as x) has been assigned as an element to the stack the
 * "stack pointer" top will then increment by one so that it is pointing to the next
 * free space.
 */
  void push(int x)
  {
        stack[top] = x;
        top ++;
  }
 


int main (int argc, char *argv[])
{
        int i;
        int j = 0;
        for (i = 1; i < argc; i++)
        {
                for(j=0; j < strlen(argv[i]); j++)
                {
                        /*This is a test to see if a the input is a
                         * alphabetical number. If it is, then the
                         * program will then check to see if it is
                         * specifically A, B, C or D.
                         */
                        if (isalpha(argv[i][j]))       
                        {
                                printf("Character: %s\n", argv[i]);
                        }      
                                       
                        /* These tests will test to see if input is an operand*/
                        else if (strcmp(argv[i], "+") == 0)
                        {
                                printf("Symbols: %s\n", argv[i]);
                        }
                        else if (strcmp(argv[i], "-") == 0)
                        {
                                printf("Symbols: %s\n", argv[i]);
                        }
                        else if (strcmp(argv[i], "/") == 0)
                        {
                                printf("Symbols: %s\n", argv[i]);
                        }
                        else if (strcmp(argv[i], "x") == 0){
                                printf("Symbols: %s\n", argv[i]);
                        }
                        /* else, it will be an integer.*/
                        else
                        {
                                int temp = atoi(argv[i]);
                                push (temp);                           
                                //int i = 0;
                               
                                printf("Stack: %d", stack[top]);
                               
                                //printf("Integer: %d\n",atoi(argv[i]));
                        }
               
                }
        }
}

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

Date: 03/28/08     Keywords: programming, html, java

I'm finding C difficult to understand. I'm working using two books: C in a Nutshell and I'm referencing with Comprehensive C (which is old but it was free.) The problem I'm trying to solve is to create a Reverse Polish Notation calculator. I'm using an array as a stack and the basic principle is:
for input (from command prompt) 2 1 +
Push 2 on the stack. Push 1 onto the stack. Meet operator, pop two and then push answer onto the stack.

But I'm having problems with my main method, particularly with the C syntax. This is my main method so far:

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

Date: 03/27/08     Keywords: virus, web

The link in the previous post is a Trojan website that will attempt to install a virus on your computer.

I repeat, DON'T CLICK ON THE LINK

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

Date: 02/01/08     Keywords: programming, java

Can anyone recommend a good beginners book on C?

In a few weeks time I will be using C for low level programming to solve problems. (Low level programming being the class.) C will be my second language, I already understand the basics of java objects and ADT's so preferably a book that defines clearly why C isn't object oriented...

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

Date: 01/20/08     Keywords: google

What work does there exist on the topic of minimizing non-'conventional' finite state automata? I mean everything but the commonest FSM's usually used for simple regular languages:
- Pushdown automata
- Automata with actions on transitions
- Automata with extra internal state
- ...

So, which variants of FSM's can be minimized?

I googled for something like 'minimizing automata' and found work on minimizing fuzzy automata (not that interesting for me), pushdown (http://www.labri.fr/perso/igw/Papers/igw-min-vis.pdf) and automata over infinite inputs. Also something named 'history dependent automata' (http://cometa.dimi.uniud.it/meetings/gioconople/pistore.pdf)

What else does there exist?

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

Date: 12/31/07     Keywords: software, technology, asp, security

We are excited to announce SOURCE Boston, a new computer security conference taking place in Boston, Massachusetts on March 12-14, 2008. SOURCE combines business, technology, and software development, and provides security experts an opportunity to share ideas, insights and opportunities.

SOURCE Boston will include the following:

* An intimate setting provides opportunities for networking, focused conversations, opportunities to converse with speakers and industry thought leaders
* Top keynote speakers, including Steven Levy, Dan Geer, and Richard Clarke.
* Special VIP evening reception
* First con to combine the edginess and creativity of hacking with the professionalism of the business environment.
* First computer security conference to have a track devoted to application security
* Combines industry and professional sessions with edgy fun approaches
* First L0pht reunion in ten years
* Business track will include talks from chief executives and other key members of the management community
* SOURCE Boston is organized by key industry thought leaders, including former founders of @stake, professionally published security research experts, and former NSA employees
* SOURCE Boston takes place the week before St Patrick’s Day – one of the most exciting times to be in Boston. Additionally, the Hyatt rate will be extended into the weekend so attendees can experience Boston’s St. Patrick’s Day celebrations.


Additional speakers include:
* Matthew Moynahan, CEO of Veracode
* James Mobley, CEO of Neohapis and former CEO of @stake
* Andy Jaquith, Yankee Group
* Cedric Blancher, EADS
* Robert Martin, MITRE
* Senior Members and Founders oof Cult of the Dead Cow
* Michael Rash, Author and Security Researcher

Cost:
$895 per person
$195 student/volunteer rate

We are also looking for volunteers to assist us during the con. Please email info@sourceboston.com for more information.

HTTP://WWW.SOURCEBOSTON.COM

Please go to http://www.regonline.com/Checkin.asp?EventId=167940 to purchase tickets.

See you in March!

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

Date: 12/22/07     Keywords: no keywords

Hi, im new here so first of all hi everyone!!!

Now, i am looking for a C to turing translator, this is a program that takes a piece of code in C as an entry and outputs the representation of a turing machine that does the same. This is theoretically possible but i haven't found any real world implementations, does anybody know of such a thing?

Thx :-)

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

Date: 11/14/07     Keywords: asp

Hello.

Computation is the process of state transition. An algorithm is a permutation of those states in such a way as to produce a correct output. 'Correct' means that what was put in agrees with what came out, and everyone's perceptions of those things.

"The fundamental problem of communication is that of reproducing at one point, either exactly or approximately, a message selected at another point." [Claude Shannon, "A Mathematical Theory of Communication"]

The algorithm is communication. That idea has always meant something to me.



So there's no use wasting words. I have an algorithm.

A while back, I had to solve the common maze-running problem for a course. The instructor gave the usual depth-first and breadth-first search algorithms, but instead of implementing one of those, I spent an extra week or so developing my own algorithm, based on what is, as far as I know, an entirely novel idea.

We have these assumptions:

1. It is appropriate to represent the maze as a two-dimensional grid;


2. Every place on the grid is either blocked (is a wall) or open (is a path);


3. Both the starting and the ending point are known;

STEP 1: Input maze grid; set UP = {(START_ROW, START_COL)}, DOWN = {(END_ROW, END, COL)}, and ALL = {all open spaces in grid};

STEP 2: while(UP intersection DOWN is empty AND new elements were added to UP or DOWN on the last iteration)
        repeat STEP 3 through STEP 5;

STEP 3:     DOWN = {all elements located by PingDwn( )} union DOWN;
            DOWN = DOWN union {all elements of ALL adjacent to an element of DOWN};

STEP 4:     UP = {all elements located by PingUp( )} union UP;
            UP = UP union {all elements of ALL adjacent to an element of UP};

STEP 5:     ALL = ALL complement (UP union DOWN);

STEP 6: if(the loop exited with no new elements added either to UP or DOWN)
          output NO SOLUTION;
          EXIT;
        else
          go to STEP 7;

STEP 7: PATH = {(START_ROW, START_COL), (END_ROW, END_COL)} union (UP intersection DOWN);
STEP 8: while(an element not in PATH could be pinged between any pair of points in PATH)
        repeat STEP 9;
STEP 9: for(each pair of elements p1, p2 in PATH)
            repeat STEP 3 through STEP 5, subsituting p1 for START and p2 for END;

STEP 10: output maze, description of the solution;
         EXIT;

It also serves to more completely describe the "ping" operation; we do so for PingDwn only; the operation for PingUp
is distinct only in that the directions are reversed, and '-' is substituted for '+'.

STEP 1: Input START := (START_ROW, START_COL);
        DOWN = {START};

STEP 2: while(elements could be added to DOWN)
        repeat STEP 3;
STEP 3: for(each element (i, j) in DOWN)
            if((i + 1, j) is CLEAR)
              add to DOWN;
            if((i, j + 1) is CLEAR)
              add to DOWN;
STEP 4: return the list DOWN;

solve(start, end, PathList){
	if(start == end){
		return NULL;	
	}

	else{
		mid = ping(start, end);  /*meet half-way*/
		if(NULL == mid){
			NO SOLUTION;    /*if no common point, no solution*/
			goto END;
		}

		insert(mid, PathList); /*else add mid-way to solution*/

		solve(start, mid, PathList);
		solve(mid, end, PathList);
	}
}

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

Date: 11/02/07     Keywords: technology

I pose the question: Is finding the ideal mate is an intractable problem or are we just not dedicating sufficient computational resources to the problem presently?

The ability to identify and assess every person in the world to determine which one is best suited for one's self is presently beyond the informational and computational power of any one person. Can present or near-future computational power be successfully harnessed to increase the success of lifelong intimate relationships?

Let a 'match' be a pairing of two individuals for the purpose of being lifelong romantic partners.
Let 'suitability' be a measure of how suitable person A is for person B in the event of A being matched with B.
Let an 'ideal match' be one where the measure of the sum of A suitable for B and B suitable for A is maximized.

The methods that dominated courtship over the last century require the relatively slow biological computational processes within our human bodies in general and brains in particular--we must meet and get to know other people. Even then, the accuracy of such processes may be questioned, as the time devoted to courting or 'assessing' any one particular 'match' may lead to an irrational 'escalation of commitment' and a premature, if not ill-advised coupling may ensue.

Over the past few decades, online interactions in general and online dating services in particular have promised a more streamlined approach to culling through the candidates to find those matches that may be more ideal, allowing people to focus on assessing those potentials that are most promising. eHarmony.com, for example, presents its members with extensive personality and interests inventory questions and claims to 'match' its members based upon 'algorithms'.

I have only recently began my study (read: 'use') of these online dating services however my initial assessment is that services like these and their future incarnations may be able to at least find some of us matches that are 'near ideal'.

However, I suspect that a related problem--that of maximizing the total 'ideal-ness sum' for all matches--is ultimately NP-hard. Clearly as we match more of us up, there will be a smaller pool from which to find 'near ideal' matches for the rest of us. In fact, some matches may have negative suitability, leading to the intuitive result that some of us just will not be matched, once the pool of remaining candidates becomes relatively small. I believe our friends in the Economics Department will find interest in this problem as well.

This leads me to four conclusions:
1. Whatever the methods of courtship available to us, whatever the technology employable, the result remains the same: find someone suitable before it is too late. The childhood exercise of 'musical chairs' clearly illustrates this point.
2. Technological assisted matching may provide some of us an edge in finding a 'near deal' match, or 'more ideal' match. However, we do not all share equal access to these resources, meaning that finding a suitable match is more likely for those of us with privilege.
3. Each 'match' commitment makes the pool of potentials smaller for the remaining unmatched individuals. This benefits no one but the pair involved in the match and likely harms the potential of some of the remaining unmatched individuals as the pair effectively removes themselves from the pool.
4. I understand why my mother gave up on men after several failed relationships. Those men remaining unmatched in their fifties are just not likely good matches for anyone. Clearly, if she had been more privileged as a young woman, she would have had a larger pool of suiters from which to choose, and would have had a better chance to find a 'near ideal' match.

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

Date: 11/02/07     Keywords: programming

Ok, so I obviously don't know how the computer works, or the internet. But I was just thinking, is it hard to make your own version of livejournal? Do I need to take a bunch of computer programming to do that? Cuz I was thinking of making my own, except it's not livejournal, more like a place for people to create their own profile page. And no it's not another facebook, myspace.. thing. But yeah, is it possible?

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