代做COMP 3022: Algorithm Engineering Lab 5. Generating Random Data 2025代写Java程序
- 首页 >> Database作业COMP 3022: Algorithm Engineering
Lab 5. Generating Random Data
2025
Generation of a random double
Generate a random double number in [0, 1)
1 double rand_d () {
2 return rand () / ( RAND_MAX + 1.0);
3 }
Generate a nonnegative inteer strictly smaller than bound.
1 int rand_range (int min , int max ) {
2 return rand () % ( max - min + 1) + min ;
3 }
4 int rand_bound (int bound ) {
5 return rand_range (0 , bound );
6 }
Generation of a random permutation
All permutations of [1..n] have the same probability to be generated.
The algorithm runs in O(n) time.
1 void random_perm (int perm [] , int n ) {
2 for ( i = 0; i < n ; i ++)
3 perm [ i ] = i +1; /* initialization */
4 for ( i = n - 1; i > 0; i - -) {
5 j = rand_bound ( i ); /* random index
6 int tmp = perm [ i ];
7 perm [ i ] = perm [ j ];
8 perm [ j ] = tmp ;
9 }
10 }
Random samples: k integers from [1..n]
1 void sample (int s [] , int n , int k ) {
2 for ( i = 0; i < k ; i ++)
3 s [ i ] = rand_bound ( n ) + 1;
4 }
What if duplicates not allowed? sampling with replacement
To generate a random permutation of length n, then take the first k values.
Better solutions.
1 void sample (int s [] , int n , int k ) {
2 for ( i = 0; i < k ; i ++)
3 s [ i ] = rand_bound ( n ) + 1;
4 }
What if duplicates not allowed? sampling with replacement
To generate a random permutation of length n, then take the first k values.
Better solutions.
Random samples: ordered reals
Generate k distinct random reals in [0, 1) in sorted order.
1 pick a value m1 in the range [0, 1);
2 pick a value m2 in the range [0,m1);
3 pick a value m3 in the range [0,m2);
4 ...
1 static int i = k ; // counter
2 static double m =1.; // top of range
3
4 double ordered_sample_reals () {
5 m = m * exp ( ln ( rand_d ()) / i - -);
6 return m ;
7 }
Nonuniform. random generator
1 if ( p > rand_d ())
2 generate ( A );
3 else
4 generate ( B );
Bernoulli process ()
Events occur independently.
The outcome of each event: A (with probability p) and B (with probability 1−p)
Example: coin toss; Erdős–Rényi graphs ()
1 X = - ln ( rand_d ()) / lambda ;
Poisson process ()
Events occur independently and at a constant average rate: λ events per s/m/h
Example: MTR arriving at a stop; packets arriving at a router
To generate the waiting time X for the next event:
Tasks
Download random.c.
Test the random_perm function and record the result.
Finish function sample_d.
Add code in the main function to test sample and sample_d.
Optional tasks
Conduct experiments for n > 5. I used a simple trick in the main function, which cannot work for n = 6. You need to .
Conduct experiments on generating ordered real numbers.