Tag: running

Worst-case expected running time for Randomized Permutation Algorithm

I have an algorithm which, when given a positive integer N, generates a permutation of the first N integers (from 1 to N) using a method called randInt(x,y). The method randInt(x,y) will generate a random integer between the numbers x and y, provided they are positive integers and y >= x.

The algorithm is given by the following pseudo-code:

1.  if (N <= 0) { 2.     return null 3.  } else { 4.     A := new int[] w/ size N and all cells initialized to 0 5.     a[0] := randInt(1,N) 6.     for (i := 1 to length(A)-1) do  7.        boolean rInA := True 8.        while (rInA) { 9.           rInA := False  10.          int r := randInt(1,N) 11.          for (j := 0 to (i-1)) do  12.             if (r = A[j]) { 13.                rInA := True 14.             } 15.          }    16.       } 17.       A[i] := r 18.    } 19. } 20. return A

My understanding of the algorithm is as follows:

The outermost for-loop will run N-1 times and for each of those iterations a random number is generated and then compared to all the previous cells of A that have been visited in previous iterations. If any of the those cells contain that randomly generated number then that number cannot be used and a new number is randomly generated (in the next iteration of that nested while-loop). This new randomly generated number is then, like before, compared to all the previously visited cells in A to check for duplication. This continues until randInt(x,y) generates a random number that is not already in the first i cells of A.

This leads me to believe that the Worst-case expected running time of the algorithm is something like: $ \sum_{i=1}^{N-1}(\alpha i)$

Now the $ \alpha$ here represents the effect the while-loop has on the running time and is the point of uncertainty for me. I know that in the first iteration of the outermost for loop its unlikely that randInt will generate the one integer that A already contains (1/N I believe) so that inner-most for-loop is likely to only execute once. However, by the last iteration (of outer-most for-loop) the probability that randInt generates one of the N-1 integers already in A is $ \frac{N-1}{N}$ so because of the while-loop its likely that the inner-most for-loop for that iteration (of the outer-most for-loop) will execute more like n times.

How can I use the probability introduced into the algorithm by randInt to calculate the algorithms run-time?

rolling around running numbers

I’m numbering generated files with two digits 00-99 and I want to retain the last 50. The algorithm should tell me the number of the current file that I’m about to save and which of the previous files to remove.

If I scale it down to a toy version with one digits, here’s how I want it to behave.

  1. As long as there are fewer than 5 files, we can just add files. This is represented in the first block below.
  2. Once there are 5 previous files, the oldest one should be deleted. This is trivial as long as we haven’t reached the maximum number, here 9. This is represented in the second block below.
  3. Once the highest numbers has been reached, the numbering should roll around, and here is where things get tricky. See the third block below.
__prev__    __curr__   __drop__   <no files>     0         null 0              1         null 0 1            2         null 0 1 2          3         null 0 1 2 3        4         null  0 1 2 3 4      5          0  1 2 3 4 5      6          1 2 3 4 5 6      7          2 3 4 5 6 7      8          3 4 5 6 7 8      9          4  5 6 7 8 9      0          5 6 7 8 9 0      1          6 7 8 9 0 1      2          7 8 9 0 1 2      3          8 9 0 1 2 3      4          9

Some pseudocode to illustrate my progress:

if length(prev) < 5    curr = length(prev)    drop = null  else  if 9 not in prev    curr = (1+max(prev)) mod(10)    drop = curr-5  if 9 in prev

… and this is where I’m stuck. I’ve experimented with subtracting 10 from each element in prev.

I’m sure it’s trivial and that It’ll hit me when I least expect it. I also have a nagging feeling I’ll find an expression that generalizes both cases (with and without max in prev).

Can I install Metasploitable 2 on a machine other than the one running Kali Linux?

I use a kind of POTATO LAPTOP with highly limited resources so when I installed Kali Linux I simply ruled out the idea of using a Virtual Machine (running an OS on an OS is resource-heavy, isnt it?).
Now, I want to install Metaspoitable 2:
1. Can I install it without a VM? (Probably I could not and maybe I should not)
2. Since I can not install Kali on my laptop in a VM (i don’t want many kali, that’s again a waste of space and resources), is there a VM that could be installed in a installed (not in VM) Kali LInux system? (like running metasploitable in VM along with Kali Linux as the base OS) – Maybe that does not make sense at all 🙁

Tips for running 3 Faction Combat

I am running a game of 5th Edition Dungeons and Dragons.

I am going to run a climactic battle that has three factions- one will be the players, one will be their main antagonist, and the third will be an additional antagonist that is also trying to beat the main villain. I am wondering if there are any best practices when designing and running such an encounter. I don’t want to slow down what should be an epic and climactic battle by having a large number of villain turns, and it may feel like if one set of bad guys attacks the other set, that there is a lack of interaction with the players. Does anyone have experience running multi-faction fights? What were the takeaways that you learned?

Strategies for effectively running a temporary online game

Other questions have done a good job of outlining where to find online players and some of the tools available for ongoing virtual games (Roll20, Fantasy Grounds, etc). Many of those tools have a cost associated with them and a large time commitment to configure a custom, homebrew game.

Occasionally, circumstances prevent us from gathering in the way we prefer. The 2020 COVID-19 pandemic is a good example. During those times, finding ways to continue to play together, even if in a non-standard, non-permanent way, is important.

In this question, I’m interested to know what DMs and their players are using to temporarily convert their normal pen and paper, in person gatherings into a system that works with a remote group. I’m specifically interested in answers that address the following common concerns with this type of conversion:

  1. Cost – Low or no added cost (it’s temporary)
  2. Roleplaying – Support for high quality, low delay audio
  3. Content – Support for custom content including maps, handouts, items, etc
  4. Combat – Support for combat positioning, distances, and area effects normally done on a battle mat

Kernel ROP crashes running OS

I was experimenting to see if I can make an ROP chain within the kernel. In the kernel debugging mode, I can make the first jump to an arbitrary gadget address without any problem. But the problem occurs after that. If I want to continue the kernel by typing continue, Kernel freeze. OS did not respond, I have to restart my VM to get back to the working state again.

Now my understanding is, As I jump or return to a random address (gadget) in the kernel, my stack contains doesn’t change as a normal function call would do. Therefore, when I execute the gadget instructions one by one or continue to run the kernel if the instructions needed some value from the stack which is not present there, as a result, kernel crash.

So, My question is, how can I jump/return to multiple gadgets and after running all the gadgets continue to run the kernel without crashing it. I guess there is no easy and straight forward answer for it. But if someone can give some basic idea about where to start that would be very helpful. Thank you in advance.

Data Consistency Between 2 Mysql Databases Running Different Versions

I need to migrate an old web application using old php and mysql versions. I am intending to start by migrating the code that interacts with the database to a new server with the latest versions and allow the old server to use an API in the new server. Ideally I would like to have the data consistent between the database in the new server and the one in the old server. It seems that replication only works only when the master is only one version behind the slave. In this case the difference is a way more than one version. I also want changes to the database on the new server to reflect on the database on the old server. Are there any tools/techniques to help with this situation other than ensuring the data consistency programmatically with cron jobs …. If something is not clear please let me know and all suggestions are welcome.

Algorithm Running Time

I’ll do my best to explain my question but what I’m wondering is how to calculate a theoretical running time of an algorithm. In my textbook I have questions written as such:

If a $ \Theta(\log_2{n})$ algorithm requires 20 seconds to execute on an input of one million elements, approximately how long should it take on an input of two million elements?

The answer it gives is 21 seconds and I’m stuck on how they come up with that number.