- Original Message -
From: "Gene" <[EMAIL PROTECTED]>
To: "Algorithm Geeks"
Sent: Sunday, November 20, 2005 11:58 PM
Subject: [algogeeks] Re: "Reverse Doubling List" is there an alias?
I didn't mean anything negative. You asked whether the idea was common
knowledge. I've seen it u
I didn't mean anything negative. You asked whether the idea was common
knowledge. I've seen it used as a homework problem e.g. after the
introduction of Fibonacci heaps. Last time for sure was 1984. Usually
homework problems fall in the domain of "common knowedge."
Googling "linked list of arr
- Original Message -
From: "Gene" <[EMAIL PROTECTED]>
To: "Algorithm Geeks"
Sent: Sunday, November 20, 2005 1:42 PM
Subject: [algogeeks] Re: "Reverse Doubling List" is there an alias?
It would make a nice homework question in an undergraduate data
structures course, and there might
It would make a nice homework question in an undergraduate data
structures course, and there might be some applications where it
performs marginally better than the standard approach, which is a
single pointer to a single array. To grow the array, allocate new
memory twice as large as the existin
Yes. You missed something. Keep in mind that the odds of success for
the commoner hoping to get the dowry, is only 37%, even with the best
strategy. Also, clearly the Sultan can defeat this strategy very easily
if he wishes, just by sending in the daughter with the highest dowry,
first.
The idea
Gaijinco,
Your method is correct except for one small bug. You will call permute
method only for values 0,1 and 2 (since array length is 3). So the
condition should be if (n<2) and not if (n<3).
Correct code :
void permute(int n){
for(int i=0; i<5; ++i){
A[n]=i+1;
I am using a abstract data type, which is a linked list of arrays, each
one twice as big as the next. Does anyone know if this data-type
pre-exists under a different name than "reverse doubling list"?
I've discovered that this data type has the property O(1) growth in the
average and worst case,
Hi,
I'm not ignoring other points because i and j go through 0..n-1, so
every pair of points is considered.
I've recently found out that O(n^2) solultions exists :))
The idea is not to recalculate k from scratch for each i, j pair, but
use results from previous pair.
bestArea = 0;
for (int i = 0;
And how do you guys find the points on the convex hull.
For the whole task I am thinking for algo like this :
select 3 random points from the set and make "Starting triangle".
For every one of the remining points do the following :
If the point is inside the "Starting triangle" remove it from
With STL a simpler solution is possible:
#include
#include
using namespace std;
int main()
{
int a[] = {1, 2, 3, 4, 5};
do
{
for (int i = 0; i < 5; ++i)
cout << a[i] << " ";
cout << endl;
}while(next_permuta
No. It's illegal in any language. You're missing a closing brace.
Celebrity problem - as far as I know it states that every body knows
the celebrity and the celebrity knows nobody. With this additional
constraint O(n) solution is obvious. :)
I believe that the problem about numbers is O(nlogn).
Ok but why are you searching the point exactly in this points:P[i],
P[(i+1)%n], P[(i+2)%n], P[(i+3)%n] .. P[(j-1)%n],
How do you ignore the other points
Can any body do me a favour? I can't understand the Sultan's dowry problem. If the maximum number can be any of them with equal probability, then we have only 1/n chance which is definite to choose the maximum one. Did I miss something?
Hi Gaijinco,
What is it that you want to do? Generate permutations? Or print a table
of values 111, 112, etc.. (because that's what your first program is
doing)?
If the former is what you want to do:
#include
inline void swap( int &a, int &b ) { int c = a; a = b; b =c; }
void permute(int values[
15 matches
Mail list logo
