Re: [algogeeks] Random number

[석문기]

Box-muller method is the good solution without a lot of computation overhead

2011/8/8 Puneet Gautam 

> You may be right..we cant remove collisions in O(1) time...
>
> But hey, hash table is still an effective way..
>
>
> On 8/8/11, Puneet Gautam  wrote:
> > Hey avoiding collisions using hash table can be real easy :
> > eg:
> > if 192 is the no generated let it hash to say index 7 of hash
> > table...so when it is again generated, it hashes to the same 7th index
> > of hash table, but we have a non zero value already present at that
> > index , 192 so we can reject this generated no. and proceed to the
> > next one..
> >
> > Whereas in an array , avoiding collision is a really hectic way...u
> > need to scan all the previously generated no.s for duplicacy...well
> > that aint gonna run in O(1) time..
> >
> > So implementing hash table reduces that overhead and runs it in O(1)
> > time..(it just has to check one if condition)with a bigger
> > constant.
> >
> > And moreover, we may even dont want an ordered sequence...just put the
> > generated no.s in hash table as soon as they are generated...dats it..
> >
> > then afterwards display that hash table..
> >
> > Did u get me...?
> >
> >
> > On 8/7/11, Gaurav Menghani  wrote:
> >> We can have a sorted sequence and display them in random order, but
> >> that is the same problem. How do we display them in random order? We
> >> need to have a sequence of random indices, that is the same problem as
> >> having random numbers, isn't it.
> >>
> >> Moreover, I don't think collisions can be avoided in less than O(n).
> >> We can have an efficient hash-table, but I am not sure how it can be
> >> done in O(1) or better.
> >>
> >> On Sat, Aug 6, 2011 at 12:37 PM, Puneet Gautam  >
> >> wrote:
> >>> I rhink to avoid collisions altogether we should generate an ordered
> >>> sequence , in a dec. or inc. order and
> >>> display them randomly, i mean:
> >>>
> >>> Let say a[10] contains all the random no.s , map all the 10 indexes to
> >>> a hash table and then display the arrays with the hashed index...
> >>>
> >>> I think it may work...
> >>>
> >>> what say..?
> >>>
> >>>
> >>> On 8/5/11, Gaurav Menghani  wrote:
>  1. Get a good seed.
>  2. Increase the degree of the polynomial.
> 
>  This is no fixed algorithm, if you find that more than T steps have
>  passed and a new number has not been generated, you can always change
>  the polynomial. And, please remember it is a 'pseudo-random number
>  generator'. You can read the theory about PRNGs and LFSRs, all of them
>  repeat.
> 
>  On Fri, Aug 5, 2011 at 7:14 PM, payel roy 
> wrote:
> > How do you guarantee termination of your algorithm if duplication
> > occurs
> > ??
> >
> > On 5 August 2011 18:25, Gaurav Menghani 
> > wrote:
> >>
> >> You might want to read the theory on Pseudo-Random Number Generators
> >> [0] and Linear Feedback Shift Register [1]
> >>
> >> The basic way of generating a random number is taking up a
> >> polynomial,
> >> f(x) = ax^n + bx^(n-1) + .. + yx + z, and finding f(i + seed) % N,
> >> where i is the ith random number you want, and seed can be anything
> >> random available, for example, you can find the current millisecond
> >> using time.h functions.
> >>
> >> A simple implementation, without the time thing is below:
> >>
> >> #include
> >> using namespace std;
> >>
> >> int poly[10],pn,N,M;
> >> int get(int seed)
> >> {
> >>int t=0;
> >>for(int i=0;i >>{
> >>int res=poly[i];
> >>for(int j=1;j<=(i+1);j++) { res = (res*seed);
> >> if(res>=N)
> >> res%=N; }
> >>t+=res;
> >>if(t>=N) t%=N;
> >>}
> >>t=(t+seed);
> >>t%=N;
> >>return t;
> >> }
> >>
> >> void setup_prng()
> >> {
> >>pn=5;
> >>poly[0]=2; poly[1]=3; poly[2]=5; poly[3]=7; poly[4]=11;
> >>N=200; M=100;
> >> }
> >>
> >> int main()
> >> {
> >>setup_prng();
> >>for(int i=1;i<=M;i++)
> >>cout< >>return 0;
> >> }
> >>
> >> Whenever there is a collision, you can increment the value passed to
> >> the random number generator and continue. However, I am not sure how
> >> to check for collisions in O(1) space.
> >>
> >> [0] http://en.wikipedia.org/wiki/Pseudorandom_number_generator
> >> [1] http://en.wikipedia.org/wiki/Linear_feedback_shift_register
> >>
> >> On Fri, Aug 5, 2011 at 5:19 PM, payel roy 
> >> wrote:
> >> > Given a range 0-N, generate 'M' random numbers from the range
> >> > without
> >> > any
> >> > duplication. The space complexity is O(1).
> >> >
> >> > --
> >> > You received this message because you are subscribed to the Google
> 

Re: [algogeeks] puzzle

[석문기]

The problem is finding the subspaces that satisfy two conditions in the 6*6
total space?

2011/7/28 vetri 

> given a 6x6 matrix with all the elements as either 1 or -1.
> find the number of ways the elements can b arranged such that
>
> 1.the product of all elements of all columns is 1
> 2.the product of all elements of all rows is 1
>
> can u pls post the answer if u no...
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Easy question

[석문기]

Qestion is not for genius;;;

Easy question .

 

From: algogeeks@googlegroups.com [mailto:algoge...@googlegroups.com] On
Behalf Of Aminooo~
Sent: Tuesday, June 02, 2009 6:30 PM
To: alireza gorjipoor
Subject: 

 


Dear Friends,

 

A question for the genius, the one who solve the problem will write the
name in the attached file.

IF; 2+3=10
 7+2=63
 6+5=66
 8+4=96
THEN;

  9+7=???


The answer is the password to open the file attached 

  

  

Best Regards 

  Aminooo.com





--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---



successor.xlsx
Description: application/vnd.openxmlformats-officedocument.spreadsheetml.sheet