4
$\begingroup$

As a hobbyist problem-solver, recently I stumbled upon two problems related to Frobenius numbers on one of the 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 that describes a couple of approaches: Faster Algorithms for Frobenius Numbers. I successfully 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.

The 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 the first iteration seems to produce expected values like in the example table, but things start to go wrong on the second iteration.

Pseudocode as given in the paper:

[![enter image description here][4]][4]

  • 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 the 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 the pseudocode of DQQD in the 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 :)

Improve this question
$\endgroup$
2
  • $\begingroup$ A partial Python implementation: pastebin.com/fPwAPKd9. It doesn't work correctly though (I might not be understanding some of the notation correctly). You can use this so you don't need to start from scratch. $\endgroup$
    – mqtdzklsb
    Commented Jul 7, 2020 at 6:30
  • $\begingroup$ I cannot directly help with that, but in my case it helped to contact the authors of the algorithm and asking for help there. $\endgroup$
    – DLade
    Commented May 1, 2021 at 10:07

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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