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

Date: 11/01/07     Keywords: software, asp, web, microsoft

Cracking GO By Feng - Hsiung Hsu
First Published October 2007 < http://www.spectrum.ieee.org/oct07/5552 >

Brute-force computation has eclipsed humans in chess, and it could soon do the same in this ancient Asian game

In 1957, Herbert A. Simon, a pioneer in artificial intelligence and later a Nobel Laureate in economics, predicted that in 10 years a computer would surpass humans in what was then regarded as the premier battleground of wits: the game of chess. Though the project took four times as long as he expected, in 1997 my colleagues and I at IBM fielded a computer called Deep Blue that defeated Garry Kasparov, the highest-rated chess player ever.
You might have thought that we had finally put the question to rest—but no. Many people argued that we had tailored our methods to solve just this one, narrowly defined problem, and that it could never handle the manifold tasks that serve as better touchstones for human intelligence. These critics pointed to weiqi, an ancient Chinese board game, better known in the West by the Japanese name of Go, whose combinatorial complexity was many orders of magnitude greater than that of chess. Noting that the best Go programs could not even handle the typical novice, they predicted that none would ever trouble the very best players.
Ten years later, the best Go programs still can't beat good human players. Nevertheless, I believe that a world-champion-level Go machine can be built within 10 years, based on the same method of intensive analysis—brute force, basically—that Deep Blue employed for chess. I've got more than a small personal stake in this quest. At my lab at Microsoft Research Asia, in Beijing, I am organizing a graduate student project to design the hardware and software elements that will test the ideas outlined here. If they prove out, then the way will be clear for a full-scale project to dethrone the best human players... (full story at the above website)

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

Date: 10/19/07     Keywords: google

Hi. I'm looking for an algorithm that can be used to translate a finite state machine directly into a regular expression without an intermediate step of a non-deterministic state machine. It's not necessary to get a direct explanation -- if you know of a good site for explaining said technique, would you please post it? There's a certain inefficiency in separating the wheat from the chafe in google searches on the matter.

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

Date: 10/18/07     Keywords: no keywords

Hello people,
Could you please point me to some methods of detecting peaks in 1-dimensional time-discrete signals?
I've been googling for "peak detection" but 99% of the info is about cardiography and chemistry and virtually noone seems to be describing their method...
I thought for a while about just computing sliding average and dispersion and thresholding the growth/fall of the average and dispersion but there's a lot to think about the window size, adaptivity etc.; would be really nice to have a look at what the science has already invented in this area.

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

Date: 10/18/07     Keywords: no keywords

hey I was wondering if anyone could help me with this question,

Write a pseudocode algorithm to print the numbers from 1 to 10, and then from 10 to 1, using exactly one loop. (Try using an if statement inside the loop.)

so far I have this...

for ( i = 1; i <= 20; i ++)
print i
if ( i > 10)
i--

I know it's probobly wrong... especially the if part.
any suggestions?

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

Date: 10/13/07     Keywords: programming, web

To those interested in programming, A.I., robotics, real-time systems.



RTSS 2007 - 3rd Students Design Competition
Dec 3, 2007
Tucson, Arizona, USA

CiberMouse@RTSS2007
http://www.ieeta.pt/~lau/web_ciberRTSS07/

A competition among autonomous robotic agents that have to rescue
three rally teams lost in the desert during the last Lisbon-Dakar
rally. Cars send a localization RF beacon that is used to guide the
rescue agents. No GPS info is available. Each agent can only rescue
one team. Which team will be rescued first in order to continue the
race asap?

Make your own team and participate in this challenge by programming
the rescue agent to reach the beacon and return. It is a great way to

test your skills in reactive real-time programming.

Technically, the rules are similar to last year rules (check the
website). The tools are all available so that you can develop and
test you robotic agent.

Stay tuned. We will keep you posted. If you already have an interest
on this, send us an email! (see our contacts on the webpage!). It is
the best way to be aware of the lastest news.

CyberMouse Org

PS: Could you please forward this call to anyone you know that
might be interested? Thanks a lot

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

Date: 09/23/07     Keywords: no keywords

I need to come up with an algorithm and general formula for using bilinear interpolation onto a regularly-spaced 2-D grid (x,y) from starting observations that are irregularly spaced. I know how to do bilinear interpolation when going from one regular grid to another, but my starting points are irregular, so I'm not sure how to alter it. The regular form I've used is:

f(x,y) = [f(x1,y1)/(x2-x1)(y2-y1)](x2-x)(y2-y) + [f(x2,y1)/(x2-x1)(y2-y1)](x-x1)(y2-y) + [f(x1,y2)/(x2-x1)(y2-y1)](x2-x)(y-y1) + [f(x2,y2)/(x2-x1)(y2-y1)](x-x1)(y-y1)

where (x1,y1) is in the lower-left, (x1,y2) is the upper-left, (x2,y1) lower-right, and (x2,y2) upper-right with (x,y) in the middle of that rectangle. The problem I have now is that my known points aren't on a rectangle. Suggestions? Thanks in advance!

(Crossposted to math_help.)

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

Date: 08/25/07     Keywords: no keywords

I am trying to follow this example (from the CLRS algorithm book, p.66)  # you don't really need the book anyway. 

T(2^m) = 2T(2 ^(m/2)) + m 
let S(m) = T (2^m)
=>  S(m) = 2T(m/2) + m   #  

I don't get how if S(m) = T(2^m) ,  then 2T(2^(m/2))  = 2S(m/2)   ? 

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

Date: 08/25/07     Keywords: no keywords

I think this is actually an easy question, but I'm feeling dumb, so I figured I'd ask here. (My excuse is that I'm really a statistician, trying to figure out an algorithm.)

What does an algorithm having linear convergence apply about the required number of iterations for convergence (within a fixed tolerance)?

In particular, I have an algorithm (the PCG algorithm, in case you're curious) whose convergence rate is linear in the square root of the condition number. If I could prove that the condition number was O(f(n)), would the number of iterations be O(sqrt(f(n)))? (My advisor thinks so; I can't get my head around it.)

Thanks in advance!

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

Date: 08/20/07     Keywords: rss, software

What pure computer science / software engineering blogs do you read? (Not general IT/industry blogs like Slashdot.)
Bonus points for links to an lj feed.

(my contributions)
bramcohen (the bittorrent guy)
thedailywtf_rss (going about things backwards)

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

Date: 08/18/07     Keywords: software

hello. new here. i don't think  that i've posted here before. but anyways, i've been having a persistent algorithm w/ my desktop. it's been going slow – so slow that it's nearly grinding. it almost does this on a schedule like about 8 or 8:30 a.m. every morning. i have to reboot it for a while to get it to pick up its speed. after i reboot for the day, it runs like new. it could be a ram-related problem, but whenever i go to shut it down, it tells me it's running another program. i never asked it to run another program (that i know of or recall).

to answer your questions: yes. it is a a part of a 4+ puter network. it has been so since it's been bought. the prototype is a dell, i believe. several yrs old.

question: is there anything that i could've scheduled it to do and forgot about that's been causing this retardation? is it a sign of age or a combination of varied factors? i haven't messed w/ this thing in quite a while and have a limited knowledge of computer use. it's been getting worse than usual lately.

lastly, if this is more of a tech-support-related question, then forgive it. i'll post it there later.

::PS:: i've also programmed this thing to stealth mode, though not totally since that requires software that i'm not willin' to purchase because i'm a tight-wad. fyi.

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

Date: 03/06/07     Keywords: no keywords

I’ve been trying to solve a problem, and it seems like the sort of problem someone has probably solved already. I would be grateful if anyone can point me in the right direction. This is a practical problem, but I’ll state it here in abstract form.

There are N “request queues.” Requests arrive at random. The rates of arrival are not known but may be assumed to vary slowly. At any particular time, the number of requests currently in each queue can be determined.

There are M “server pools.” Each pool has a maximum number of requests it can service simultaneously. The maximums differ from pool to pool and change over time. At any given time the maximum for each pool is known, and it may be assumed that these maximums change slowly compared to the rate at which requests are serviced.

The length of time required to service a request is random. It may be assumed to be independent of which request queue and server pool are involved.

There is an N by M matrix of non-negative numbers which represent the “worth” of servicing requests from each of the queues in each of the server pools. The value of servicing a request is equal to the worth of servicing the request in the server pool to which it is assigned depreciated according to the length of time the request has waited before being serviced. The depreciation is geometric, with a half-life which is the same for all requests in a queue but may be different for different queues. The worth values and half-lives are specified beforehand and do not change.

The problem is to determine an algorithm for assigning requests to server pools that will tend to maximize the total service value. When a server pool opening arises, there may be several non-empty queues for which the server pool has non-zero worth; it is not obvious how to tell which request is best to satisfy and which requests should be left for a later opening in a different server pool. The solution only needs to be “good,” not optimal; but it must avoid notably inefficient behavior in degenerate cases (such as a queue receiving no requests for an extended period of time, or a server pool having a maximum capacity of zero).

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

Date: 02/05/07     Keywords: java

I've been writing a class in Java similar to BigInteger.

I have been able to write arithmetic methods for add, subtract, and multiply using the same methods they teach grade school kids.

I am stuck on division (which honestly, I am lousy at doing myself with pencil and paper).

My integers can be huge, much larger than regular integer division within Java can handle. I am using a linked list to represent an integer. Each node in the list is a digit in the number.

I need a way to do division while only using one-to-a-few digits at a time. With my other methods I have used one digit from each number and a carry digit.
I am just baffled here because when I do long division I have to use the entire divisor, I can't break it up into pieces.


I'd love any help I can get. I need to have this finished soon though... like in about the next 4 hours.

Thanks!

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

Date: 01/30/07     Keywords: programming

Hi, I'm new to the community. I study Graphics Design (this is my first year) but we started with Computer Science in general. I have no idea about programming and I don't get pascal at all... Can anyone help me with writing a program?

I'm supposed to create a program using Delphi7 (=> console type). There's a .txt file with a list of 4 students, the number of their grades and the list of the grades. The program should count the average of the grades for each student and then sort the names by the average, lowest to highest.


Kowalski Andrzej
4
3 3.5 4 3.5

Nowak Siergiej
5
5 3 4.5 4 2.5

Elfryda Ciupaga
4
4 4 3 4.5

Gertruda Cebula
3
5 4 3.5


I tried to do it myself but I'm a poor programmer. Here's what I came up, but most of it is probably wrong.



program Project2;

{$APPTYPE CONSOLE}

uses
SysUtils;

const max = 20;

type

student = record end;
ave = real;
studentlist = array [1..max] of student;

var
f: text;
no, i : integer;
sum : real;
name : string;
u : studentlist;
N : 4;

begin
assign(f, 'data.txt');
reset(f);

for 1..N do
u[i];

readln (f; u) name;
readln(f, no);
sum : 0;

for i:= 1 to no do

begin
read(f, grade);
sum:= sum + grade;
end;

u.ave := sum/no;
{ TODO -oUser -cConsole Main : Insert code here }
end.


If somebody can help me I'd be really grateful. I promise to study more on the pascal in the future.

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

Date: 12/18/06     Keywords: no keywords

I have a problem with dvb-s2 scrambling sequense generating. I have try to simulate dvb-s2 scrambling sequence in matlab for n=0 (gold code), then convert it in to binary sequense. The sequence i have got is differ from real signal sequence (some bits are inverted). Could You please help me to find some information about dvb-s2 scrambler (exept ETSI EN 302 307).



PS.
If You can please send me original binary sequence (in binary file) not less than 70000 bits.

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

Date: 11/27/06     Keywords: no keywords

I'm trying to understand program verification using Hoare logic. I've looked through all the resources I could find online, but I'm still a bit lost as to how one actually goes about doing it.

I understand partial verification as: given some pseudocode and the input, prove that the pseudocode produces the desired output. Is that correct?

Now how does one do this? Represent every step of the code by a Hoare triple? If there are blocks within the program, is it all right to verify each block separately? To what extent of detail should you go (eg., element-wise assignment for arrays)? How about loops -- is it enough to show the final change of state after all the runs of the loop, or does it need to be done at each step?

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

Date: 11/19/06     Keywords: spam

So, I've turned off anonymous comments, turned on IP logging, deleted that last message and marked it as spam and banned them.

It's odd, because nothing is more likely to generate sympathy for the targets than this type of crap.

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

Date: 11/16/06     Keywords: no keywords

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

Date: 10/07/06     Keywords: no keywords

Was having coffee at a Starbucks last weekend with a friend, when we met an electrical engineer. We got talking and in the course of our conversation, he mentioned a problem that had been bugging him for more than a year now.

Imagine you've a 2-d (MxN) grid of resistors, all of which have the same value. You're only provided with a finite number (say k) of probing points that are located at the boundary. You can attach wires to them and measure some network stats like current, voltage etc., I've illustrated this with a diagram, with some of the probing points indicated by arrows.

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