Date: 06/02/05     Keywords: no keywords

So here is a problem.

Imagine you have a list of cities that a salesman wants to visit, each on a particual date or range of dates.
You know, Moscow: June 1-3; Tokio: June 17; New York: June 19-25, etc.
Also here is a list of transit station which the salesman can travel through: Paris, Singapour, Washington, whatever.

All these Cities can be I guess arranged in a simple graph bu what is important not every city is connected to another one, there is a network of "railroads" connecting those (I know, there is no railroad between Tokio and New York, but let it be :)). Of course those railroads have lengths (cost functionas) associated with those.

What the salesman needs is an optimal path that would make it possible to make o all those conferences or meetings by the dates specified (and i does not matter, what transition he is taking, but it should make sence in terms of lengths of the paths between those cities, that is, he should be choosing the paths hat would make "perfect timing" for him.

I am pretty sure this is a well known "classic" problem, but what is the "classic" name for the problem?
I would really appreciate if you could help me categorize the problem so that I would know where to start my search for an appropriate algorithm.

Thanks guys!

Source: http://www.livejournal.com/community/algorithms/55411.html

Date: 05/29/05     Keywords: browser

hi all,
As part of my final semester project I wrote an extension for firefox.
The project is about a firefox extension that adapts the homepage of the browser to the user.
Everyone who browses has habits they dont know. Each day as soon as people come to the office they check their mail. In the noon , say, they checkout slashdot and at night they update their blog. The heuristic applied should make appropriate decisions and find out the most appropriate page to load given the time of day.

Purpose it will serve:
It will make the browser more intelligent. The browser will be able to predict what site the user intends to browse at the given time.
Problem it will solve:
Presently the homepage is a static item in the browser. It doesnt change with the user let alone with his habits. It should basically answer to the question
"What site should I browse now?"

Though presently it is not intelligent as it is dreamt-to-be it serves as a starting to build upon. I wanted people to use it and provide feedbacks and report bugs.

You can download the firefox extension
here
After it downloads just drag and drop the .xpi file into the browser and it should install properly.
Thanks one and all and looking forward to your support.

Source: http://www.livejournal.com/community/algorithms/55130.html

Date: 05/28/05     Keywords: programming

Algogeeks is a discussion group for algorithms started over a year back. Any discussions related to programming and algorithms are welcome. Announcements about online programming contests are also posted.

Source: http://www.livejournal.com/community/algorithms/54927.html

Date: 05/17/05     Keywords: no keywords

I haven't come across any algorithms or methods of approaching this, though I guess it's pretty standard... so bear with my questions:

Given an ordered list of elements, what is the best way find a regular pattern within a given accuracy? Say, for instance, the list [2, 4, 3, 6, 7, 9, 11, 2]... the pattern is [prime, even, prime, even, prime, odd, prime, even]->[prime, even, prime, even, prime, even, prime, even] with 11/12 accuracy. (This is a constructed example; hope it is clear enoungh.) We're assuming, of course, that the attribute space is predefined and finite.

Source: http://www.livejournal.com/community/algorithms/54027.html

Date: 05/10/05     Keywords: no keywords

What is tail recursion vs. non-tail recursion?

What is recursive recursion vs. iterative recursion?

The simpler the terms the better. Sometimes I'm a little dense at understanding things.

Thanks.

Source: http://www.livejournal.com/community/algorithms/53343.html

Date: 04/21/05     Keywords: no keywords

Folks, it looks like the Linked List problem has been cracked. Check out the post by ringzero. Ofcourse, there are a few corrections thrown in by him and others. Read them too. If you find a flaw, please spoil the party asap.

Am introducing this as a new thread just in case you forget to revisit the original thread.

Source: http://www.livejournal.com/community/algorithms/52906.html

Date: 04/20/05     Keywords: no keywords

My boss and I were discussing a tricky one (tricky for us atleast):
You are given a simple one-way linked-list. You are assured that at most one loop exists. You have to identify the node at which the loop begins in the most efficient manner.

Example:
Node 1 --> Node 2--> Node 3 --> Node 4 --> Node 5

If node 5 points back to node 3, node 3 should be the answer.

But the problem is that you cannot add fields to the linked list (e.g., a 'visited' mark). You can't build a duplicate linked list to clone the original linked list as you traverse it, since you will double the memory requirement. And ofcourse, O(n^2) time solutions are absolutely unwelcome.

Solutions anyone? I'm still working on it. Will self-reply if a Eureka moment hits me. I have a feeling I am missing the solution by a whisker.

Source: http://www.livejournal.com/community/algorithms/52678.html

Date: 04/18/05     Keywords: no keywords

Hey. Just thought I'd poke my head up, and point out that the latest Dr. Dobb's Journal is all about the Algorithms. Some interesting things in there.

Source: http://www.livejournal.com/community/algorithms/52239.html

Date: 04/14/05     Keywords: no keywords

Please prove, using propositional logic, that horsies are pretty.

Source: http://www.livejournal.com/community/algorithms/52172.html

Date: 04/02/05     Keywords: no keywords

Anyone care to steer my thought process here? I swear, I am up to someting if I can just ...

Source: http://www.livejournal.com/community/algorithms/51543.html

Date: 03/30/05     Keywords: no keywords

I am trying to get a quick and dirty greedy method for solving the below job scheduling problem. I already developed a GA (genetic alg) version of it so want to compare between the 2 and probably can use the greedy one as a local optimization. Any one has any idea for the greedy algorithm ? Thanks,


This job (talk) scheduling is simpler than others, no different time length or penalties, each talk takes a fix-length time slot, users send in requests list, the only constraint is the schedule solution causes no conflict (i.e each user is able to attend all the talks he/she requested). Of course the goal is to minimze the number of different time slots.

Source: http://www.livejournal.com/community/algorithms/51301.html

Date: 03/26/05     Keywords: database

Hi all, I attempt to show an example of heuristic based algorithm such as Genetic Algorithm runs in polynomial time, my analysis is below. Please give comments as I feel that the way I write it is not very clear and possibly can contain technical errors.  Thank you in advance. 

  


    Approximation algorithms such as Genetic Algorithm takes polynomial time.  It is O(G) where G is the number of generation.
       
    The most important and time consuming part in each generation is probably the fitness evaluation since all chromosomes are tested against the database (tvn note: in this GA example the chrome fitness is tested against a DB).  The time for each individual chromosome to process an entire database of size D, where D is the number of column and R is the largest row, is at worst (max(D,R))^2 or O(max(D,R)), still polynomial time.  Of course, each chromosome will be tested against the database so it would be the population size * the time to process the entire database for each in
dividual.
        There are other operations in each generation such as the cross-over and mutation, but the run time for these two operations per chromosome is either constant or at most O(n) where n is the number of genes in a chromosome.
       

Source: http://www.livejournal.com/community/algorithms/50976.html

Date: 03/20/05     Keywords: no keywords

Hi, how do I analyse the run time of a GA progam ? MY program is based on 1) A: Chromosome population size, 2) B: the DB size which each chromosome tested against and 3) C: the size of each individual chromosome. So it's A*B*C or O(N^3) which is still polynomial O(N) where N is the max(A,B,C) ? Thanks ,

Source: http://www.livejournal.com/community/algorithms/50481.html

Date: 03/14/05     Keywords: no keywords

This approach may be well known, but it's new and neat to me. The fundamental idea is picking the appropriate rules for reducing two bits into one bit. Repeating that step leads to implementations for copying, xoring, comparing, and others.

"Appropriate rules" is one of the sixteen combinations of two two-state values. The code below uses the numeric encoding defined here: here (details).

Actually implementing memcpy this way is senseless. I've run some tests, and performance is comparable for small chunks of small blocks. But as either grow the stock impl runs away really fast.

Apologies for the grisly code. I have a much easier to read version but it's a handful of lines longer. All original, licensed under the GNU GPL.

quick sample:

void* oft_xor(void *dst, const void *src1, const void *src2, size_t len)
{
        return oft_emit(dst, src1, src2, len, op_xor);
}
void* oft_memcpy(void *dst, const void *src, size_t len)
{
        return oft_emit(dst, src, NULL, len, op_left);
}

#include 

/* All original, licensed under the GNU GPL. seth.schroeder@gmail.com. Part of the oft (one from two) library. */

#ifdef __cplusplus
 #define boolean bool
#else
 typedef int boolean;
 #ifndef TRUE_FALSE_DEFINED
  #define true 1
  #define false 0
 #endif
#endif


void* oft_xor(void *dst, const void *src1, const void *src2, size_t len);
void* oft_memcpy(void *dst, const void *src, size_t len);
void* oft_fill(void *dst, size_t len);


boolean oft_memeq(const void *b1, const void *b2, size_t len);
boolean oft_memneq(const void *b1, const void *b2, size_t len);
boolean oft_mem_oppose(const void *b1, const void *b2, size_t len);


static const int op_left = 10;
static const int op_always = 15;
static const int op_xor = 6;
static const int op_same = 9;

#define idx(a, b) \
        ((a) + 2 * (b))

#define ival(op, expr) \
        (op & 1 << (expr))

#define bval(op, expr) \
        (((op) & 1 << (expr)) != false)

#define advance(ptr) \
        if (ptr) ptr++

#define testval(ptr, val) \
        ((!ptr) ? false : ((*(const unsigned char*)ptr & val) != false))


void* oft_emit(void *dst, const void *s1, const void *s2, size_t bytes, int op)
{
        unsigned char *d = (unsigned char*)dst;
        const unsigned char *l = (const unsigned char *)s1;
        const unsigned char *r = (const unsigned char *)s2;

        while (bytes--)
        {
                if (ival(op, idx(testval(l, 0x01), testval(r, 0x01))))
                        *d |= 0x01; else *d &= 0xFE;
                if (ival(op, idx(testval(l, 0x02), testval(r, 0x02))))
                        *d |= 0x02; else *d &= 0xFD;
                if (ival(op, idx(testval(l, 0x04), testval(r, 0x04))))
                        *d |= 0x04; else *d &= 0xFB;
                if (ival(op, idx(testval(l, 0x08), testval(r, 0x08))))
                        *d |= 0x08; else *d &= 0xF7;
                if (ival(op, idx(testval(l, 0x10), testval(r, 0x10))))
                        *d |= 0x10; else *d &= 0xEF;
                if (ival(op, idx(testval(l, 0x20), testval(r, 0x20))))
                        *d |= 0x20; else *d &= 0xDF;
                if (ival(op, idx(testval(l, 0x40), testval(r, 0x40))))
                        *d |= 0x40; else *d &= 0xBF;
                if (ival(op, idx(testval(l, 0x80), testval(r, 0x80))))
                        *d |= 0x80; else *d &= 0x7F;

                advance(d);
                advance(l);
                advance(r);
        }

        return d;
}


boolean oft_match(const void *s1, const void *s2, size_t n, int op,
                  boolean pat)
{
        const unsigned char *l = (const unsigned char *)s1;
        const unsigned char *r = (const unsigned char *)s2;

        while(n--)
        {
                if (bval(op, idx(testval(l, 0x01), testval(r, 0x01))) == pat ||
                    bval(op, idx(testval(l, 0x02), testval(r, 0x02))) == pat ||
                    bval(op, idx(testval(l, 0x04), testval(r, 0x04))) == pat ||
                    bval(op, idx(testval(l, 0x08), testval(r, 0x08))) == pat ||
                    bval(op, idx(testval(l, 0x10), testval(r, 0x10))) == pat ||
                    bval(op, idx(testval(l, 0x20), testval(r, 0x20))) == pat ||
                    bval(op, idx(testval(l, 0x40), testval(r, 0x40))) == pat ||
                    bval(op, idx(testval(l, 0x80), testval(r, 0x80))) == pat)
                        return true;

                advance(l);
                advance(r);
        }
        return false;
}


boolean oft_match_any(const void *l, const void *r, size_t n, int op)
{
        return oft_match(l, r, n, op, true);
}


boolean oft_match_all(const void *l, const void *r, size_t n, int op)
{
        return !oft_match(l, r, n, op, false);
}


void* oft_xor(void *dst, const void *src1, const void *src2, size_t len)
{
        return oft_emit(dst, src1, src2, len, op_xor);
}


void* oft_memcpy(void *dst, const void *src, size_t len)
{
        return oft_emit(dst, src, NULL, len, op_left);
}


void* oft_fill(void *dst, size_t len)
{
        return oft_emit(dst, NULL, NULL, len, op_always);
}


boolean oft_memeq(const void *b1, const void *b2, size_t len)
{
        return oft_match_all(b1, b2, len, op_same);
}


boolean oft_memneq(const void *b1, const void *b2, size_t len)
{
        return oft_match_any(b1, b2, len, op_xor);
}


boolean oft_mem_oppose(const void *b1, const void *b2, size_t len)
{
        return oft_match_all(b1, b2, len, op_xor);
}

#	memcpy	oft	1 byte
1	0	1	
2	0	0	
4	0	1	
8	0	1	
16	1	1	
32	0	4	
64	1	7	
128	3	13	
256	5	27	
512	10	53	
#	memcpy	oft	2 bytes
1	0	1	
2	0	0	
4	0	1	
8	0	2	
16	0	4	
32	0	7	
64	1	12	
128	2	25	
256	4	49	
512	8	94	
#	memcpy	oft	4 bytes
1	0	0	
2	0	1	
4	0	2	
8	0	3	
16	0	6	
32	1	12	
64	1	23	
128	2	48	
256	4	95	
512	8	192	
#	memcpy	oft	8 bytes
1	1	0	
2	0	1	
4	0	3	
8	0	6	
16	0	12	
32	1	24	
64	1	86	
128	2	96	
256	4	192	
512	8	382	
#	memcpy	oft	16 bytes
1	0	2	
2	0	3	
4	0	6	
8	0	12	
16	0	24	
32	1	48	
64	1	94	
128	2	190	
256	4	379	
512	8	812	
#	memcpy	oft	32 bytes
1	0	3	
2	0	6	
4	0	12	
8	0	24	
16	0	48	
32	1	95	
64	1	190	
128	2	378	
256	5	754	
512	9	1512	
#	memcpy	oft	64 bytes
1	0	6	
2	0	12	
4	0	24	
8	0	48	
16	1	94	
32	1	194	
64	1	379	
128	3	760	
256	7	2465	
512	13	3101	
#	memcpy	oft	128 bytes
1	2	12	
2	1	23	
4	0	47	
8	0	95	
16	0	190	
32	1	378	
64	1	756	
128	3	1512	
256	6	3045	
512	11	6249	
#	memcpy	oft	256 bytes
1	2	23	
2	0	48	
4	0	95	
8	0	187	
16	0	377	
32	0	761	
64	2	1534	
128	3	3031	
256	6	6130	
512	15	15804	
#	memcpy	oft	512 bytes
1	3	47	
2	1	94	
4	0	187	
8	0	375	
16	1	1596	
32	3	1510	
64	2	3178	
128	4	6196	
256	10	12339	
512	19	25461	
#	memcpy	oft	1024 bytes
1	3	95	
2	0	190	
4	0	377	
8	0	753	
16	1	1504	
32	2	3116	
64	4	6209	
128	10	12258	
256	18	26003	
512	34	49812	
#	memcpy	oft	2048 bytes
1	3	189	
2	0	381	
4	1	871	
8	3	1500	
16	2	3121	
32	4	9837	
64	11	13289	
128	17	25521	
256	33	50316	
512	63	100882	
#	memcpy	oft	4096 bytes
1	5	373	
2	1	751	
4	1	1511	
8	2	3143	
16	6	6072	
32	8	12931	
64	18	24895	
128	34	50472	
256	64	100426	
512	124	205406	
#	memcpy	oft	8192 bytes
1	57	750	
2	1	1513	
4	2	3178	
8	7	6117	
16	8	12251	
32	18	25397	
64	33	50933	
128	64	101312	
256	126	201690	
512	247	407443	
#	memcpy	oft	16384 bytes
1	75	1506	
2	2	3032	
4	4	6869	
8	11	13132	
16	19	24837	
32	33	50750	
64	65	104674	
128	124	202902	
256	248	409276	
512	493	817020	
#	memcpy	oft	32768 bytes
1	118	3090	
2	6	6186	
4	15	12297	
8	22	25320	
16	37	51467	
32	67	101540	
64	126	202058	
128	349	412381	
256	522	821465	
512	979	1.638	

Source: http://www.livejournal.com/community/algorithms/49994.html

Date: 03/08/05     Keywords: microsoft

Someone mentioned a Microsoft Interview question and I went to that referenced site and saw this one.

There are 3 baskets. one of them have apples, one has oranges only and the other has mixture of apples and oranges. The labels on their baskets always lie. (i.e. if the label says oranges, you are sure that it doesn't have oranges only,it could be a mixture) The task is to pick one basket and pick only one fruit from it and then correctly label all the three baskets.


Anyone wants to try this one out as I gave up on it :)

I understand the problem is the labels are only either A="Apple" or O="Orange" , so either 2 A and 1 O or 1 O and 2 A . The task is after do what is allowed, able to correctly point out which is pure apple, which is pure orange and which is mixture.

Source: http://www.livejournal.com/community/algorithms/49661.html

Date: 03/04/05     Keywords: programming, web

I have been tinkering with Satisfiability solvers of late, but they all take input in CNF format and as my logic is not always of that form, I have a question: do you know of any algorithms to transform an arbitrary AND/OR tree into a set of CNF clauses? Can the result be shown to be minimal (cannot be done with fewer clauses nor fewer variables per clause), or is determining if a boolean logic relation between inputs and an output is minimal an NP-complete problem in itself?

On another note, it seems one can factorize in pseudopolynomial time by dynamic programming. Run the Sieve of Eratosthenes, but for each discovered prime, assign that prime to multiples of it that haven't been assigned to something else already. Then, starting at some number within the sieve, divide by the number assigned to it (which is one of its prime factors) and recurse until a prime is reached.
I don't know if this is common knowledge, though it seems simple in retrospect. It might be interesting as I didn't find any mention of it on the obvious web searches.

Source: http://www.livejournal.com/community/algorithms/49222.html

Date: 03/02/05     Keywords: google

Guys,

I'm studying for my PhD qualifier and my copy of Distributed Systems by Tanenbaum has gone missing. At present, it's my only source for information about the following algorithms. Can anyone here point me to resources that give an overview of...

• coterie-based distributed mutual exclusion
• quorum-voting protocol for replicated data objects
• Ricart and Agrawala algorithm for distributed mutual exclusion
• Distributed two-phase commit, esp. related to potential points of failure

Source: http://www.livejournal.com/community/algorithms/48899.html

Date: 03/02/05     Keywords: no keywords

I here by order change of how we describes numbers to better fit the way computers world.
0) When counting up, start at 0. 0 1 2 3 4 5 ... This convention also matches the current countdown. ... 5 4 3 2 1 0.
1) All real integers must be written in multiple of 3 digits. Add 0 in front to fill in the space. 1 == 001; 1,234 == 001,234
2) Banning of all numbering system that does not support zero. ie. Roman Numerals.

Source: http://www.livejournal.com/community/algorithms/48722.html

Date: 03/02/05     Keywords: no keywords

I was reading my Distributed algorithms book (by Nancy Lynch) last night and I got stuck in the 3rd chapter on the leader election problem in a synchronous network. I noticed that the LCR algorithm's communication-complexity is O(n^2) and the time-complexity is O(n). The time-complexity makes sense because you go through the ring and each node in the ring gets a chance to send out it UID to it's clockwise neighbor and wait for a reply from it's counter-clockwise neighbor and you do this for every node in the ring, since every node has a Unique Id, then there must be a largest value and the algorithm is O(n) to elect the leader. I am having trouble understanding why the algorithm has each node send out its UID (one at a time of course) until a leader is elected; making the communication complexity be O(n^2). Can't you just start in an arbitrary location in the ring and send out your uid, then when you receive a message (which should be the largest uid in the ring), record it and send out a "who's is this?" message around the ring and halt when the node with that uid annouces herself as leader? And if you want every node to know who the leader was so that each nodal process halts, the leader can send a "I am you leader" message around the ring. Now, this is O(3n) which is still O(n) and that's better than O(n^2) and also better than the O(n log n) algorithm (when n is large) they present in that chapter as well. Maybe someone can explain to me why LCR works the way it does? Am i missing something?

Source: http://www.livejournal.com/community/algorithms/48518.html

Date: 03/01/05     Keywords: java

Anyone knows where I can find a good explanation of transformation coding, especially the Karhunen-Loeve and the Walsh-Hadamard algorithms? Pseudo- or C/C++/Java code would be great :) My lecturer wants me to compare them and in the moment all I can see are Greek letters and parentheses --'

Source: http://www.livejournal.com/community/algorithms/48301.html