2
$\begingroup$

As a hobbyist problem-solver, recently I stumbled upon two problems related to Frobenius numbers on one of competitive coding websites I like: Zombie Apocalypse: the Last Number Standing and Matunga coins. I did some research (i.e. googling), found some information, and most notably a paper which describes a couple of approaches: Faster Algorithms for Frobenius Numbers. I succesfully managed to implement Round Robin, BFD and BFDU algorithms and with that I managed to solve the tasks (yay!). However I also wanted to implement DQQD(U) algorithms described there, and I cannot get the implementation right.

Pseudocode for BFD presented on page 9 is rather clear and I managed to implement it without any special problem. Adding one small update step I also got BFDU right. But with pseudocode for DQQD on p. 15, I always get to the point that first iteration seems to produce expected values like in example table, but things start to go wrong on second iteration.

Pseudocode as given in the paper:


enter image description here


  • Either I am getting things mixed up because of inconsistent indexing used in the paper (1-based for vector A, 0-based for other stuff), or

  • I am misinterpreting some ambiguous symbols (for example, w mutates through the iteration, and Qw can mean different things, depending on whether we use Qw determined on the beginning of the iteration, or we use different Qw every time w changes), or

  • there is a typo or some other mistake somewhere in the pseudocode, or

  • everything is OK there and it's just my mathematical ineptitude getting in the way. Unfortunately, I am not a mathematician, and theoretical basis for the algorithm is beyond my comprehension skills :( Maybe I should just GIT GUD?

I already tried changing here-or-there, but it was just a guessing game. I tried to find other implementations of DQQD, especially one in Mathematica, but they do not seem to be available. I also do not need to have the code written for me. All I need is someone to take a peek at pseudocode of DQQD in mentioned paper, and, if possible, try to implement it or verify it in any way if it's correct and I suck, or if it indeed has some typos, mistakes, or other issues.

Next step: overkilling the problem with FROBENIUS NUMBERS BY LATTICE POINT ENUMERATION :)

$\endgroup$
  • $\begingroup$ +1 for enthusiasm! $\endgroup$ – vonbrand Feb 19 at 1:11
0
$\begingroup$

Try to undestand how the algorithm is supposed to work, and write your own, clean/consistent pseudocode (or directly Python) from it.

You already searched for implementations, look for comments on this paper. You might find corrections published elsewhere...

It is unlikely, but possible, that the given pseudocode or even the proposed algorithm itself is wrong. Mistakes happen.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.