Date: 10/02/06     Keywords: html

C++ Simulator of a Post Machine can be downloaded at :
* http://alexvn.freeservers.com/s1/post-m.html
* http://sourceforge.net/projects/turing-machine/

Source of Post Machine description :
* V.A.Uspensky, "A Post Machine" (in Russian), Moscow, "Nauka", 1979.

The program simulates Deterministic and Nondeterministic Multitape Post
Machine (PM).

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

Date: 10/02/06     Keywords: html, google

In contrast to practical situation an ordinary Turing Machine never
fails.
An attempt to describe some Turing Machine that may fail was made.
Here is brief description of
* Turing Machine with faults, failures and recovery
http://arxiv.org/abs/cs/0410051
and
* its C++ Simulator (Beta version).
http://sourceforge.net/projects/turing-machine/
http://alexvn.freeservers.com/s1/turing-s.html
http://groups.google.ca/groups?hl=en&lr=&threadm=b4p5pt%2422nsld%241%40ID-79865.news.dfncis.de

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

Date: 10/02/06     Keywords: html

C++ Simulator of a Universal Turing Machine can be downloaded at :
* http://alexvn.freeservers.com/s1/utm.html
* http://sourceforge.net/projects/turing-machine/

The program simulates a Universal Turing Machine (UTM).

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

Date: 10/02/06     Keywords: html

C++ Simulator of a Turing Machine can be downloaded at :
* http://sourceforge.net/projects/turing-machine/
* http://alexvn.freeservers.com/s1/turing.html

The program simulates Deterministic and Nondeterministic Multitape
Turing Machine (TM).

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

Date: 09/03/06     Keywords: no keywords

First post of mine in this group. I am using Python here, but I understand some other procedural languages too.

The permutations of the elements of the array [1, 2, 3] are:
[[1, 2, 3], [2, 1, 3], [3, 1, 2], [1, 3, 2], [2, 3, 1], [3, 2, 1]]


To find the unique permutations I use this brute force way:

def uniqPermutations(items):
__cache = set()
__for el in xpermutations(items):
____tel = tuple(el)
____if tel not in cache:
______cache.add(tel)
______yield el

(Note: yield turns this function in a state-based generator. cache is a set data structure. A tuple is like a list, but it can be hashed and put into a Python set. xpermutations is another generator function that gives all the permutations.)


uniqPermutations([1,2,1]) returns:
[1, 2, 1] [2, 1, 1] [1, 1, 2]

I'd like an algorithm to find such unique permutations that doesn't require all that memory (And I'll need a similar algorithm to find the unique combinations too).

Bye and thank you.

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

Date: 08/19/06     Keywords: no keywords

Forgive me if this is elementary, I've been searching the tubes with no real luck for a while now.

I'm looking for the description of an algorithm to get all of the unique n-element combinations out of a given set.

So, given the set

[A, B, C, D, E]

and looking for combinations of threes, I'd want:

[
  [A, B, C],
  [A, B, D],
  [A, B, E],
  [A, C, D],
  [A, C, E],
  [A, D, E],
  [B, C, D],
  [B, C, E],
  [B, D, E],
  [C, D, E]
]

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

Date: 08/04/06     Keywords: no keywords

I'm studying a graph algorithm, and the notation used for efficiency is:
O(|V| + |E|)

where V is vertices, and E is edges.

I understand the big oh notation. The part that puzzles me is why the | | is necessary to indicate count.

I've noticed this | | notation used a lot to indicate the count of something. It seems to me it would be clear enough if I put:
O(V + E)
because V and E could not sensibly mean anything except the count of the vertices and edges.

So why is the convention to use | |?

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

Date: 08/02/06     Keywords: programming

Hello everyone. Longtime member-first time poster here. I was wondering if any of you could aid me in some research I'm doing while on my summer student placement. I am attempting to find a suitable algorithm that satifies the following requirements for use in a project:

The algorithm is to be used for returning a set of 0-1 decisions from a set of options.

There are an unlimited number of possible items (aka Interventions) to choose from, but for the purpose of aiding the search for a suitable algorithm an arbitrary limit of 1000 has been chosen.

The decision can only be a sequence of Yes-No/0-1 answers.

The may be some dependencies involved between items.

Can support up to 8 constraints, of differing designations i.e. Cost, Risk or Key Performance Indicators (KPIs) such as the metric of water leakage.

Only one variable can be minimised/maximised at any one time e.g. minimise risk for set cost or vice versa.

It certainly seems to be a binary integer programming problem. I have looked into the possibility of using a 0-1 Multidimensional Knapsack Problem (MKP) but have found little information on how to model one, or a decent example. I'm using ILOG OPL Dev Studio 4.2.

Thanks in advance.

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

Date: 07/14/06     Keywords: programming

(This question doesn't use any code, but I do think it's related to logic programming, so is included in this community.)

Say you have sets of things, so that each set contains different elements and each set has n things.
(1 2 3)
(a b c)
(x y z)

How do you determine how many possible ways there are to arrange the items in the set?
For instance, one way is:
( (1 a x) (2 b y) (3 c z))

As it turns out, I've counted the number of arrangements for 3 sets that each have 3 items, and there are 36 of them. This went against my first instinct that there would be 27. But now I understand why there are 36 though: imagine you had 3 sets of 2 items each. There are 6 solutions to that problem. There are 6 ways to permute (1 2 3). And 6 * 6 = 36.

I am wondering if there is a general formula for determining how many possibilities there are. For instance, if I have 4 sets of 6 items each, how many possible solutions are there? 7 sets of 5 elements each? And so on?

The answer has computing implications, in that the magnitude of the answer needs to be taken into consideration when planning out a program I'm writing. Thanks for any help!

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

Date: 07/07/06     Keywords: no keywords

Hi

I'm trying to do a DFT using this (VB, sorry not very good at C):

Private Sub Transform()
For n = 0 To 500
Hann(n) = (ChIN(n) - 127) * (1 - Cos(n * 3.1416 / 500)) 'Hann Window
Next n

For k = 1 To 500
r = 0
i = 0
For j = 1 To 500
r = r + Hann(j) * Sin(k * j / 380)
i = i + Hann(j) * Cos(k * j / 380)
Next j
ChIN(k) = 1 / 100 * Sqr(r * r + i * i)
Next k
End Suba

It is working on a microcontroller measuring vibration, taking 500 samples (1byte resolution) and I don't really know how to get rid of the DC (big peak at 0Hz on the frequency spectrum). I though of dividing the signal in half (ChIN(n) -127) but with some signals work and with others it doesn't. Not very stable.... :(

Anyone with experience in DFTs or FFTs?

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

Date: 07/05/06     Keywords: no keywords

"All Internet traffic is shaped and passed by mathematical Al-Gore-Rythms!"

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

Date: 07/05/06     Keywords: no keywords

I've been thinking of buying a good book on algorithms that would also serve as a reference in future. There are three books I know, of Cormen,Tanenbaum and Knuth. 

Is there any other book that is better, and which one should I choose among these ?




X-posted elsewhere

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

Date: 07/05/06     Keywords: no keywords

People used to use a temp variable to swap two variables, here is a trick that doesn't use an additional register:

#define SWAP(a,b) a^=b^=a^=b

But we have a problem, that method doesn't work with floating point variables... ok, every problem has a solution, try it:

#define SWAP2(a,b) a=a+b;b=a-b;a=a-b

Have a good coding!

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

Date: 06/26/06     Keywords: no keywords

Here's a neat image (under the lj-cut) generated by
for(y=0;y<480;y++)
for(x=0;x<640;x++)
put_pix(x,y,x^y);

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

Date: 06/24/06     Keywords: web

Here is some code from a uc berkeley lecture on insertion sort (available from the amazing berkeley webcasts, CS61B, "Sorting I" lecture ):
Presumably A is an existing array.

for (int i=1; i   int j;
   Object x = A[i];
   for (j=i-1; j>= 0; j-= 1) {
      if (A[j].compareTo (x) <= 0)  /* (1) */
         break;
      A[j+1] = A[j];
   }
   A[j+1] = x;
}


I have two questions (I'm not in the class, just watching the webcasts):
1)  In the code "A[j].compareTo(x)", I imagine that compareTo is some kind of callback which is supposed to already be implemented on this type of data. Is there a way I'm supposed to know how the callback is supposed to behave - I figure it returns 0 when the values are equal, but what about if a is greater than b? By the logic of this program, a.compareTo(b) returns something less than 0 if a is less than b. Is this behavior standard, or just a function of this program?

2) There is a comment that says "/*  (1)   */"
I don't understand what this means. Does anyone else?

Thanks.

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

Date: 06/24/06     Keywords: no keywords

I've noticed that a lot of algorithms say that something is in "non-decreasing order." Why don't these algorithms just say "increasing order." Is there a subtle difference between "increasing order" and "non-decreasing order"?

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

Date: 06/23/06     Keywords: no keywords

I was listening to a lecture by a professor today who said that some modern sorting algorithms aren't included in Knuth's seminal volume on Sorting and Searching. He didn't elaborate however, on exactly which algorithms aren't included. I've read (well, scanned at least) the sorting section of the book, and it looks like everything is there that I can think of. Ideas on what is not?

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

Date: 06/22/06     Keywords: no keywords

So recently I learned about heaps, that is, a tree structure in which the two children of a node are smaller than that particular node. Therefore when inserting an item into the heap, the maximum time is log<sub>2 n, where n is the number of nodes in the tree.

I was wondering why heaps are designed with two children per node, as opposed to say, three, or four, or five. It seems like the efficiency could then be improved because the log base would be higher. I'm sure there's a good reason why it's two children and not more. But I don't know what it is...</sub>

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

Date: 06/21/06     Keywords: web

I am wondering if anyone on this community knows of a good towers of hanoi tutorial. Here's the problem: I've read several of these tutorials. But to me, they all jump a lot of steps in the explanation. They will say something like: this is a recursive problem. The first thing is to move all of the disks but the first one onto a helper peg. The next step is to move the large peg onto the destination. Then we move the other pages onto the destination peg. It's that easy. And here is the simple algorithm for that: [blah blah blah].

The problem with this type of explanation to me is that it doesn't make it at all clear just how someone devised the algorithm, that is, how they determined the order of the source, destination, and auxiliary arguments for each recursive call. I'm a beginner and I really want someone to break down the problem for me into its smallest possible components, being very explicit about how each line of code is generated. So far, I just haven't seen a site that has done this (which I find really surprising and disappointing, I must say).

Note that I'm not asking for the solution to the problem. That's readily available. What I need to do is understand the process involved in developing the solution, because right now I'm just not getting it. So I would be extremely grateful to anyone who can point me to an exceptionally basic web site on the matter or, if you're extremely kind, try to explain how the solutions knew how to add the extra source, destination, and auxiliarly peg information.

I can show you the part of the problem I understand really well. It's this part, stripped of everything from the disk numbers:
function hanoi(n)
{
if (n == 1)
print(n);
else {
hanoi(n-1);
print(n);
hanoi(n-1);
}
}

But I'm really having trouble understanding how someone gets from the code I just wrote to the full solution...?

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

Date: 06/17/06     Keywords: no keywords

I've been reading texts list the recurrence relation for mergesort as Mergesort_n =2 * Mergesort_n-1 + n.

However, one of the things that these texts don't make clear is if this recurrence relation is true for all mergesorts...it seems to me that mergesort that copies arrays as opposed to in-place sorting would have a difference recurrence relation; specifically, it seems to me like it would be Mergesort_n =2 * Mergesort_n-1 +2 n. While this still resolves to Theta(n log n) efficiency, I'm surrprised that texts don't differentiate between in-place and copying. But I'm pretty new to recurrence analysis, so am eager to read any intelligent discussion on the matter...

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